常数级查找算法 – 哈希散列

@创建时间 2019年12月09日 16:39:48
@更新时间 2022年11月04日 09:36:10

哈希函数用查询键值K直接计算为一个数组下标索引，即index = hash(Key)形成了一对一的映射关系，将查找算法简化为O(1)复杂度

散列函数

将N个键值均匀映射到M个位置上
尽可能利用键值信息计算
尽可能随机分散减少冲突

除留余数法

hash = K % M

M一般取素数，增加键值的信息利用

乘基取整法

hash = Math.round(M * K)

也可用二进制除留余数增加信息利用

字符串

int hash = 0;
for(int i = 0; i < s.length(); i++)
    hash = (R * hash + s.charAt(i)) % M;

[BKDR HASH算法]
根据 不同字符 及 字符所在不同位 区分字符串
使用类似进制方式可以很好地将不同字符串分散
取系数R作为进制，字符值作为所在位取值
所得结果取余分散到[0, M - 1]区间

[进制计算转换]
进制的直观计算
hash = Σ R ^ i * s.charAt(i)
递归算法（除k取余法逆用）
hash = R * hash + s.charAt(i)

[余数的加法定理]
(a + b) % c = (a % c + b % c) % c

组合键

hash =  (R * ((R * K0 + K1) % M) + K2) % M

BKDR HASH算法，将所有键值作为位取值编码进来

冲突解决

新插入的元素发现散列位置已有元素时，应安置一个新的存储位置

拉链法

散列位置的首个元素作为链表头，再插入的元素加入链表

开放定址法

从散列位置开始，继续向前后寻找新的位置
$\scriptsize newIndex = (hash(Key) + \Delta) \mod M$

线性探测法

从散列位置开始，按线性增量向后查找，直至找到下个空余位置

int i = 0, Delta = 0, oldIndex = hash(Key) % M;
while(Entry[(oldIndex + Delta) % M] != null)
    Delta = i++;
int newIndex = (oldIndex + Delta) % M;

平方探测法

从散列位置开始，按平方增量向后查找，直至找到下个空余位置

int i = 0, Delta = 0, int oldIndex = hash(Key) % M;
while(Entry[(oldIndex + Delta) % M] != null)
    Delta = i * (i++);
int newIndex = (oldIndex + Delta) % M;

再散列法

引入第二个hash函数，重新确定地址

int Delta = 0, oldIndex = hash(Key) % M;
while(Entry[(oldIndex + Delta) % M] != null)
    Delta = newHash(Key);
newIndex = (oldIndex + Delta) % M;

伪随机数法

引入一个随机生成数，重新确定地址

int Delta = 0, oldIndex = hash(Key) % M;
while(Entry[(oldIndex + Delta) % M] != null)
    Delta = rand();
newIndex = (oldIndex + Delta) % M;