引入概念
已知的几种查找方法：
| 查找方法 | 时间复杂度 |
|---|---|
| 顺序查找 | O(N) |
| 二分查找（静态查找） | \(O(log_2N)\) |
| 二叉搜索树 | O(h) h为二叉查找树的高度 |
| 平衡二叉树 | \(O(log_2N)\) |
【问题】如何快速搜索到需要的关键词？如果关键词不方便比较怎么办？
- 查找的本质: 已知对象找位置。
- 有序安排对象：全序、半序
- 直接“算出”对象位置：散列
- 散列查找法的两项基本工作：
- 计算位置：构造散列函数确定关键词存储位置；
- 解决冲突：应用某种策略解决多个关键词位置相同的问题
- 时间复杂度几乎是常量：O(1) ，即查找时间与问题规模无关！
抽象类型表示
类型名称:符号表（SymbolTable）
数据对象集：符号表是“名字(Name)-属性(Attribute)”对的集合。
操作集：Table ∈ SymbolTable，Name ∈ NameType，Attr ∈ AttributeType
-
SymbolTable InitializeTable( int TableSize )：
创建一个长度为TableSize的符号表；
-
Boolean IsIn( SymbolTable Table, NameType Name)：
查找特定的名字Name是否在符号表Table中；
-
AttributeType Find( SymbolTable Table, NameType Name)：
获取Table中指定名字Name对应的属性；
-
SymbolTable Modify(SymbolTable Table, NameType Name, AttributeType Attr)：
将Table中指定名字Name的属性修改为Attr；
-
SymbolTable Insert(SymbolTable Table, NameType Name, AttributeType Attr)：
向Table中插入一个新名字Name及其属性Attr；
-
SymbolTable Delete(SymbolTable Table, NameType Name)：
从Table中删除一个名字Name及其属性。
概念
“散列（Hashing）” 的基本思想是：
-
以关键字key为自变量，通过一个确定的函数 h（散列函数），计算出对应的函数值h(key)，作为数据对象的存储地址。
-
可能不同的关键字会映射到同一个散列地址上， 即h(keyi) = h(keyj)（当keyi ≠keyj），称为“冲突(Collision)”。
----需要某种冲突解决策略
装填因子（Loading Factor）：设散列表空间大小为m，填入表中元素个数是n，则称α＝ n / m为散列表的装填因子
Java 关联
- HashMap
- Hashtable
- 实现了Map接口，是同步的