Hash.md

Hash冲突处理

开放定址法 -> 闭散列表

线性探测再散列

$$ H_i = (H(key) + d_i){\ }%\ m {\quad} (d_i = 1, 2, 3, ..., m-1) $$

其中key代表需要计算hash值的关键字，i为计算hash值的次数，$d_i$表示增量序列——即每次hash冲突后新hash值相较原值增长的数值

• 线性探测法会出现非同义词间对同一个hash地址争夺的现象，称为堆积 / 聚集

二次探测再散列

$$ H_i = (H(key) + d_i){\ }%\ m {\quad} (d_i = 1^2, -1^2, 2^2, -2^2, ..., q^2, -q^2{\ }且{\ }q<= m/2) $$

随机探测再散列

$$ H_i = (H(key) + d_i){\ }%\ m {\quad} (d_i 是一个随机数列, i = 1, 2, 3, ..., m-1) $$

再哈希法

$$ H_i = RH_i(key){\quad}(i = 1, 2, 3, ..., k) $$ 需要注意的是$RH_i$均是不同的哈希函数

• 再哈希法不易产生聚集，但增加了计算时间

链地址法 -> 开散列表

将所有关键词为同义词的记录储存在同一线性链表中(同义词子表)。在散列表中储存的是所有同义词子表的头指针。