1. 前言

哈希表（Hash table）也叫散列表，是通过键直接获取该键对应的值的数据结构。它的使用很广，在很多语言上都出现过它的身影，有的语言将哈希称作字典、列表、映射等，而无论是如何实现或者如何命名，哈希所表示的就是键值对之间映射的关系。

2. 参考资料

以下内容会从下面链接吸取知识总结记录

在通常情况下，哈希函数是将不同键映射到不同的索引上的，当键值的数量远大于映射的范围时，就会出现冲突

开放寻址法是解决哈希冲突的一种办法，当哈希发生冲突时，从发生冲突的那个位置开始，依次从哈希表中寻找空闲的位置，然后把发生冲突的元素放到该位置。

可以把开放寻址法想象成蹲坑问题，若当前坑位有人，则继续向前寻找坑位，直到找到一个空的坑位，然后就进入蹲坑。

缺点

删除元素的时候不能真的删除，否则会出现查找错误，只能先做标记，直到下个元素插入时才能真正删除

开放地址法写入数据

如果使用开放寻址法来实现哈希表的话，它的底层数据结构就是数组，因为数组长度有限，向哈希表写入 (author, draven) 这个键值对时会从如下的索引开始遍历：

index := hash("author") % array.len

开放寻址法中对性能影响最大的是负载因子,它是数组中元素的数量与数组大小的比值,随着负载因子向 100% 增加，线性探测的平均用时就会逐渐增加，这会影响哈希表的读写性能。一旦表变满整个哈希表甚至会完全失效，这时查找和插入任意元素的时间复杂度都是 O(n) 的，需要遍历数组中的全部元素。

拉链法是哈希表最常见的实现方法，大多数的编程语言都用拉链法实现哈希表，比如go语言的map，它的实现会比开放地址法复杂一点，但平均查找长度会短，用于存储节点的内存是动态申请的，可以节省更多存储空间

实现拉链法一般会使用数组加上链表，拉链法会使用链表数组作为哈希底层的数据结构，我们可以将它看成可以扩展的二维数组。

拉链法写入数据

当我们需要将一个键值对 (Key6, Value6) 写入哈希表时，键值对中的键 Key6 都会先经过一个哈希函数，哈希函数返回的哈希会帮助我们选择一个桶，和开放地址法一样，选择桶的方式是直接对哈希返回的结果取模：

index := hash("Key6") % array.len

在遍历链表的过程中会遇到以下两种情况：

找到键相同的键值对 — 更新键对应的值；

没有找到键相同的键值对 — 在链表的末尾追加新的键值对；