golang之哈希表：散列查找算法

我们要通过一个<code>key</code>来查找相对的<code>value</code>。有一种最简单的方式，就是将键值对存放在链表里，然后遍历链表来查找是否存在<code>key</code>，存在则更新<code>key</code>对应的<code>value</code>，不存在则将<code>key-value</code>链接到链表上。

这种链表查找，最坏的时间复杂度为<code>O(n)</code>

有一种算法叫做散列查找，也称hash查找，是一种空间换时间的查找算法，依赖的数据结构称为哈希表或者散列表：<code>HashTable</code>

散列表（Hash table，也叫哈希表），是根据关键码值(Key
value)而直接进行访问的数据结构。也就是说，它通过dao把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

Hash 算法虽然是一种算法，但更像一种思想，没有一个固定的公式，只要符合这种思想的算法都称 Hash 算法。

散列查找，主要是将<code>key</code>进行<code>hash</code>计算得出一个大整数，然后与数组长度进行取余，这样一个比较大的域空间就只会映射到数组的下标范围，利用数组索引块的特征，用空间换时间的思路，使得查找的速度快于线性查找

首先有一个大数组，每当存一个键值对时，先把键进行哈希，计算出的哈希值是一个整数，使用这个整数对数组长度取余，映射到数组的某个下标，把该键值对存起来，取数据时按同样的步骤进行查找。

有两种方式实现哈希表：线性探测法和拉链法。

当hash冲突不严重的时候，查找某个键，只需要求hash值，然后取余，定位到数组的某个下标即可，时间复杂度为<code>O(1)</code>

当hash冲突十分严重的时候，每个数组元素对应的链表会越来越长，即使定位到数组的某个下标，也要遍历一条很长很长的链表，就退化为查找链表了。时间复杂度为<code>O(n)</code>

所以hash表实现要解决的问题就是寻找相对均匀，具有很好的随机分布性的hash函数。

Golang语言实现的哈希函数参考了以下两种哈希算法：

xxhash:https://code.google.com/p/xxhash
cityhash: https://code.google.com/p/cityhash
当然还有其他哈希算法如MurmurHash:https://code.google.com/p/smhasher。

还有哈希算法如Md4和Md5等。

因为研究均匀随机分布的哈希算法，是属于数学专家们的工作，我们在此不展开了。

我们使用号称计算速度最快的哈希xxhash，我们直接用该库来实现哈希：https://github.com/OneOfOne/xxhash：

输出：

我们已经寻找到了计算较快，且均匀随机分布的哈希算法xxhash了，接下来就需要根据hash值映射到哈希数组了。

拿到哈希值之后，我们要将这个值映射到数组的某一个空间，也就是进行数组寻址。如果数组的长度为len，那么<code>index = xxhash(key) % len</code>。

可以看出，不管是从初始化哈希数组还是根据值映射哈希数组，我们都需要先确定哈希数组的长度，那么数组的长度应该如何选择？

引出此问题，是看到一篇有关jdk中HashMap和Hashtable对于hash算法的选择。

1、位运算(&)比模运算(%)效率高很多，原因是位运算直接对内存数据进行操作，不需要像模运算一样转成十进制，因此处理速度快。

2、<code>HashMap</code>中对key求完hash值，在进行数组寻址时，使用的方法是位运算（代替的取模运算）。公式如下：

3、<code>HashMap</code>我们一般选择2^x作为hash数组的长度, 是因为我们可以使用&代替%来进行数组寻址

4、<code>Hashtable</code>中求完hash值，在进行数组寻址时，使用的取模运算

来自

https://www.jianshu.com/p/e4cbe8c545cf

https://www.cnblogs.com/nima/p/12724872.html
https://www.cnblogs.com/itbsl/p/10600110.html