本文转自ICMLL实验室对问题 如何理解哈希表的工作原理？的回答

哈希表是根据关键值(key)来直接访问目标值(value)的一种数据结构。其特点就在于能够快捷的实现信息的查询和检索。

比如我们在手机中存放的通讯录就是用哈希表来实现的，即我们输入一个联系人的姓名，就能返回相应的电话号码。用哈希表实现的过程就是，将联系人姓名的字符通过一个哈希函数，映射成一个整数（哈希码），然后根据哈希码来索引出电话号码。比如哈希码为5，就表示是在存储位置为5，因此我们就能直接取出该位置的值，并返回结果。

那么实现哈希表的关键就在于哈希函数的构建，也就是如何建立一个合适的索引来满足如下条件：

    (1）同一个键每次输入到哈希函数中，其对应的哈希码也必须相同；

    (2）不同键对应的哈希码不能相同。

第一个条件意味着哈希函数必须是确定性的；第二个条件则要求不能出现哈希冲突。当两个或更多个键产生相同的哈希码时就会发生冲突（hash collisions）。

比如我们现在考虑建立一个简单的哈希表来查询年龄,{Jim：5, Davis：7, Taylor:12, Bob:3}，如果我们选择哈希函数为输入键值的字符个数。那么在建立哈希表时，就讲Jim存放在位置3处，Jack存放在位置4处。而这样的话Jim和Bob的存储位置就会发生冲突，不符合哈希函数的要求。但是如果我们将哈希函数替换为首字母顺序存放，在这个数据中就没有哈希冲突了。

然而万一无法避免哈希冲突的话，我们可以用链接和线性探测的方法来避免哈希值发生碰撞。

链接就是将发生冲突的键值直接链接在链表的尾部；线性探测则是，如果在位置i处发生冲突，那么就检查i+1处是否为空，为空的话就将冲突键值放入其中，否则继续检查下一个。

没有完全讲透，一次哈希、二次哈希、三次哈希。。。

最好的哈希算法，暴雪哈希，玩游戏的应该都知道~哈~

其实还应该关注一下算法复杂度、和非线性的问题；

另外，就是散列分布的密度，决定了哈希算法的好坏。。。

顶一下~