为了解决动态查找的问题
散列查找法的两项基本工作：
- 计算位置：构造散列函数确定关键词存储位置
- 解决冲突：应用某种策略，解决多个关键词位置相同的问题
时间复杂度几乎为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)
分离链接法
- 冲突的关键词存放在同一个单链表中
