using System;
using System.Collections;public class SamplesHashtable
{ public static void Main()
{
// 虽然我设定初始容量，但好像小于11就会按默认值11来
Hashtable myHT = new Hashtable(2); // 存入 buckets 数组位置 0, hash_coll = 11, key = 11
// 可能 11 除以 11 余数为 0，所以才定位在0上，余数定位的想法在 12 13 等数上都验证过
myHT.Add(11, "Hello");
// 本来应该存入位置 0，因为和上边重叠，所以存入位置 2 了，2 是怎么算出来的？
// 另外位置 0 的 hash_coll 变为 -2147483637，为什么？ -2147483637 怎么算出来的？
myHT.Add(0, "World"); // 特意让其 HashCode 和位置 0 的 hash_coll 相同，结果被存入了位置 4，4 是怎么算出来的？
// 另外位置 2 的 hash_coll 变为 -2147483648，为什么？ -2147483648 怎么算出来的？
// 还有位置 4 的 hash_coll 本来应该是 -2147483637，现在却是 11，为什么？
myHT.Add(-2147483637, "!"); // 实验方法：
// 本程序用 VS2005 监视 myHT 的非公共成员
// 发现 buckets 数组专门用来存储各个键对的内容
// 但存入 buckets 数组的位置是怎么算出来的？
// 还有遇到以上存入位置重叠的情况，内部又发生了什么？
// 关于 HashTable 的实现原理，高手来帮帮我吧。
}
}
using System.Collections;public class SamplesHashtable
{ public static void Main()
{
// 虽然我设定初始容量，但好像小于11就会按默认值11来
Hashtable myHT = new Hashtable(2); // 存入 buckets 数组位置 0, hash_coll = 11, key = 11
// 可能 11 除以 11 余数为 0，所以才定位在0上，余数定位的想法在 12 13 等数上都验证过
myHT.Add(11, "Hello");
// 本来应该存入位置 0，因为和上边重叠，所以存入位置 2 了，2 是怎么算出来的？
// 另外位置 0 的 hash_coll 变为 -2147483637，为什么？ -2147483637 怎么算出来的？
myHT.Add(0, "World"); // 特意让其 HashCode 和位置 0 的 hash_coll 相同，结果被存入了位置 4，4 是怎么算出来的？
// 另外位置 2 的 hash_coll 变为 -2147483648，为什么？ -2147483648 怎么算出来的？
// 还有位置 4 的 hash_coll 本来应该是 -2147483637，现在却是 11，为什么？
myHT.Add(-2147483637, "!"); // 实验方法：
// 本程序用 VS2005 监视 myHT 的非公共成员
// 发现 buckets 数组专门用来存储各个键对的内容
// 但存入 buckets 数组的位置是怎么算出来的？
// 还有遇到以上存入位置重叠的情况，内部又发生了什么？
// 关于 HashTable 的实现原理，高手来帮帮我吧。
}
}
先介绍介绍其中的基本知识，所谓Hash，一般是一个整数，通过某种算法，可以把一个字符串"压缩" 成一个整数，这个数称为Hash，当然，无论如何，一个32位整数是无法对应回一个字符串的，但在程序中，两个字符
串计算出的Hash值相等的可能非常小具体计算的方法是数学家所掌握的
字符串也是object 的子类其实可以理解 HashTable 为指针名为与地址的映射内存中
HashCode就像指针的名字 而 里边的东西就放在HashCode指针指向的内存中
HASHTABLE的容量是素数，如果小于11会取11，这是定好的。
首先，对key进行求GetHashCode()
对这个HASH取其低31位作为需有HASH值
并且将这个值的二进制右移5位，也就是除以32后加1再与HASHTABLE的容量－1取余数再加1作为冲突后的偏移量，后面要用到
公式 incr = 1 + ((((Hash低31位 >> 5) + 1) % (hashsize - 1)));
你这里的领衔量就是2，可以算出来的。
然后将这个HASH除以TABLE的容量的余数作为索引
如果该位置为空，则将value放入这个位置中。
如果该位置不为空且key相同，则更新该位置为value
如果该位置不为空且key不相同则发生冲突
将hash_coll的高31位开始置为1，代表有冲突发生
然后将索引位置向后移动前机算得的偏移量incr
重复上述步骤，直至找到可以放的位置。可以完美解释你看到的情况，有问题继续留
using System.Collections; public class SamplesHashtable
{ public static void Main()
{
// 虽然我设定初始容量，但好像小于11就会按默认值11来
// 你说对了
Hashtable myHT = new Hashtable(2); // 存入 buckets 数组位置 0, hash_coll = 11, key = 11
// 可能 11 除以 11 余数为 0，所以才定位在0上，余数定位的想法在 12 13 等数上都验证过
// 事情就是这样子的
myHT.Add(11, "Hello");
// 本来应该存入位置 0，因为和上边重叠，所以存入位置 2 了，2 是怎么算出来的？
// 另外位置 0 的 hash_coll 变为 -2147483637，为什么？ -2147483637 怎么算出来的？
// 2是由你的key的HASH值低31位除32加1除以TABLE容量取余再加1得出的偏移量
// -2147483637 是你的key的HASH高33位置1得出的，用于标识该位置有冲突
myHT.Add(0, "World"); // 特意让其 HashCode 和位置 0 的 hash_coll 相同，结果被存入了位置 4，4 是怎么算出来的？
// 另外位置 2 的 hash_coll 变为 -2147483648，为什么？ -2147483648 怎么算出来的？
// 还有位置 4 的 hash_coll 本来应该是 -2147483637，现在却是 11，为什么？
// 同上
myHT.Add(-2147483637, "!"); // 实验方法：
// 本程序用 VS2005 监视 myHT 的非公共成员
// 发现 buckets 数组专门用来存储各个键对的内容
// 但存入 buckets 数组的位置是怎么算出来的？
// 还有遇到以上存入位置重叠的情况，内部又发生了什么？
// 关于 HashTable 的实现原理，高手来帮帮我吧。
}
}
0d | FFFFFFFF80000000h = -2147483648d
-2147483637 | FFFFFFFF80000000h = 11dFFFFFFFF80000000h = 1111111111111111111111111111111110000000000000000000000000000000b够明白了吧，高位置1目的是为了标识该位置有冲突
-2147483637d & 7FFFFFFFh = 11d
之前说了，因为对key，GetHashCode()后取低31位作为HASH值
所以-2147483637和11对于Hashtable来说相当于是同一个key
那么我在设计 HashTable 类内联的 IEnumerator 结构时，是先拷贝 buckets 的副本按 key 值排序吗？有没有效率更高的算法。还有 HashTable 达到规定的 loadFactor （默认是0.72，好像是微软 HashTable 开发团队经过大量试验后得出的最佳值），需要扩大内部的 buckets 数组，新容量为旧容量 2 倍以上最小的素数，这样需要把所有旧数组的元素按照 key 值重新在新数组中定位吗？有没有效率更高的算法。或你有相关的网址，我去研究下，谢谢！
那么我在设计 HashTable 类内联的 IEnumerator 结构时，是先拷贝 buckets 的副本按 key 值排序吗？有没有效率更高的算法。 还有 HashTable 达到规定的 loadFactor （默认是0.72，好像是微软 HashTable 开发团队经过大量试验后得出的最佳值），需要扩大内部的 buckets 数组，新容量为旧容量 2 倍以上最小的素数，这样需要把所有旧数组的元素按照 key 值重新在新数组中定位吗？有没有效率更高的算法。 或你有相关的网址，我去研究下，谢谢！
----------------------------------素数容量能够降低第一次的key hash值冲突概率, 但是并不能避免冲突, Hashtable一般会采取多次Hash, 移位处理, 桶处理等几种方法来避免Hash冲突.
.Net采用的是桶处理.
几个名词的具体含义你google一下就明白了.Hashtable不存在排序的概念, Hash表是用于查找的, 如果你要排序之类, 用链表或者普通数组.
扩大容量并不会重新定位, 因为Hash算法是一定的. 扩大容量是由于有的Key的hash值超出了最大的Index, 需要扩容.
第2个，是重新进行定位的。不重新定位分布就不平均了。
存储的位置是HASH的低31位除以容量长度的余数
既然容量变了，位置当然也会变
所以扩容的时候先算新的容量，初始化新的buckets
然后遍历原buckets，计算位置放入新buckets
完了把原buckets指向新buckets。
HashTable 容量一定会是素数，那些素数是动态计算出来的，还是静态的素数数组？如果动态计算的，如题：Hashtable myHT = new Hashtable(21);
loadFactor 默认是 0.72，
所以内部 buckets 数组长度就是 29，因为 21 / 29 = 0.72（小数点2位后的数字抛弃），没超过 loadFactor Hashtable myHT = new Hashtable(22);
按上边的想法 22 / 31 < 0.72，应该取 31 为 buckets 数组长度，
可为什么系统给开成37个元素的数组了？我发现相隔2的素数都有这个情况，较大的那个从来不取，例如11完了直接找17，而不是13。
这情况只有理解为静态的素数数组才比较好理解。不过我感觉也不一定对。总之就是，有些搞不明白 Hashtable 构造函数怎么根据用户传入的 capacity 初始化 buckets 的数组长度。
大于这个值的就去运行时计算。
小于7199369的值分别如下：
3, 7, 11, 0x11, 0x17, 0x1d, 0x25, 0x2f, 0x3b, 0x47, 0x59, 0x6b, 0x83, 0xa3, 0xc5, 0xef, 0x125, 0x161, 0x1af, 0x209, 0x277, 0x2f9, 0x397, 0x44f, 0x52f, 0x63d, 0x78b, 0x91d, 0xaf1, 0xd2b, 0xfd1, 0x12fd, 0x16cf, 0x1b65, 0x20e3, 0x2777, 0x2f6f, 0x38ff, 0x446f, 0x521f, 0x628d, 0x7655, 0x8e01, 0xaa6b, 0xcc89, 0xf583, 0x126a7, 0x1619b, 0x1a857, 0x1fd3b, 0x26315, 0x2dd67, 0x3701b, 0x42023, 0x4f361, 0x5f0ed, 0x72125, 0x88e31, 0xa443b, 0xc51eb, 0xec8c1, 0x11bdbf, 0x154a3f, 0x198c4f, 0x1ea867, 0x24ca19, 0x2c25c1, 0x34fa1b, 0x3f928f, 0x4c4987, 0x5b8b6f, 0x6dda89
软件说明：
哈希表是重要的数据结构形式，微软特意让所有类都实现GetObject()，来支持 Hashtable，可见其重要性。 但大部分朋友可能不太了解哈希表（字典）内部是怎么运作的，所以一直很想搞明白它。 现在好了，源代码加详细注释，你想不成为专家都难，赶快下载吧！ 源码一切规则都照搬微软源码的！客户端代码兼容度超过 95%，功能实现大约 2/3。 相当于微软的开源代码！ 欢迎下载！