Java 中的开散法和闭散法

在本文中，我们将学习 Java 编程语言中的开放寻址哈希和封闭寻址哈希。阅读完本文，我们将涵盖该主题的不同部分，例如这些技术在 Java 编程语言中的用途，使用这些技术的优缺点以及开放寻址哈希和封闭寻址哈希之间的区别。

冲突处理技术

如果两个数据在哈希表中具有相同的值，则称为哈希中的冲突。由于哈希函数的键对于整数或字符串是较小的数字，因此两个键很可能产生相同的值。因此，冲突也称为新插入的键映射到哈希表中已占用位置的情况。这些冲突使用称为冲突处理技术的不同技术进行处理。这些技术也称为冲突解决技术。

用于处理或解决冲突的技术主要分为两类。它们是

• 开放寻址哈希（或）拉链法
• 封闭寻址哈希（或）开放寻址

开放寻址哈希

第一种冲突解决或处理技术“开放寻址哈希”俗称拉链法。这是一种用于将数组实现为链表的技术，称为链。它是程序员处理冲突最常用的技术之一。基本上，链表数据结构用于实现拉链法。当许多元素被散列到单个槽的索引时，它们会被插入到单链表中。这个单链表就是我们在开放寻址哈希技术中提到的链。

我们可以使用键“K”通过线性遍历来搜索链。如果键 K 和单链表中任何条目的内部键相等，则表示我们找到了条目。但是，如果我们遍历单链表并在不找到条目的情况下到达末尾，则表示我们要查找的条目不存在。

因此，当有两个键争夺同一个键位置时，这两个键或记录将被分配到同一个键位置。在用链表放置一个键后，键位置会进一步扩展。最后，哈希表将包含发生冲突的链。这就是称此技术为“链式技术”的主要原因。

开放寻址哈希的优点

1. 拉链法易于实现和理解。
2. 哈希表永远不会满，所以我们可以一直添加新元素。
3. 开放寻址哈希对负载因子或哈希函数不太敏感。
4. 当不知道键的插入或删除频率时，可以使用它。

开放寻址哈希的缺点

1. 拉链法的缓存性能较差，因为键是使用单链表存储的。
2. 浪费了很多存储空间，因为哈希表的某些部分从未被使用。
3. 在最坏的情况下，搜索时间可以达到“O(n)”。这仅发生在链变得过长时。
4. 存储链的链接需要额外的存储空间。

开放寻址哈希中使用的数据结构

1. ArrayList
   • 搜索：O(l)，其中 l 是数组的长度。
   • 删除：O(l)
   • 插入：O(l)
   • 它是缓存友好的
2. 链表
   • 搜索：O(l)，其中 l 是链表的长度。
   • 删除：O(l)
   • 插入：O(l)
   • 它不是缓存友好的。
3. 自平衡二叉搜索树
   • 搜索：O(log(l))，其中 l 是链表的长度。
   • 删除：O(log(l))
   • 插入：O(l)
   • 它不是缓存友好的。
   • Java 8 以来一直用于 HashMap。

实现开放寻址哈希的程序

输出

3
4
null
2
false

开放寻址哈希中嵌入了不同的函数，用于在上述程序中实现拉链法。让我们看看这些函数是什么以及它们如何用于开放寻址哈希过程。

开放寻址哈希中使用的函数

1. get(K key)：如果键存在于 HT 中，get(K key) 返回与键对应的（哈希表）值。
2. getSize()：它将返回哈希表的大小。
3. add()：如果键值对已存在，则更改 HT 中现有的有效键值对，然后再添加新键值对。
4. remove()：remove 函数将删除键和值对。
5. isEmpty()：如果大小为零，它将返回值“True”。

现在，我们将看到这些函数的详细实现，以便更好地理解和描绘程序。

函数实现

1. get()：get() 函数只需接受一个键作为输入，如果键在表中可用，则返回匹配的值；否则，返回 null。get() 函数实现步骤如下
   • 要定位 HT 中的索引，请获取输入键。
   • 如果在未返回的情况下完全遍历列表，则表示表中不存在该值且无法获取，因此返回 null。遍历与 HT 对应的链表。
2. remove()
   • 使用辅助函数检索与输入键对应的索引。
   • 与 get() 遍历链表的方式类似，此方法除了查找键之外还需要删除键，这会产生两种情况。
   • 如果必须删除的键位于链表的头部。
   • 如果必须删除的键不在头部，而在其他位置。
