ExpressionHasher有个Hash方法，可用于计算一个表达式数的散列值。与之前的几种ExpressionVisitor实现类似，ExpressionHasher也准备一些辅助方法供其他方法调用。这些辅助方法接受不同类型的参数，完全避免了数据的装箱/拆箱，尽可能保持算法的高效。从上面的代码看出，我们不断地向这些辅助方法内传入对象时，它们会被累加到HashCode属性中——这就是老赵在这里使用的“组合方式”，将表达式树中每个元素的散列值进行组合，最终成为整个表达式数的散列值。老赵无法证明这是一种优秀的散列组合算法，但是从测试上来看，这么做的效果还是不错的（事实上，老赵随机生成了大量表达式还没有出现碰撞）。更关键的一点是，这么做非常高效，如果将这些元素拼接起来，并得到最终字符串的散列值可能会有更好的结果，但是其性能就比整数的相加要差许多了。
现在，我们只需要在Visit每个节点的时候，把节点的属性作为表达式树的每个元素传入对应的辅助方法便可，以下为部分代码：
{
if (exp == null) return exp;
this.Hash((int)exp.NodeType).Hash(exp.Type);
return base.Visit(exp);
}
protected override Expression VisitBinary(BinaryExpression b)
{
this.Hash(b.IsLifted).Hash(b.IsLiftedToNull).Hash(b.Method);
return base.VisitBinary(b);
}
protected override Expression VisitConstant(ConstantExpression c)
{
this.Hash(c.Value);
return base.VisitConstant(c);
}
protected override Expression VisitMemberAccess(MemberExpression m)
{
this.Hash(m.Member);
return base.VisitMemberAccess(m);
}
protected override Expression VisitMethodCall(MethodCallExpression m)
{
this.Hash(m.Method);
return base.VisitMethodCall(m);
}
...
按照我们刚才的设想，首先计算出一个表达式树的散列值，然后从字典中获取具体的一个分组，再从这个分组中进行查找。使用这个方法则得到了HashedListCache：
{
private ReaderWriterLockSlim m_rwLock = new ReaderWriterLockSlim();
private Dictionary<int, SortedList<Expression, T>> m_storage =
new Dictionary<int, SortedList<Expression, T>>();
public T Get(Expression key, Func<Expression, T> creator)
{
SortedList<Expression, T> sortedList;
T value;
int hash = new ExpressionHasher().Hash(key);
this.m_rwLock.EnterReadLock();
try
{
if (this.m_storage.TryGetValue(hash, out sortedList) &&
sortedList.TryGetValue(key, out value))
{
return value;
}
}
finally
{
this.m_rwLock.ExitReadLock();
}
this.m_rwLock.EnterWriteLock();
try
{
if (!this.m_storage.TryGetValue(hash, out sortedList))
{
sortedList = new SortedList<Expression, T>(new ExpressionComparer());
this.m_storage.Add(hash, sortedList);
}
if (!sortedList.TryGetValue(key, out value))
{
value = creator(key);
sortedList.Add(key, value);
}
return value;
}
finally
{
this.m_rwLock.ExitWriteLock();
}
}
}
计算一个表达式树的散列值需要耗费O(m)的时间复杂度，从字典中查找分组需要O(1)，如果散列值够好的话，每个分组中的表达式树数量（k）应该非常少，这样从中进行查询的时间复杂度（O(log(k))）就非常接近于常数了。因此，HashedListCache的查找操作，其时间复杂度为O(m)，这也达到了最为理想的时间复杂度。
