用于处理冲突的链式地址法

描述什么是冲突。

由于哈希函数会为一个大整数或字符串的键返回一个较小的数字，两个键可能会产生相同的值。当新添加的键映射到哈希表中一个已经被占用的槽位时，必须使用冲突处理机制来处理这种情况。

对于大表，冲突的频率如何？

即使我们有一个很大的表来存放键，冲突仍然非常普遍。“生日悖论”是一个重要的发现。仅需23人，就有50%的概率会有两个人共享同一个生日。

处理冲突

主要有两种处理冲突的方法

• 链式寻址
• 开放地址法。

本文仅介绍分离链接法。下一篇文章将介绍开放地址法。

链式寻址

通过分离链接法，数组被实现为一个链，即一个链表。分离链接法是处理冲突最流行和最常用的方法之一。

该方法使用链表数据结构实现。因此，当多个元素被哈希到同一个槽位索引时，这些元素会被添加到一个链中，这个链是一个单向链表。在这里，所有哈希到同一槽位索引的条目都会形成一个链表。现在，我们可以用一个键 K，通过简单的线性遍历来搜索这个链表。如果任何条目的内在键等于 K，那么我们就找到了我们的条目。如果我们已经搜索到链表的末尾仍然找不到它，那么该条目就不存在。因此，在分离链接法中，我们得出结论：如果两个不同的条目具有相同的哈希值，我们将它们一个接一个地存储在同一个链表中。

让我们使用“键 mod 7”作为我们简单的哈希函数，键值如下：50, 700, 76, 85, 92, 73, 101。

优点

• 易于实现
• 我们总是可以向链中添加更多元素，因此哈希表永远不会空间不足。
• 对加载因子或哈希函数不太敏感。
• 通常在不清楚键可能被添加或删除的数量或频率时使用。

缺点

• 由于键存储在链表中，链接法的缓存性能较差。而开放地址法将所有内容存储在同一个表中，因此提高了缓存速度。
• 空间浪费（哈希表的某些部分从未使用）
• 在最坏的情况下，随着链变长，搜索时间可能变为O(n)。
• 链接需要额外的空间。

链接法的性能

在假设每个键被哈希到任何表槽位的可能性相等（简单均匀哈希）的前提下，可以评估哈希的性能。

用于存储链的数据结构

• 链表
  • 搜索：O(l)，其中 l = 链表长度
  • 删除：O(l)
  • 插入：O(l)
  • 缓存不友好
• 动态大小的数组（C++ 中的 Vectors, Java 中的 ArrayList, Python 中的 list）
  • 搜索：O(l)，其中 l = 数组长度
  • 删除：O(l)
  • 插入：O(l)
  • 缓存友好
• 自平衡二叉搜索树（AVL 树，红黑树）
  • 搜索：O(log(l))
  • 删除：O(log(l))
  • 插入：O(l)
  • 缓存不友好
  • Java 8 起的 HashMap 使用此方法

总结

• 为了处理冲突，分离链接法将链表与哈希表相结合。
• 该解决方案利用额外的内存来解决问题。
• 哈希表的搜索和删除操作都需要O(n)的时间，其中n是可能哈希到同一空间中的键的数量。
• 当我们想在当前哈希表中添加额外元素或对之前的哈希函数进行再哈希时，我们使用加载因子。