对于双重哈希，如果与第一个哈希函数发生冲突，您将使用第二个哈希函数，但如果仍然存在冲突呢？例如，假设哈希表的大小为15，哈希函数为(key + 3) % 15，第二个哈希函数为((key % 8) / 3) + 2。假设“insert59”通过第一个散列函数转到索引2，但那里已经有一个键。第二个散列函数将使它变为3，但假设那里已经有一个值。59会被插入到哈希表的哪里，为什么？谢啦，谢啦我特别想使用双哈希，而不是链式哈希或线性探测。
(key + 3) % 15
((key % 8) / 3) + 2
wsewodh21#
这不是我们计算第二个散列函数的方式，因为对于每个探测（插槽不可用），您需要有一个新的散列函数，这是不可行的。通用第二哈希函数的类型为，H1（x）-第一哈希函数，H2（x）-第二哈希函数第一次尝试跟随槽- H1（x）时，下一个探针将是- H1（x）+H2（x），下一个探头H1（x）+2 × H2（x）........ H1（x）+n*H2（x）
edqdpe6u2#
第二个散列函数本身并不计算新的索引，而是使用两个函数的组合，使用冲突数-- i。假设有H1(k)和H2(k)，则组合为
-- i
H1(k)
H2(k)
H = (H1(k) + i*H2(k))%n
字符串然后我们继续递增i。
i
dohp0rv53#
这是特定于实现的，但通常您会使用链表或其他灵活的数据结构来管理冲突数据。在java.util.HashMap javadoc中：它使用哈希桶方法;也就是说，通过将新节点与预先存在的节点（或节点列表）相链接来处理散列冲突。通过这种方式，避免了诸如线性探测（这可能导致主聚类）和重散列（这不太适合Java的预计算散列代码的方法）之类的技术。在理想情况下（没有冲突），HashMap在大多数操作上提供O（1）的性能（当然，containsValue()是O（n））。在最坏的情况下（所有键都Map到相同的哈希码--非常不可能），大多数操作都是O（n）。
containsValue()
3条答案
按热度按时间wsewodh21#
这不是我们计算第二个散列函数的方式，因为对于每个探测（插槽不可用），您需要有一个新的散列函数，这是不可行的。
通用第二哈希函数的类型为，
H1（x）-第一哈希函数，H2（x）-第二哈希函数
第一次尝试跟随槽- H1（x）时，
下一个探针将是- H1（x）+H2（x），
下一个探头H1（x）+2 × H2（x）........ H1（x）+n*H2（x）
edqdpe6u2#
第二个散列函数本身并不计算新的索引，而是使用两个函数的组合，使用冲突数
-- i。假设有H1(k)和H2(k)，则组合为字符串
然后我们继续递增
i。dohp0rv53#
这是特定于实现的，但通常您会使用链表或其他灵活的数据结构来管理冲突数据。
在java.util.HashMap javadoc中：
它使用哈希桶方法;也就是说，通过将新节点与预先存在的节点（或节点列表）相链接来处理散列冲突。通过这种方式，避免了诸如线性探测（这可能导致主聚类）和重散列（这不太适合Java的预计算散列代码的方法）之类的技术。在理想情况下（没有冲突），HashMap在大多数操作上提供O（1）的性能（当然，
containsValue()是O（n））。在最坏的情况下（所有键都Map到相同的哈希码--非常不可能），大多数操作都是O（n）。