独立的碰撞处理链

描述碰撞。

两个键可能提供相同的值，因为对于一个大整数或字符串的键，散列函数返回一个小数字。必须使用冲突处理机制来处理新添加的键映射到已被占用的散列表槽的情况。

与大表碰撞的频率是多少?

即使我们有一个大的表来存放键，碰撞仍然非常频繁。生日悖论是一个重要的发现。在只有23个人的情况下，两个人同一天生日的概率是50%。

处理碰撞

主要有两种处理碰撞的方法:

• 单独的链接
• 打开地址。

本文只提到独立链。下面的文章将介绍开放寻址。

独立的链接:

使用单独的链，数组被实现为链，这是一个链表。处理事故最流行和最常用的方法之一是单独锚链。

该方法是使用链表数据结构实现的。因此，当许多元素被散列到同一个槽索引中时，这些元素被添加到一个链中，这是一个单链表。这里，用散列到相同槽索引的所有条目创建一个链表。现在，仅仅使用线性遍历，我们就可以用键K来搜索链表。如果任何项的内在键等于K，那么我们就确定了我们的项。如果我们一直搜索到链表的末尾，仍然找不到它，那么这个条目就不存在。因此，在单独的链接中，我们得出结论，如果两个不同的条目具有相同的哈希值，我们将它们依次存储在同一个链表中。

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

优点:

• 易于实现
• 我们总是可以向链中添加更多的元素，因此哈希表永远不会耗尽空间。
• 不太容易受到负载因素或哈希函数的影响。
• 当不清楚添加或删除键的数量或频率时，通常使用它。

缺点:

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

链接性能:

在每个键被散列到任何表槽的可能性相等的前提下，可以评估散列的性能(简单统一散列)。

存储链的数据结构:

• 链表
  • 搜索:O(l)，其中l =链表的长度
  • 删除:O(左)
  • 插入:O(左)
  • 不支持缓存
• 动态大小数组(c++中的vector, Java中的ArrayList, Python中的list)
  • 搜索:0 (l)，其中l =数组的长度
  • 删除:O(左)
  • 插入:O(左)
  • 缓存友好
• 自平衡BST (AVL树，红黑树)
  • 搜索:O (log (l))
  • 删除:O (log (l))
  • 插入:O(左)
  • 不支持缓存
  • Java 8以后将此用于HashMap

总结

• 为了处理冲突，分离链接技术将链表与散列表结合起来。
• 为了解决这个问题，这个解决方案利用了更多的RAM。
• 哈希表的搜索和删除操作都需要O(n)的时间，其中n是同一空间中可以包含的键的数量。
• 当我们想要向当前哈希表添加额外的元素或重新哈希前一个哈希函数时，我们使用负载因子。