为了能有效地应用HASH查找技术，必须解决的两个问题是[$#

[填空题]

为了能有效地应用HASH查找技术，必须解决的两个问题是1和2。

格雷厄姆在刷题

1、hash 函数；

2、hash 冲突的处理：

开放寻址法：线性寻址和平方寻址（移动距离分别为1和某值的平方）
双重 hash 法：再用一个 hash 函数去第二次散列
拉链法：在冲突的位置拉出一个链表，但是在最坏情况下，会造成 O（N）的结果，因此在 jdk 1.8中，当超过8个数据hash到了同一个地址的时候，会将拉链法转换成红黑树。 8 个数据的来源有两处：第一，log2（8） = 3，超过三层才有转换的必要；第二，根据泊松分布（这和hash函数的选取有关），8个数据在同一个位置的概率低于千万分之一（P=0.00000006），如果真的发生了要转换的情况，一般而言并不是数据的问题，而是hash函数出了问题，那么一定要进行转换了。
布谷鸟函数：两个hash 函数，与双重hash区别在于，这里是用第一个hash函数的值来确定第二个hash函数的参数，相当于f(g(x))。

发表于 2020-12-20 13:44:28 回复(0)