散列|集2（单独链接）

我们强烈建议将下面的帖子作为这篇文章的先决条件。 散列|集1（简介）

什么是碰撞？ 由于散列函数为一个大整数或字符串的键获取一个小数字，因此两个键可能产生相同的值。新插入的密钥映射到哈希表中已被占用的插槽的情况称为冲突，必须使用一些冲突处理技术来处理。

与大桌子发生碰撞的可能性有多大？ 即使我们有大桌子来存放钥匙，也很可能发生碰撞。一个重要的观察结果是 生日悖论 .由于只有23人，两个人生日相同的概率为50%。

如何处理碰撞？ 处理碰撞的方法主要有两种： 1） 分离链 2） 公开寻址 在本文中，只讨论单独的链接。我们将在下一篇文章中讨论公开演讲。

单独链接： 其思想是使哈希表的每个单元格指向具有相同哈希函数值的记录的链表。

让我们考虑一个简单的哈希函数。 按键mod 7 按键顺序为50、700、76、85、92、73、101。

用链式散列的C++程序

优势： 1） 易于实现。 2） 哈希表永远不会填满，我们总是可以向链中添加更多元素。 3） 对哈希函数或加载因子不太敏感。 4） 它主要用于未知插入或删除密钥的数量和频率的情况。

缺点： 1） 链接的缓存性能不佳，因为密钥是使用链表存储的。开放寻址提供了更好的缓存性能，因为所有内容都存储在同一个表中。 2） 浪费空间（哈希表的某些部分从未被使用） 3） 如果链变长，那么在最坏的情况下搜索时间可能变为O（n）。 4） 为链接使用额外的空间。

链接的性能： 可以在假设每个键都有可能被散列到表的任何插槽（简单的统一散列）的情况下评估散列的性能。

 m = Number of slots in hash table n = Number of keys to be inserted in hash table  Load factor α = n/m    Expected time to search = O(1 + α)  Expected time to delete = O(1 + α)Time to insert = O(1) Time complexity of search insert and delete is  O(1) if  α is O(1)

存储链的数据结构：

• 链表
  • 搜索：O（l），其中l=链表的长度
  • 删除：O（l）
  • 插入：O（l）
  • 不友好
• 动态大小数组（C++中的向量，爪哇中的数组，在Python中列出）
  • 搜索：O（l），其中l=数组的长度
  • 删除：O（l）
  • 插入：O（l）
  • 缓存友好
• 自平衡BST（AVL树、红黑树）
  • 搜索：O（日志（l））
  • 删除：O（日志（l））
  • 插入：O（l）
  • 不友好
  • Java8以后的版本将其用于HashMap

下一篇帖子： 用于冲突处理的开放寻址

参考资料： http://courses.csail.mit.edu/6.006/fall09/lecture_notes/lecture05.pdf 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。