上篇文章，我们知道了散列函数会使得 Key 发生碰撞冲突。
那么，.NET 的 Hashtable 类是如何解决该问题的呢？
很简单，探测。
我们首先利用散列函数 GetHashCode() 取得 Key 的散列值。为了保证该值在数组索引范围内，让其与数组大小求模。这样便得到了Key 对应的 Value 在数组内的实际位置，即 f(K) = (GetHashCode() & 0x7FFFFFFF) %Array.Length。
当有多个 Key的散列值重复的时候(即发生碰撞冲突时)，算法将会尝试着把该值放到下一个合适的位置上，如果该位置已经被占用，则继续寻找，直到找到合适的空闲的位置。如果冲突的数量越多，那么搜索的次数也越多，效率也越低(无论是线性探测法，二次探测法，双散列法都会这样寻找，只不过寻找的偏移位置算法不同而已，.NET Hashtable 类使用的是双散列法)。整个过程如下图所示：
如果散列表的容量接近饱和时，找到合适的空闲的位置将会很困难，而且发生碰撞冲突的几率也很大。这个时候，就要对散列表进行扩容。那我们根据什么来判断应该扩容了呢？根据散列表内部数组容量和装填因子。当散列表元素数量 = 数组大小 * 装填因子时，就应该扩容了。
.NET Hashtable 类默认的装填因子是 1.0。但实际上它默认的装填因子是 0.72，Microsoft认为这个值对于开发人员来说不好记，所以改成了 1.0。所有从构造函数输入的装填因子，Hashtable 类内部都会将其乘以0.72。这是一个要求苛刻的数字, 某些时刻将装填因子增减 0.01, 可能你的 Hashtable 存取效率就提高或降低了 50%,其原因是装填因子决定散列表容量, 而散列表容量又影响 Key 的冲突几率, 进而影响性能. 0.72 是 Microsoft经过大量实验得出的一个比较平衡的值. (取什么值合适和解决冲突的算法也有关， 0.72 不一定适合其他结构的散列表，比如 Java 的HashMap<K, V> 默认的装填因子是 0.75)。
扩容是个耗时非常惊人的内部操作，Hashtable 之所以写入效率仅为读取效率的 1/10 数量级,频繁的扩容是一个因素。当进行扩容时，散列表内部要重新 new 一个更大的数组，然后把原来数组的内容拷贝到新数组，并进行重新散列。如何 new这个更大的数组也有讲究。散列表的初始容量一般来讲是个素数。当扩容时，新数组的大小会设置成原数组双倍大小的相近的一个素数。为了避免生成素数的额外开销，.NET 内部有一个素数数组，记录了常用到的素数。如下所示：
当要扩容的数组大小超过以上素数时，再使用素数生成算法来获取跟其两倍大小相近的素数。正常情况下，我们可能不会存储这么多内容。细心的你可能发现这样很耗内存。没错，这的确非常耗费内存资源。比如当我们要在容量为 11 的 Hashtable 中添加 8 个元素。因为 8 / 11> 0.72，所以要扩容。根据算法，跟 2 * 11 相近的素数是 23。看出有多浪费了吧。即使通过构造函数把容量设置为 17，也浪费了9 个空间。假如你有 Key - Value 映射的需求，同时对内存又比较苛刻，可以考虑使用由红黑树构造的词典或映射。
那 Dictionary<TKey, TValue> 又是什么情况呢？
它没有采用 Hashtable 类的探测方法，而是采用了一种更流行，更节约空间的方法：分离链接散列法(separate chaining hashing)。
采用分离链接法的 Dictionary<TKey, TValue> 会在内部维护一个链表数组。对于这个链表数组 L0,L1,...，LM-1,散列函数将告诉我们应当把元素 X 插入到链表的什么位置。然后在 find 操作时告诉我们哪一个表中包含了 X。这种方法的思想在于：尽管搜索一个链表是线性操作，但如果表足够小，搜索非常快(事实也的确如此，同时这也是查找，插入，删除等操作并非总是 O(1) 的原因)。特别是，它不受装填因子的限制。
这种情况下，常见的装填因子是 1.0。更低的装填因子并不能明显的提高性能，但却需要更多的额外空间。Dictionary<TKey,TValue> 的默认装填因子便是 1.0。Microsoft 甚至认为没有必要修改装填因子，所以我们可以看到Dictionary<TKey, TValue> 的构造函数中找不到关于装填因子的信息。Java 的 HashMap<K,V> 默认装填因子是 0.75。它的理由是这样可以减少检索的时间。我在测试的时候，发现Java HashMap<K, V>检索时间的确要比 .NET Dictionay<TKey, TValue> 的检索时间要少，但差距相当微小。同时HashMap<K, V> 的插入时间却跟 Dictionary<TKey, TValue>差了老大一截，几乎是后者的 3~8 倍。一开始，我以为是错觉。因为 HashMap<K, V>没有采用取模操作，而是位移操作，而且它使用的容量大小也是以 2 的指数级增长。这些都是些加速操作。甚是疑惑，望达人解答。
分离链接散列法的吸引力不仅在于适度增加装填因子时，性能不受影响，而且可以在扩容时避免再次散列(这相当耗时)。
最后，当我们要在应用程序中使用 Hashtable 或 Dictionary<TKey, TValue> 时，请尽量评估要插入的元素数量，因为这可以有效避免扩容和再次散列操作。同时，装填因子尽量使用 1.0。
PS：实现代码就不给出了。待描述并发散列表时，一并给出吧。:-)
那么，.NET 的 Hashtable 类是如何解决该问题的呢？
很简单，探测。
我们首先利用散列函数 GetHashCode() 取得 Key 的散列值。为了保证该值在数组索引范围内，让其与数组大小求模。这样便得到了Key 对应的 Value 在数组内的实际位置，即 f(K) = (GetHashCode() & 0x7FFFFFFF) %Array.Length。
当有多个 Key的散列值重复的时候(即发生碰撞冲突时)，算法将会尝试着把该值放到下一个合适的位置上，如果该位置已经被占用，则继续寻找，直到找到合适的空闲的位置。如果冲突的数量越多，那么搜索的次数也越多，效率也越低(无论是线性探测法，二次探测法，双散列法都会这样寻找，只不过寻找的偏移位置算法不同而已，.NET Hashtable 类使用的是双散列法)。整个过程如下图所示：
如果散列表的容量接近饱和时，找到合适的空闲的位置将会很困难，而且发生碰撞冲突的几率也很大。这个时候，就要对散列表进行扩容。那我们根据什么来判断应该扩容了呢？根据散列表内部数组容量和装填因子。当散列表元素数量 = 数组大小 * 装填因子时，就应该扩容了。
.NET Hashtable 类默认的装填因子是 1.0。但实际上它默认的装填因子是 0.72，Microsoft认为这个值对于开发人员来说不好记，所以改成了 1.0。所有从构造函数输入的装填因子，Hashtable 类内部都会将其乘以0.72。这是一个要求苛刻的数字, 某些时刻将装填因子增减 0.01, 可能你的 Hashtable 存取效率就提高或降低了 50%,其原因是装填因子决定散列表容量, 而散列表容量又影响 Key 的冲突几率, 进而影响性能. 0.72 是 Microsoft经过大量实验得出的一个比较平衡的值. (取什么值合适和解决冲突的算法也有关， 0.72 不一定适合其他结构的散列表，比如 Java 的HashMap<K, V> 默认的装填因子是 0.75)。
扩容是个耗时非常惊人的内部操作，Hashtable 之所以写入效率仅为读取效率的 1/10 数量级,频繁的扩容是一个因素。当进行扩容时，散列表内部要重新 new 一个更大的数组，然后把原来数组的内容拷贝到新数组，并进行重新散列。如何 new这个更大的数组也有讲究。散列表的初始容量一般来讲是个素数。当扩容时，新数组的大小会设置成原数组双倍大小的相近的一个素数。为了避免生成素数的额外开销，.NET 内部有一个素数数组，记录了常用到的素数。如下所示：
CODE:
internal static readonly int[] primes =
{
3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107,
131, 163, 197, 239, 293, 353, 431, 521, 631, 761,
919, 1103, 1327, 1597, 1931, 2333, 2801, 3371,
4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
17519, 21023, 25229, 30293, 36353, 43627, 52361,
62851, 75431, 90523, 108631, 130363, 156437,
187751, 225307, 270371, 324449, 389357, 467237,
560689, 672827, 807403, 968897, 1162687, 1395263,
1674319, 2009191, 2411033, 2893249, 3471899,
4166287, 4999559, 5999471, 7199369
};
{
3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107,
131, 163, 197, 239, 293, 353, 431, 521, 631, 761,
919, 1103, 1327, 1597, 1931, 2333, 2801, 3371,
4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
17519, 21023, 25229, 30293, 36353, 43627, 52361,
62851, 75431, 90523, 108631, 130363, 156437,
187751, 225307, 270371, 324449, 389357, 467237,
560689, 672827, 807403, 968897, 1162687, 1395263,
1674319, 2009191, 2411033, 2893249, 3471899,
4166287, 4999559, 5999471, 7199369
};
当要扩容的数组大小超过以上素数时，再使用素数生成算法来获取跟其两倍大小相近的素数。正常情况下，我们可能不会存储这么多内容。细心的你可能发现这样很耗内存。没错，这的确非常耗费内存资源。比如当我们要在容量为 11 的 Hashtable 中添加 8 个元素。因为 8 / 11> 0.72，所以要扩容。根据算法，跟 2 * 11 相近的素数是 23。看出有多浪费了吧。即使通过构造函数把容量设置为 17，也浪费了9 个空间。假如你有 Key - Value 映射的需求，同时对内存又比较苛刻，可以考虑使用由红黑树构造的词典或映射。
那 Dictionary<TKey, TValue> 又是什么情况呢？
它没有采用 Hashtable 类的探测方法，而是采用了一种更流行，更节约空间的方法：分离链接散列法(separate chaining hashing)。
采用分离链接法的 Dictionary<TKey, TValue> 会在内部维护一个链表数组。对于这个链表数组 L0,L1,...，LM-1,散列函数将告诉我们应当把元素 X 插入到链表的什么位置。然后在 find 操作时告诉我们哪一个表中包含了 X。这种方法的思想在于：尽管搜索一个链表是线性操作，但如果表足够小，搜索非常快(事实也的确如此，同时这也是查找，插入，删除等操作并非总是 O(1) 的原因)。特别是，它不受装填因子的限制。
这种情况下，常见的装填因子是 1.0。更低的装填因子并不能明显的提高性能，但却需要更多的额外空间。Dictionary<TKey,TValue> 的默认装填因子便是 1.0。Microsoft 甚至认为没有必要修改装填因子，所以我们可以看到Dictionary<TKey, TValue> 的构造函数中找不到关于装填因子的信息。Java 的 HashMap<K,V> 默认装填因子是 0.75。它的理由是这样可以减少检索的时间。我在测试的时候，发现Java HashMap<K, V>检索时间的确要比 .NET Dictionay<TKey, TValue> 的检索时间要少，但差距相当微小。同时HashMap<K, V> 的插入时间却跟 Dictionary<TKey, TValue>差了老大一截，几乎是后者的 3~8 倍。一开始，我以为是错觉。因为 HashMap<K, V>没有采用取模操作，而是位移操作，而且它使用的容量大小也是以 2 的指数级增长。这些都是些加速操作。甚是疑惑，望达人解答。
分离链接散列法的吸引力不仅在于适度增加装填因子时，性能不受影响，而且可以在扩容时避免再次散列(这相当耗时)。
最后，当我们要在应用程序中使用 Hashtable 或 Dictionary<TKey, TValue> 时，请尽量评估要插入的元素数量，因为这可以有效避免扩容和再次散列操作。同时，装填因子尽量使用 1.0。
PS：实现代码就不给出了。待描述并发散列表时，一并给出吧。:-)
添加至收藏夹