概念
哈希是由键(key)和值(value)组成的数据。
存储数据
例如，将图中所示数据，存储到哈希表中
- 准备数组：声明长度为5的数组
- 尝试把Joe存进去
- 使用哈希函数(Hash)计算Joe的值，即字符串"Joe"的哈希值。得到的结果是4928
- 将得到的哈希值处以数组的长度5，求得其余数。这样的操作叫"mod运算"。此处mod的运算结果为3
- 将Joe进行mod运算的值作为数组下标，放进数组里。
- 重复上述步骤，即可往哈希表中添加数据、
存储冲突
当元素进行mod运算后，可能会与其他元素的mod值一样，此时数组中已经有其他元素占了这个下标位置，这种存储位置重复了的情况便叫做“冲突”。
使用链表解决冲突问题
遇到存储冲突问题时，可使用链表在已有数据的后面继续存储新的数据，也称之为链地址法
例如，Nell的mod结果为1，此时下标为1的地址中已经有了Sue元素，此时使用链表在Sue后面添加Nell即可。
查询数据
将要查询的key使用哈希函数计算出哈希值，进行mod运算，得出的结果即当前要查询key在数组中的的下标，通过下标访问即可获取存储的元素，取出对应的值。
例如要查询Dan的值
- 对Dan进行mod运算得出值为4，则得之Dan在数组的下标是4
- 取出Dan对应的value值为M
数组中的链表数据查询
将需要查找的key进行mod运算，得到结果后，发现对应下标下的key不一致，然后对不一致的key的链表进行线性查找，得出查找的key，取出value值。
例如，需要查询Ally键对应的value值
- 求出Ally的哈希值，对哈希值进行mod运算，得出值为3
- 对下标为3元素的连败哦进行线性查找，找到Ally元素
哈希表的优点
在哈希表中，可以利用哈希函数快速访问到数组中的目标元素。如果发生哈希冲突，就是用链表进行存储。这样一来，不管数据量多少，我们都能够灵活应对。
哈希表的缺点
如果数组空间太小，使用哈希表的时候很容易发生冲突，线性查找的使用频率也会更高，反过来，如果数组的空间太大，就会造成内存的浪费。因此，使用哈希表时，数组空间大小的指定非常重要。
更多解决冲突的方法
- 开放地址法
这种方法是指当冲突发生时，立刻计算出一个候补地址(数组上的位置)并将数据存去。如果仍然有冲突，便继续计算下一个候补地址，直到有空地址为止。可以通 过多次使用哈希函数或“线性探测法”等方法计算候补地址。
写在最后
- 文中使用的图片源自《我的第一本算法书》，如若侵权，请评论区留言，作者立即删除相关图片。
- 公众号无法外链，如果文中有链接，可点击下方阅读原文查看😊