3. add()：add() 函数是整个执行中最有趣和最困难的部分。它很有趣，因为当负载因子超过我们设定的数字时，我们必须动态扩展列表的大小。
   • 与添加和减去步骤直到遍历一样，两种情况（头部位置的添加或非头部位置的添加）没有改变。
   • 如果负载因子在最后大于 0.7，我们将列表的大小增加两倍，然后递归地对已存在的键使用 add() 方法，因为数组的大小用于压缩我们场景中的内部 JVM 哈希码，并且我们必须获取已存在的键的新索引。

注意：如果“n”是我们最初打算填充的链中单元格的总数，例如 10，并且其中 7 个单元格现在已填满，则负载因子为 7/10，即 0.7。

因此，这就是用于在哈希表中解决冲突的开放寻址哈希技术。现在，让我们看看并理解封闭寻址哈希技术。

封闭寻址哈希

第二种冲突解决技术，封闭寻址哈希，是一种处理冲突的方式，类似于拉链法。在开放寻址中，哈希表本身存储所有元素。表的大小始终应大于或等于键的总数（我们也可以在需要时通过复制已存在的旧数据来增加表的大小）。此机制称为封闭寻址哈希。整个过程的形成和考虑是探测。

封闭寻址哈希中使用的函数

1. Insert( k )：不断探测，直到找到一个空格。将键“k”放置在找到的第一个空槽中。
2. Search( k )：探测每个槽，直到键不等于 k 或直到找到一个空槽。
3. Delete( k )：删除东西很有趣。当我们仅删除一个键然后执行搜索操作时，搜索可能会失败。属于已删除键槽的槽被视为“已删除”。

执行封闭寻址哈希的几种技术

1. 线性探测：在线性探测中，哈希表从哈希的初始或起始点开始进行清晰整洁的检查。如果计算后得到的槽已被占用，则我们应寻找不同的槽。负责执行重新哈希的函数是“key = rehash(n+1)%table-size”。两个探测或位置之间的空间通常为 1。

让我们来看一下线性探测，对于槽索引“hash(a)”，它使用哈希函数进行计算。它是具有最佳缓存性能的最佳技术之一。

线性探测遇到的困难

• 主聚集：主聚集是线性探测技术引起的主要问题之一。许多相邻的元素通常会形成簇或分散的组，这反过来使得哈希表更难找到空槽或搜索元素。
• 次聚集：次聚集不像主聚集那么严重，并且必须放置在同一位置的元素或记录仅允许共享一个冲突链（也称为探测序列），如果它们从同一位置开始。
• 聚集是线性探测中唯一的问题。如果在此机制中可以减少聚集，那么它就可以被认为是最佳的冲突解决技术之一。

2. 二次探测：在二次探测中，与线性探测相比，当哈希函数不同时，键位置之间的间隔会增加。通过使用二次探测技术可以轻松解决上述技术中由聚集引起的问题。此技术也称为中平方方法。当当前运行的迭代为“i”时，则 i^2 的位置被视为该键的键位置。只有当我们尝试的键位置已被占用时，才会检查其他位置的槽。这是具有封闭特性的哈希表最有效和最高效的方法。它具有平均缓存性能，但存在轻微的聚集问题。

二次探测遇到的困难

它处理次聚集，有时两个键具有相同的探测序列，只要它们具有相同的键位置。

3. 双重散列

在此解决技术中，使用另一个哈希函数，该函数是专门为双重散列机制创建的。在此技术中，有效地处理并进一步减少了键之间形成的聚集。键位置的增量由将在此机制中使用的函数确定。使用该函数，根据其键计算键位置，并相应地放置它们。然后将函数与变量“i”相乘，然后执行模运算。

双重散列中的困难

与其他技术相比，双重散列的缓存性能较差，但没有聚集问题。由于需要执行两个哈希函数，因此完成整个过程所需的时间更长。因此，这会导致缓存性能不佳。除此之外，双重散列没有问题。

实现封闭寻址哈希的程序

输出

The key 246 is not found in the hash table. It has done 20 step sizes.
The key 246 is not removed as the element does not exist in a hash table.

开放寻址哈希和封闭寻址哈希概述

开放寻址哈希主要用于避免实现中的复杂性并以简单的方式完成工作，而封闭寻址哈希则涉及更多的复杂性和计算。开放寻址哈希对可以插入的元素、键或记录没有大纲或边界。当使用开放寻址哈希时，可以无限制地输入记录。封闭寻址哈希受到一些有限记录的约束，其中一些记录可能没有足够的键位置供其输入。在开放寻址哈希中，会创建额外的存储空间，而不管表的大小如何。这种存储用于发生冲突的情况。封闭寻址哈希中不执行此类型的机制，因为整个表是记录放置的唯一来源，并且不添加外部存储。