哈希表的认识

概念

哈希是由键(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元素

哈希表的优点

在哈希表中，可以利用哈希函数快速访问到数组中的目标元素。如果发生哈希冲突，就是用链表进行存储。这样一来，不管数据量多少，我们都能够灵活应对。

哈希表的缺点

如果数组空间太小，使用哈希表的时候很容易发生冲突，线性查找的使用频率也会更高，反过来，如果数组的空间太大，就会造成内存的浪费。因此，使用哈希表时，数组空间大小的指定非常重要。

更多解决冲突的方法

• 开放地址法

这种方法是指当冲突发生时，立刻计算出一个候补地址(数组上的位置)并将数据存去。如果仍然有冲突，便继续计算下一个候补地址，直到有空地址为止。可以通 过多次使用哈希函数或“线性探测法”等方法计算候补地址。

写在最后

• 文中使用的图片源自《我的第一本算法书》，如若侵权，请评论区留言，作者立即删除相关图片。