共计 3626 个字符，预计需要花费 10 分钟才能阅读完成。
对于散列表的代码实现及下边实际局部的代码实现均可从我的 Github 获取（欢送 star^_^）
散列思维
概念
散列表（Hash Table），也能够叫它 哈希表 或者Hash 表
散列表用的是数组反对依照下标随机拜访数据的个性，所以散列表其实就是数组的一种扩大，由数组演变而来。能够说，如果没有数组，就没有散列表
举例
假如全校有 1000 名学生，为了不便记录他们的期末问题，会给每个学生一个编号，编号从 1~1000。当初如果要实现通过编号来找到具体的学生
能够把这 1000 个学生的信息放在数组里。编号为 1 的学生，放到数组中下标为 1 的地位；编号为 2 的学生，放到数组中下标为 2 的地位。以此类推，编号为 k 的学生放到数组中下标为 k 的地位
因为编号跟数组下标一一对应，当咱们须要查问编号为 x 的学生的时候，只须要将下标为 x 的数组元素取出来就能够了，工夫复杂度就是 O(1)
实际上，这个例子曾经用到了散列的思维。在这个例子里，编号是自然数，并且与数组的下标造成一一映射，所以利用数组反对依据下标随机拜访的个性，查找的工夫复杂度是 O(1)，就能够实现疾速查找编号对应的学生信息
然而，上边这个例子用到的散列思维不够显著，改一下
假如编号不能设置得这么简略，要加上年级、班级这些更具体的信息，所以这里把编号的规定略微批改了一下，用 8 位数字来示意。比方 05110067，其中，前两位 05 示意年级，两头两位 11 示意班级，最初四位还是原来的编号 1 到 1000。这个时候该如何存储学生信息，才可能反对通过编号来疾速查找学生信息呢？
思路还是跟后面相似。只管不能间接把编号作为数组下标，但能够截取编号的后四位作为数组下标，来存取学生信息数据。当通过编号查问学生信息的时候，用同样的办法，取编号的后四位，作为数组下标，来读取数组中的数据
这就是典型的散列思维。其中，学生的编号叫作 键（key）或者 关键字 。用它来标识一个学生。把学生编号转化为数组下标的映射办法就叫作 散列函数 （或“Hash 函数”“哈希函数”），而散列函数计算失去的值就叫作 散列值（或“Hash 值”“哈希值”）
总结
散列表用的就是数组反对依照下标随机拜访的时候，工夫复杂度是 O(1)的个性。通过散列函数把元素的键值映射为下标，而后将数据存储在数组中对应下标的地位。当依照键值查问元素时，用同样的散列函数，将键值转化数组下标，从对应的数组下标的地位取数据
散列函数
概念
散列函数，顾名思义，它是一个函数。能够把它定义成 hash(key)，其中 key 示意元素的键值，hash(key) 的值示意通过散列函数计算失去的 散列值
在上边的例子中，编号就是数组下标，所以 hash(key)就等于 key。革新后的例子，写成散列函数就像下边这样
func hash(key string) int {hashValue,_ := strconv.Atoi(key[len(key)-4:])
return hashValue
}散列函数根本要求
上边的的例子，散列函数比较简单，也比拟容易想到。然而，如果学生的编号是随机生成的 6 位数字，又或者用的是 a 到 z 之间的字符串，这种状况，散列函数就会简单一些
散列函数设计的根本要求
- 散列函数计算失去的散列值是一个 非负整数
- 如果 key1 = key2，那 hash(key1) == hash(key2)
- 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)
第一点了解起来应该没有任何问题。因为数组下标是从 0 开始的，所以散列函数生成的散列值也要是非负整数。第二点也很好了解。雷同的 key，通过散列函数失去的散列值也应该是雷同的
第三点了解起来可能会有问题。这个要求看起来荒诞不经，然而在实在的状况下，要想找到一个不同的 key 对应的散列值都不一样的散列函数，简直是不可能的。即使像业界驰名的 MD5、SHA、CRC 等哈希算法，也无奈完全避免这种散列抵触。而且，因为数组的存储空间无限，也会加大散列抵触的概率
所以，简直无奈找到一个完满的无抵触的散列函数，即使能找到，付出的工夫老本、计算成本也是很大的，所以针对散列抵触问题，须要通过其余路径来解决
散列抵触
凋谢寻址法
凋谢寻址法的核心思想是，如果呈现了散列抵触，就从新探测一个闲暇地位，将其插入 。
从新探测一个闲暇地位的办法有好几个，这里以 线性探测 举例
当往散列表中插入数据时，如果某个数据通过散列函数散列之后，存储地位曾经被占用了，就从以后地位开始，顺次往后查找，看是否有闲暇地位，直到找到为止。看下图
从图中能够看出，散列表的大小为 10，在元素 x 插入散列表之前，曾经有 6 个元素插入到散列表中。x 通过 hash 算法之后，被散列到下标为 7 的地位，然而这个地位曾经有数据了，所以就产生了抵触。于是就程序地往后一个一个找，看有没有闲暇的地位，遍历到尾部都没有找到闲暇的地位，于是再从表头开始找，直到找到闲暇地位 2，于是将其插入到这个地位
在散列表中查找元素的过程相似插入过程。通过散列函数求出要查找元素的键值对应的散列值，而后比拟数组中下标为散列值的元素和要查找的元素。如果相等，则阐明就是咱们要找的元素；否则就程序往后顺次查找。如果遍历到数组中的闲暇地位，还没有找到，就阐明要查找的元素并没有在散列表中
散列表和数组一样，也反对插入、查找、删除操作，然而对于线性探测办法解决散列抵触，在进行删除操作时比拟非凡，不能单纯地把要删除的元素设置为空
上边在说散列表的查找操作时，通过线性探测的形式找到一个闲暇地位，而后就认定散列表中不存在该数据。如果说这个闲暇地位是起初删除的，就会导致原来的线性探测有问题，可能原本存在的数据，认为不存在了
这种状况下，就须要 将删除的元素加一个删除的标记。在进行线性探测的时候，如果遇到删除标记的元素，则持续向下探测
小伙伴必定曾经看出问题了，当散列表中插入的数据越来越多时，散列抵触产生的可能性就会越来越大，闲暇地位会越来越少，线性探测的工夫就会越来越久。极其状况下，可能须要探测整个散列表，所以最坏状况下的工夫复杂度为 O(n)。同理，在删除和查找时，也有可能会线性探测整张散列表，能力找到要查找或者删除的数据
对于凋谢寻址抵触解决办法，除了线性探测办法之外，还有另外两种比拟经典的探测办法，二次探测 （Quadratic probing）和 双重散列（Double hashing）
二次探测
二次探测跟线性探测很像，线性探测每次探测的步长是 1，它探测的下标序列就是 hash(key)+0，hash(key)+1，hash(key)+2……而二次探测探测的步长就变成了原来的“二次方”，它探测的下标序列是 hash(key)+0，hash(key)+1^2，hash(key)+2^2,hash(key)+3^2……
双重散列
双重散列意思就是不仅要应用一个散列函数。应用一组散列函数 hash1(key)，hash2(key)，hash3(key)……先用第一个散列函数，如果计算失去的存储地位曾经被占用，再用第二个散列函数，顺次类推，直到找到闲暇的存储地位
凋谢寻址法总结
不论采纳哪种探测办法，当散列表中闲暇地位不多的时候，散列抵触的概率就会大大提高。为了尽可能保障散列表的操作效率，个别状况下，会尽可能保障散列表中有肯定比例的闲暇槽位。用 装载因子（load factor）来示意空位的多少
装载因子的计算公式
散列表的装载因子 = 填入表中的元素个数 / 散列表的长度装载因子越大，阐明闲暇地位越少，抵触越多，散列表的性能会降落
链表法
链表法是一种更加罕用的散列抵触解决办法，相比凋谢寻址法，它比较简单。在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值雷同的元素都放到雷同槽位对应的链表中
当插入的时候，只须要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，所以插入的工夫复杂度是 O(1)。当查找、删除一个元素时，同样通过散列函数计算出对应的槽，而后遍历链表查找或者删除
对于查找和删除操作，工夫复杂度跟链表的长度 k 成正比，也就是 O(k)。对于散列比拟平均的散列函数来说，实践上讲，k=n/m，其中 n 示意散列中数据的个数，m 示意散列表中“槽”的个数
实际
假如咱们有 10 万条 URL 拜访日志，如何依照拜访次数给 URL 排序？
遍历 10 万条数据，以 URL 为 key，拜访次数为 value，存入散列表，同时记录下拜访次数的最大值 K，工夫复杂度 O(N)
如果 K 不是很大，能够应用桶排序，工夫复杂度 O(N)。如果 K 十分大（比方大于 10 万），就应用疾速排序，复杂度 O(NlogN)
因为文章篇幅的起因，代码实现，我放在了 github 上，须要的能够自取（GO 实现）
有两个字符串数组，每个数组大概有 10 万条字符串，如何疾速找出两个数组中雷同的字符串？
以第一个字符串数组构建散列表，key 为字符串，value 为呈现次数。再遍历第二个字符串数组，以字符串为 key 在散列表中查找，如果 value 大于零，阐明存在雷同字符串。工夫复杂度 O(N)
