数据结构笔记（散列查找->散列表）

为了解决动态查找的问题
散列查找法的两项基本工作：

• 计算位置：构造散列函数确定关键词存储位置
• 解决冲突：应用某种策略，解决多个关键词位置相同的问题
  时间复杂度几乎为O(1)

散列表（哈希表）

• 类型名称：符号表（SymbolTable）
• 数据对象集：符号表是”名字(Name)-属性(Attribute)“对的集合
• 装填因子：散列表大小/填入散列表元素的个数

散列函数

数字关键词的散列函数构造

• 直接定址法
  h(key) = a * key + b
• 除留余数法
  h(key) = key % p（p = Tablesize，一般取素数）
• 数字分析法
  取比较随机的几位数字组成散列地址
• 折叠法
  把关键词分成位数相同的几个部分，然后叠加
• 平方取中法
  大数平方，取中间几位作为地址

字符关键词的散列函数构造

• ASCII码加和法
  h(key) = 每个字符ASCII码加和 mode Tablesize
• 前三个字符移位法
  h(key) = (key[0] * 27 ^ 2 + key[1] * 27 ^ 1 + key[2] * 27 ^ 0)mod Tablesize
• 移位法

散列表查找性能分析

• 成功平均查找长度（ASLs）
• 不成功平均查找长度（ASLu）

影响散列表性能因素

• 散列函数是否均匀
• 处理冲突的方法
• 散列表的装填因子α

再散列

• 当装填因子过大，查找效率下降，装填因子最好在0.5-0.85之间
• 解决的方法是加倍扩大散列表，即再散列（Rehashing）

处理冲突的方法

开放地址法（Open Addressing）

hi(key) = (h(key) + di) mod Tablesize

• 线性探测 di = i
• 平方探测 di = ±i^2（如果表的大小设计为4k+3形式的素数，平方探测法可以探测到整个散列表空间）
• 双散列 di = i*h2(key)

分离链接法

• 冲突的关键词存放在同一个单链表中