HashTable华山论剑比特宇宙编程语言联合委员会正在准备召开以Hashtable为主题的会议。邀请函已经发往各大编程语言帝国，大会召开的日子马上就要到了。联委会秘书长致开幕词：“各位，为促进科技交流与发展，增进帝国之间的友谊，联委会特举办此次活动，感谢大家的支持。”会场爆发出一阵掌声……秘书长继续发言：“本次会议的主题是哈希表，这是人类程序员使用最多的数据容器之一。相信所有主要的编程语言帝国已经实现了，今天的大会围绕哈希表分为几个话题进行讨论，首先是第一个话题：存储结构与冲突解决来自GoLang帝国的《存储结构与冲突解决》图率先发言：哈希表，哈希表，首先它必须是一个表，所以最基本的就是用一个数组来存储，数组中的每一个元素称为一个桶。至于hash冲突，我们可以用链表来解决。”Go语言帝国地图说完，有人站了起来：“英雄见仁见智！在C++帝国的unordered_map中，我们基本都是这样选择的方法”这时候，Python帝国的代表提出质疑：“链表确实可以解决冲突，但是如果冲突太多，链表太长了，找起来不会费时间吗？”Go帝国的Map和C++帝国的unordered_map面面相觑，不知该如何应对。“如果链表太长，那就转成树形结构吧！”就在这时，又有人站了起来。见有人起身，蟒帝国代表转身问道：“这是蟒帝国的字典dict{}，怎么称呼？”“我是Java帝国的HashMap，太多了，具体来说，当链表长度超过8时，会转为红黑树结构，加快查找速度。”说完，map和unordered_map松了口气，和HashMap一起坐了下来。dict{}继续问：“在座的各位都是这样想的，用链表解决冲突？”说完，另一位代表站了起来，“等等，我们C#帝国的HashTable不是用链表的！”dict{}揭示“那你如何解决冲突？”“我们的HashTable内部使用的是双重哈希法，我们内部有不止一种哈希计算方法，一旦发生Hash冲突，我们会换成另一种重新计算，直到找到有空间存储的地方”，HashTable回复.dict{}看起来有点失望，估计他不是这样用的。“你问了半天，都没说你的Python是怎么处理冲突的？”Java帝国的HashMap之说。“是，是。”其他代表也纷纷附和。看到大家起哄，dict{}只好回答：“链表的方法不错，但是在插入数据的过程中需要动态分配内存来构建链表节点，开销不小，所以我们没有‘用它，我快急死了”，C++的unordered_map有点着急。“我们使用一种叫做开放寻址的策略。如果发现有冲突，我们就会按照既定的策略从这个位置开始向后搜索，直到找到一个空的位置进行存储，”dict{}继续说道。“哪有这么简单的事情，你占了别人的位置，什么那个位置对应的数据来了怎么办？以及如何找到它？如何删除它？这不都乱七八糟的吗？”unordered_map不情愿地问道。“是这样的。根据我们既定的规则，我们在搜索的时候需要做一些额外的工作。另外，我们删除的时候不能直接删除，否则会破坏规则链……”接下来的一段时间，dict{}给大家详细介绍了他们的处理思路。“你太麻烦了，还不如我们的链表法清楚。”“这有什么好麻烦的？好处不是很明显吗？”，dict{}也不甘示弱。就在这时，秘书长打断了大家的辩论：“大家，大家，安静，安静，我们这个话题就此打住，进入下一个话题：hash到locationmapping。”C++帝国代表unordered_map率先发言：“有什么好讨论的，不就是用哈希值对哈希表数组的长度进行取模吗？”“对啊，有什么好讨论的”，C#EmpireHashTable也附和道。大家都看了看，Python帝国的dict{}要出新东西了。戈朗帝国地图问道：“师兄用的是什么方法，别傻了，说说看。”dict{}看了大家一眼，说道：“我的方法是：”这是什么映射方法？代表们不解议论纷纷，只有Java帝国的HashMap闻言微微一笑。dict{}见状问道：“HashMap兄弟，你知道其中的奥秘吗？”HashMap不紧不慢的站起来说：“哈希表的长度是2的次方，减去1后二进制平均就变成1，比如长度16，减1就变成15，也就是二进制1111。进行与运算相当于取hash值的低位，直接映射到对应的数组位置，运算比取模运算要快很多，说实话，我在HashMap中也是用这个方法的。小本事，不值得炫耀。”众代表听完纷纷点头称赞，但dict{}不知何时坐了下来，C#的HashTable问道：“如果直接取低几位，会不会造成Hash值到数组的映射不均匀？”就拿你的例子来说，18的二进制是00010010，34的二进制是00100010，它们的低4位是一样的，1111以上都是0010，也就是应该存放在第2个位置阵列。这不是在一定程度上增加了冲突的概率吗？”突如其来的问题并没有让HashMap慌乱，他平静地解释道：“C#代表的问题很好，不知道dict{}是怎么处理的，我们的解决方案是先处理hash值再进行AND操作映射具体来说，就是对高16位和低16位进行异或运算，使得最后参与AND运算的部分结合了原哈希的所有信息，而不仅仅是低位。代表们听完点头称赞。秘书长打破了平静，“看来大家收获颇丰，我们进入下一个话题：初始产能与扩容。”秘书长见状说道：“没人主动，那我来点名……”“那我先走”，Java帝国的HashMap站了起来，“我默认的初始容量是16，有个参数叫loadfactor，默认是0.75，我的策略是，如果内部数组的空间超过75%，那么就要做好扩容的准备，否则后续Hash冲突的概率会哦对了，扩容的时候容量必须是2的次方，原因前面已经解释过了，指数幂，而我的负载因子是2/3，扩容的时间比这个早HashMap哥。”C#帝国代表HashTable闻言也起身发言：“我的初始容量是3。至于负载因子，我通过大量的实验测试，得到的数据在两位数之间，为0.72。就capacity，我没有要求2的幂，而是一个素数，之所以要素数，是因为我用的是模运算做的映射，如果用素数，冲突会少一些.这时，C++帝国的代表unordered_map也发话了，“巧了！我也是素数。你看，容量我已经提前计算好存起来了。等到扩容的时候，我一个一个拿来就行了。”“结束的时间很快就过去了，在大家热烈的讨论中，一上午很快就结束了。大会接近尾声时，秘书长致辞并宣布：“感谢大家的积极讨论，大会取得圆满成功，本次大会到此结束，我们下期再见！”会场内又是一阵热烈的掌声……然而就在这时，会场外忽然传来一个声音：“这么盛大的活动，怎么能少了我呢？”众人看过来，叹息道：“他还在。”彩蛋会后，C#帝国的代表叫停了C++帝国的代表“哥们，八卦一下，你取什么名字，你看我和Java帝国的代表都叫Hashxxx，你咋不也叫是hash_map还是hash_table？什么叫做unordered_map”“哎，兄弟你不知道，其实我不想叫这个名字，但是，，，这就是说来话长了……”，unordered_map叹了口气。
