到目前为止，我们为了解决表达式树的缓存问题，已经提出了4种不同的处理方式，并且编写了多个操作表达式树的辅助类：

    SimpleKeyBuilder：将表达式树构造成唯一的字符串。
    PrefixTreeVisitor：根据表达式树构造一颗前缀树。
    ExpressionComparer：比较两个表达式树的“大小”关系。
    ExpressionHasher：计算一个表达式树的散列值。
    回想起第一种做法，我们使用最原始的方式，使用字典来存储对象，不过我们需要拼接出一个庞大的字符串，因为它具有“唯一性”。但是其实从那时开始，我们就已经走了一条弯路。在.NET Framework中，一个对象如果要作为字典的“键”，难道一定要是字符串吗？很显然，答案是否定的。事实上，任何类型的对象都可以作为字典的键，而字典认为两个“键”对象相同依靠的是对象的GetHashCode方法和Equals方法。字典的整个查询分两步走：

    首先根据GetHashCode获取对象散列值，用于确定需要查找的对象在那个分组（或者说是“桶”，在数据结构中称为散列表的“buckets”）中。
    每个分组的对象数量很少，然后在使用Equals方法依次进行比较，最终得到相同的那个值。
    因为有了ExpressionComparer和ExpressionHasher，我们已经可以非常轻松地实现那个作为“键”的对象了：

    private class CacheKey
    {
    private IComparer<Expression> m_comparer = new ExpressionComparer();

    public Expression Expression { get; private set; }

    public CacheKey(Expression exp)
    {
    this.Expression = exp;
    }

    private int m_hashCode;
    private bool m_hashCodeInitialized = false;

    public override int GetHashCode()
    {
    if (!this.m_hashCodeInitialized)
    {
    this.m_hashCode = new ExpressionHasher().Hash(this.Expression);
    this.m_hashCodeInitialized = true;
    }

    return this.m_hashCode;
    }

    public override bool Equals(object obj)
    {
    if (obj == null) return false;
    if (obj.GetType() != this.GetType()) return false;

    CacheKey other = (CacheKey)obj;
    return this.m_comparer.Compare(this.Expression, other.Expression) == 0;
    }
    }
    最后再实现一个DictionaryCache：

    public class DictionaryCache<T> : IExpressionCache<T> where T : class
    {
    private ReaderWriterLockSlim m_rwLock = new ReaderWriterLockSlim();
    private Dictionary<CacheKey, T> m_storage = new Dictionary<CacheKey, T>();

    public T Get(Expression key, Func<Expression, T> creator)
    {
    T value;
    CacheKey cacheKey = new CacheKey(key);

    this.m_rwLock.EnterReadLock();
    try
    {
    if (this.m_storage.TryGetValue(cacheKey, out value))
    {
    return value;
    }
    }
    finally
    {
    this.m_rwLock.ExitReadLock();
    }

    this.m_rwLock.EnterWriteLock();
    try
    {
    if (this.m_storage.TryGetValue(cacheKey, out value))
    {
    return value;
    }

    value = creator(key);
    this.m_storage.Add(cacheKey, value);
    return value;
    }
    finally
    {
    this.m_rwLock.ExitWriteLock();
    }
    }
    }
    DictionaryCache的实现其实和HashedListCache比较接近，不过从理论上说，DictionaryCache的性能不如HashedListCache。因为同样在根据散列值获取到分组后，DictionaryCache中的分组元素数量可能会比HashedListCache要多（因为字典中多个散列值也可以在同一个分组中）；同时，字典在同组的k个元素中找到指定元素使用O(k)的遍历算法，而二叉搜索树只要O(log(k))的时间复杂度——此消彼长，DictionaryCache的性能自然就要略差一些了。

    至此，老赵在这个话题中计划谈起的5种解决方案都已经讲述完毕了，您觉得哪种做法的效果优秀呢？在今后的文章中，老赵将会对5种解决方案进行性能上的比较并进行分析，同时给出每种方案的优点、缺点和改进余地——其实这些才是最重要的，朋友们千万不要错过，也欢迎大家和我一起讨论。

原文地址：http://www.cnblogs.com/jeffreyzhao/archive/2009/03/20/expression-cache-5-hash-based-cache.html