哈希表是最常用的数据结构之一，对于其用法，大家都非常熟悉，这里详细探讨一下其原理。哈希表的底层实际上是基于数组来存储的，当插入键值对时，并不是直接插入该数组中，而是通过对键进行Hash运算得到Hash值，然后和数组容量取模，得到在数组中的位置后再插入。取值时，先对指定的键求Hash值，再和容量取模得到底层数组中对应的位置，如果指定的键值与存贮的键相匹配，则返回该键值对，如果不匹配，则表示哈希表中没有对应的键值对。这样做的好处是在查找、插入、删除等操作可以做到O(1)，最坏的情况是O(n)，当然这种是最极端的情况，极少遇到。
不管哪门语言，实现一个HashMap的过程均可分为三大步骤：
- 实现一个Hash函数
- 合理解决Hash冲突
- 实现HashMap的操作方法
Hash函数非常重要，一个好的Hash函数不仅性能优越，而且还会让存储于底层数组中的值分配的更加均匀，减少冲突发生。之所以是减少冲突，是因为取Hash的过程，实际上是将输入键（定义域）映射到一个非常小的空间中，所以冲突是无法避免的，能做的只是减少Hash碰撞发生的概率。具体实现时，哈希函数算法可能不同。
这里简单总结一下常用哈希函数生成方法：
哈希表中，哈希函数必须保证它的返回值是对一个表（数组）单元的有效索引。所以，如果关键字K是数字，则最简单的方法是进行取模运算：TSize = sizeof(table)，h(K) = K mod TSize，这里TSize最好取一个素数。
当然这种方法比较受限，因为不是所有的关键字都是数字的情况。
在这种方法中把关键字分割为几个部分（反映了“散列”的真正含义），这些部分组合或折叠在一起，以某种特定的方式进行变换（例如相加），以产生目标地址。折叠法又可分为两种类型：移位折叠和边界折叠。
移位折叠：例如关键字123456789，移位折叠可将关键字分割为三部分123 | 456 | 789，然后把这三部分相加 123 + 456 + 789得到结果1368，再对累加结果进行取模（1368 / TSize）得到哈希值。
边界折叠：与移位折叠思想类似，只不过分割时类似将关键字写在一张纸上，以各部分边界折叠这张纸，然后各部分相加。例如关键字123456789，折叠后为123 | 654 | 789，然后相加取模。
就是将关键字取平方，将平方结果的中间部分作为地址。如果关键字是字符串，就必须预先（比如使用折叠的办法， 字符串中每个字符ASCII码其实就是数值）进行处理以产生数字。例如，关键字是3121，则计算3121 ^ 2 = 9740641，如果TSize=1000，可取中间值406作为哈希值。hash(3121) = 406。
在直接提取法（直接哈希法）中，只使用一部分关键字来计算地址。比如新中国成立每年的人口变化，1949、1950、1951......，就可直接用关键字K减去1949，得到0、1、......。
当然，这种情况比较少见。
就是将关键字K转换为另外一种数字基数。 例如关键字K的十进制数字345，转换为九进制为423，然后对423取模得到哈希值。
当然，哈希函数不止上面讲到的这几种方法，其具体实现有非常多种方法，在Rust及很多语言的实现中，默认选择SipHash哈希算法。
默认情况下，Rust的HashMap使用SipHash哈希算法，其旨在防止哈希表碰撞攻击，同时在各种工作负载上提供合理的性能。虽然 SipHash 在许多情况下表现出竞争优势，但其中一个比其它哈希算法要慢的情况是使用短键，例如整数。这就是为什么 Rust 程序员经常观察到 HashMap 表现不佳的原因。在这些情况下，经常推荐 FNV 哈希，但请注意，它不具备与 SipHash 相同的防碰撞性。
影响Hash碰撞（冲突）发生的除了Hash函数本身意外，底层数组容量也是一个重要原因。很明显，极端情况下如果数组容量为1，哪必然发生碰撞，如果数组容量无限大，哪碰撞的概率非常之低。所以，哈希碰撞还取决于负载因子。负载因子是存储的键值对数目与数组容量的比值，比如数组容量100，当前存贮了90个键值对，负载因子为0.9。负载因子决定了哈希表什么时候扩容，如果负载因子的值太大，说明存储的键值对接近容量，增加碰撞的风险，如果值太小，则浪费空间。
所以，既然冲突无法避免，就必须要有解决Hash冲突的机制方法。
主要有四类处理冲突的方法：
- 外部拉链法（常用）
- 开放定址法（常用）
- 公共溢出区（不常用）
- 再Hash法（不常用）
主要思想是基于数组和链表的组合来解决冲突，桶（Bucket）中不直接存储键值对，每个Bucket都链接一个链表，当发生冲突时，将冲突的键值对插入链表中。外部拉链法的有点在于方法简单，非同义词之间也不会产生聚集现象（相比于开放定址法），并且其空间结构是动态申请的，所以比较适合无法确定表长的情况：缺点是链表指针需要额外的空间，遇到碰撞拒绝服务时会退化为单链表。
同义词：两个元素通过Hash函数得到了相同的索引地址，这两个元素就叫做同义词。
下面是外部拉链法的两种实现方法，主要区别在于桶（Bucket）中是否存储数据。
主要思想是发生冲突时，直接去寻找下一个空的地址，只要底层的表足够大，就总能找到空的地址。这个寻找下一个地址的行为，叫做探测。
因为目前对github中编辑数学公式还没有熟练掌握，下面的数学公式暂时用markdown中数学公式编辑，过后掌握了再进行更改！数学公式部分可参考文档Hash table。
${hash_{i}=(hash(key)+d_{i})\,{\bmod {\,}}m}， i=1,2...k\,(k\leq m-1)$，其中$hash(key)$为哈希函数，$m$为哈希表长，$d_{i}$为增量序列，$i$为已发生冲突的次数。根据增量序列取法的不同有多种探测方法：
$d_{i}=1,2,3...(m-1)$称为线性探测(Linear Probing)；即$d_{i}=i$，或者为其他线性函数。相当于逐个探测存放地址的表，直到查找到一个空单元，把散列地址存放在该空单元。$d_{i}=\pm 1^{2},\pm 2^{2},\pm 3^{2}...\pm k^{2} (k\leq m/2)$称为平方探测(Quadratic Probing)。相对线性探测，相当于发生冲突时探测间隔$ d_{i}=i^{2}$个单元的位置是否为空，如果为空，将地址存放进去。$d_{i}=伪随机数序列$，称为伪随机探测。
下图为线性探测:
这里需要简单说一下线性探测会在表中产生聚集的问题。线性探测比较容易产生数据聚集快，而聚集块越大，它就越可能变得更大，这种情况会破坏哈希表存储和检索数据的性能。如何避免数据聚集块的形成呢？其中一个方法是仔细地选择探查函数，比如平方探测（也不能完全避免，相比线性探测好一些，但平方探测对表空间的要求比较高，如果表空闲位置比较少的话容易出现表中没有位置放了，但其实还是有空位置的）。
主要思想是建立一个独立的公共区，把冲突的键值对都放在其中。
主要思想是有冲突时，换另外一个Hash函数来算Hash值。这种方法的好处是不会产生聚集，代价是会增加计算时间。
具体的过程为：将n个不同哈希函数排成一个序列，当发生冲突时，由RHi确定第i次冲突的地址Hi。即：Hi = RHi(key) i=1,2,...,n，其中RHi为不同哈希函数。
主要是：
- insert
- remove
- get
- contains_key
- ......等等......
其中最重要的是插入、查找、删除这三个操作。
在哈希表上查找的过程与哈希表的构造过程基本一致。查找过程描述如下：
- 给定K值，根据构造表时所用的哈希函数求哈希地址；
- 若此位置无记录，则查找失败，哈希表中没有此项；否则比较关键字，若和给定的关键字相等则成功；若不等，则根据构造表时设定的冲突处理方法计算“下一地址”，重复步骤2；
删除操作，主要麻烦的地方在于解决冲突问题。对外部拉链法，删除一个元素比较简单，直接在该项链表中删除保存该元素的节点即可。而对于其他方法则需要解决冲突问题（除非在少数情况下使用的是理想哈希函数）。以开放定址法中线性探测为例。删除一个元素并不能简单的直接删除，因为直接删除后，其冲突的元素进行查找时会查找不到该元素，因为根据查找算法，第一个哈希地址位置被删除后就会认为该元素不存在，而实际上该元素因发生冲突地址在下一个位置。所以并不能直接删除，解决这个问题的一个办法是删除时将关键字留在表中，并用标记指示它们是无效的元素，那么后来的搜索就不会过早被终止。当插入一个新的关键字时，覆盖掉作为占位标记的无效关键字。而然对于大量的删除和少量的插入这种情况，表会由于已删除的记录过多而超载，从而使搜索时间增加（因为开放定址法在查找时需要测试已删除的记录），因此，表应该在删除的记录达到一定数量后进行清洗，将未删除的记录移入已删除记录占据的单元。没有被这个过程覆盖的单元则将无效元素的标记更改为自由单元。
插入过程类似查找，比较简单，这里不再叙述。
可以看到，哈希表中主要的问题，注意的要点都是解决哈希冲突而引发的各种问题。
下面列一下关于哈希的其他内容，以后需要的时候可以深读。
理想哈希函数非常罕见，它不会有冲突发生。它只适用于少量情况。
比如，在某些情况下数据总体是固定的，哈希函数可以再知道有哪些数据之后再构造出来，这时有可能会构造出理想哈希函数。