数据结构与算法第六章 集合与字典

第六章 集合与字典

相关名词：散列表、散列函数、闭散列法、线性探查法。

并查集支持两种操作：查找（Find）与合并（Union）

散列表

散列方法：建立存储位置与关键码的对应函数关系\(Hash,Address=Hash(key)\)

按此方法构造的表叫散列表，所用转换函数叫散列函数

散列函数可能造成冲突，这些产生冲突的散列地址相同的不同关键码称为同义词

（1）直接定址法：\(Hash(key)=a*key+b\)

（2）数字分析法：\(n\)个\(d\)位数，每一位可能有种不同的符号，这种不同符号在各位上出现频率不一定相同，据散列表大小，选取其中各种符号分布均匀的若干位作为散列地址。

各位数字中符号分布均匀度\(\displaystyle \lambda_k=\sum_{i=1}^{r}(\alpha_i^k-\frac{n}{r})^2\)，其中\(\alpha_i^k\)表示第\(i\)个符号在第\(k\)位上出现的次数，\(\displaystyle \frac{n}{r}\)表示各种符号在\(n\)个数中均匀出现的期望值。

（3）除留余数法：散列表中允许地址数为\(m\)，取一个不大于\(m\)，且最接近或等于\(m\)的质数\(p\)作为除数，按以下散列函数转换：

\(Hash(key)=key\%p(p\le m)\)

（4）平方取中法：计算构成关键码的标识符内码（数字）的平方，按照散列表大小取中间若干位作为散列地址。

---

处理冲突的闭散列方法：线性探查法

重点：计算散列函数/选用冲突处理方案填写哈希表，并计算搜索成功/失败的平均搜索长度

处理冲突的开散列方法：链地址法

相同地址的关键码归于同一子集，每一个子集称为一个桶，各桶中表项通过单链表链接，称为同义词子表。

搜索成功/不成功的平均搜索长度：按照桶查找次数计算

搜索速度快得多。

例如：对某表项关键码\(\text{Burke, Ekers, Broad, Blum, Attlee, Alton, Hecht, Ederly}\)，散列函数为\(Hash(x)=ord(x)-ord('A')\)

此时\(\displaystyle ASL_{suc}=\frac{13}{8},ASL_{unsuc}=\frac{34}{26}\)

通常每个桶的同义词子表都很短，设\(n\)个关键码处存到散列表的\(m\)个桶中，以搜索平均长度为\(\displaystyle \frac{n}{m}\)的同义词词表代替搜索长度为\(n\)的顺序表，速度快得多。