哈希表（Hash table）
哈希表（Hash table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数（Hash function），存放元素的数组称做散列表（Hash table）。
一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名 x 到首字母 F(x) 的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比查找包含所有人电话的电话簿就要快得多。这里使用人名作为关键字（或者说键，Key），“取首字母”是这个例子中散列函数的函数法则 F()，存放首字母的表对应散列表（Hash table）。关键字和函数法则理论上可以任意确定。
哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。
散列函数/哈希函数（Hash Function）
上面已经提到了，将一个元素的键（Key，或者说元素的特征）转换为存放元素的数组（即散列表）中对应下标的函数就是散列函数（Hash Function）。
散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快定位。
而在实际中，元素的键并不一定都是数字，有可能是字符串，还有可能是几个值的组合等，所以我们需要实现自己的散列函数。
整数
直接定址法
取关键字或关键字的某个线性函数值为散列地址。即 hash(k)=k或 hash(k)=ak+b，其中 a，b为常数（这种散列函数叫做自身函数）。
平方取中法
取元素的键平方后的中间几位为哈希地址。
假如有以下关键字序列{421，423，436}，平方之后的结果为{177241，178929，190096}，那么可以取中间的两位数{72，89，00}作为Hash地址。
通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
折叠法
将元素的键拆分成几部分，然后将这几部分组合在一起，以特定的方式进行转化形成Hash地址。
假如知道图书的ISBN号为8903-241-23，可以将address(key)=89+03+24+12+3作为Hash地址。
除留取余法
如果知道Hash表的最大长度为m，可以取不大于m的最大质数p，然后对关键字进行取余运算，address(key)=key%p。
在这里p的选取非常关键，p选择的好的话，能够最大程度地减少冲突，p一般取不大于m的最大质数。
字符串
将字符串作为键的时候，我们也可以将他作为一个大的整数，采用保留除余法。我们可以将组成字符串的每一个字符取值然后进行哈希，比如
public int GetHashCode(string str)
{
char[] s = str.ToCharArray();
int hash = 0;
for (int i = 0; i < s.Length; i++)
{
hash = s[i] + (31 * hash);
}
return hash;
}
上面的哈希值是Horner计算字符串哈希值的方法，公式为:$ h = s[0] · 31^{L–1} + … + s[L – 3] · 31^2 + s[L – 2] · 31^1 + s[L – 1] · 31^0$。
举个例子，比如要获取”call”的哈希值，字符串c对应的unicode为99，a对应的unicode为97，L对应的unicode为108，所以字符串”call”的哈希值为 $3045982 = 99·31^3 + 97·31^2 + 108·31^1 + 108·31^0 = 108 + 31· (108 + 31 · (97 + 31 · (99)))$
如果对每个字符去哈希值可能会比较耗时，所以可以通过间隔取N个字符来获取哈西值来节省时间，比如，可以 获取每8-9个字符来获取哈希值：
public int GetHashCode(string str)
{
char[] s = str.ToCharArray();
int hash = 0;
int skip = Math.Max(1, s.Length / 8);
for (int i = 0; i < s.Length; i+=skip)
{
hash = s[i] + (31 * hash);
}
return hash;
}
但是，对于某些情况，不同的字符串会产生相同的哈希值，这就是所谓的哈希冲突（Hash Collisions），比如下面的四个字符串：
如果我们按照每8个字符取哈希的话，就会得到一样的哈希值。
哈希冲突（Hash Collisions）
哈希冲突（Hash Collisions），也叫做哈希碰撞，意思是两个或者多个 key 映射到了哈希表的同一个位置。
处理哈希冲突的方式有两种：避免和解决，即冲突避免机制（Collision Avoidance）和冲突解决机制（Collision Resolution）。
避免哈希冲突的一个方法就是选择合适的哈希函数。哈希函数中的冲突发生的几率与数据的分布有关。
例如，如果社保号的后 4 位是随即分布的，则使用后 4 位数字比较合适。但如果后 4 位是以员工的出生年份来分配的，则显然出生年份不是均匀分布的，则选择后 4 位会造成大量的冲突。
我们将这种选择合适的哈希函数的方法称为冲突避免机制（Collision Avoidance）。
要知道，无论我们如何选择哈希函数，哈希冲突也不可能完全被避免（只是尽量减少其发生的频率）。因此，在冲突发生后，有很多策略可以实施，这些策略称为冲突解决机制（Collision Resolution）。
Hash表大小的确定
同时，Hash表大小的确定也非常关键，如果Hash表的空间远远大于最后实际存储的记录个数，则造成了很大的空间浪费，如果选取小了的话，则容易造成哈希冲突。
在实际情况中，一般需要根据最终记录存储个数和关键字的分布特点来确定Hash表的大小。还有一种情况时可能事先不知道最终需要存储的记录个数，则需要动态维护Hash表的容量，此时可能需要重新计算Hash地址。
哈希冲突解决机制（Hash Collision Resolution）
为了知道冲突产生的相同散列函数地址所对应的关键字，必须选用另外的散列函数，或者对冲突结果进行处理。而不发生冲突的可能性是非常之小的，所以通常对冲突进行处理。
常用的解决哈希冲突（Hash Collisions）的方法有以下几种：
开放定址法（open addressing）
开放定址法（open addressing） - 线性探查（Linear Probing）
在开放寻址法中，最简单的一种实现就是线性探查（Linear Probing），步骤如下：
- 当插入新的元素时，使用哈希函数在哈希表中定位元素位置；
- 检查哈希表中该位置是否已经存在元素。如果该位置内容为空，则插入并返回，否则转向步骤 3。
- 如果该位置为 i，则检查 i+1 是否为空，如果已被占用，则检查 i+2，依此类推（沿着地址往下探测），直到找到一个内容为空的位置。
线性探查（Linear Probing）方式虽然简单，但并不是解决冲突的最好的策略，因为它会导致同类哈希的聚集（Primary Clustering）。这导致搜索哈希表时，冲突依然存在。
开放定址法（open addressing） - 二次探查（Quadratic Probing）
一种改进的方式为二次探查（Quadratic Probing），即每次检查位置空间的步长为平方倍数。也就是说，如果位置 s 被占用，则首先检查 $s + 1^2$ 处，然后检查$s - 1^2$，$s + 2^2$，$s - 2^2$，$s + 3^2$ 依此类推，而不是象线性探查那样以 s + 1，s + 2 … 方式增长。尽管如此，二次探查同样也会导致同类哈希聚集问题（Secondary Clustering）。
开放定址法（open addressing） - 二度哈希（Rehashing）
另一种改进的开放寻址法称为二度哈希（Rehashing），或称为双重哈希（Double Hashing）。
二度哈希的工作原理如下：
有一个包含一组哈希函数 H1…Hn 的集合。当需要从哈希表中添加或获取元素时，首先使用哈希函数 H1。如果导致冲突，则尝试使用 H2，以此类推，直到 Hn。所有的哈希函数都与 H1 十分相似，不同的是它们选用的乘法因子（multiplicative factor）。
单独链表法（Separate Chaining）
**链接技术（chaining）**将采用额外的数据结构来处理冲突，其将哈希表中每个位置（slot）都映射到了一个链表。当冲突发生时，冲突的元素将被添加到桶（bucket）列表中，而每个桶都包含了一个链表以存储相同哈希的元素。
上图中的哈希表包含了 14 个桶（bucket）。如果一个新的元素要被添加至哈希表中，将会被添加至其 Key 的哈希所对应的桶中。如果在相同位置已经有一个元素存在了，则将会将新元素添加到列表的前面。
使用链接技术添加元素的操作涉及到哈希计算和链表操作，但其仍为常量，渐进时间为 O(1)。而进行查询和删除操作时，其平均时间取决于元素的数量和桶（bucket）的数量。具体的说就是运行时间为 O(n/m)，这里 n 为元素的总数量，m 是桶的数量。但通常对哈希表的实现几乎总是使 n = O(m)，也就是说，元素的总数绝不会超过桶的总数，所以 O(n/m) 也变成了常量 O(1)。
Rehash (Dynamic resizing)
很多语言或者工具包哈希表的内部实现都使用了两个数组，其中一个作为备用。如果当前哈希表的负载因子（元素个数/哈希表容量大小）过大或者过小时，就需要将数据切换到备用数组里面，这个过程就是 rehash。
新的哈希表的大小可以有很多种方案，比如 redis 里面的哈希表（字典的底层实现）扩展时，新的哈希表的大小为大于当前哈希表里面存放元素的 2 倍的最小的 2 的 n 次幂。
Rehash 过程也很有讲究，这个过程不应该影响当前系统的运行，所以比较推崇的一种方法是渐进式 rehash。渐进式 rehash 的主要思想是在 rehash 阶段对于新的写请求，并不会写入老的哈希表里面，而是直接写入到新的哈希表里；对于读请求，优先读取新的哈希表，如果不存在，则去读老的的哈希表同时将这条数据迁移到新的哈希表里面来。
Rehash 有一个问题需要讨论一下：如何鉴定 rehash 阶段的开始与结束？开始很简单，每次写操作或者定期检测一下负载因子，当满足条件则开始 rehash。那么如何鉴定结束呢？一种比较常规的方法是定期检测，但是这涉及到很多问题，比如如何界定检测的时间粒度。另一种是记录下迁移过程。还是以 Redis 为例来说明，Redis 使用的是 1.2 介绍的哈希表元素作为链表头不存储元素的方式，这样数据迁移的时候只需要从原链表将节点删除，然后插入到新的哈希表对应的位置就好了。同时哈希表结构有一个字段记录了老的哈希表残留的数据，这样我们只需要检测这个变量（代价很小）就知道 rehash 有没有完成了。
rehash 过程如下图所示（来自 《Redis 设计与实现》）：
迁移索引 1 和 2 上的过程图略去。
Reference
- https://en.wikipedia.org/wiki/Hash_table
- 小朋友学数据结构：哈希表 - https://www.jianshu.com/p/de33dc676a3f
- 浅谈算法和数据结构: 十一 哈希表 - https://www.cnblogs.com/yangecnu/p/Introduce-Hashtable.html
- 聊一聊哈希表 - http://legendtkl.com/2017/07/23/about-hash-table/