散列表（hash table）的实现通常称为散列（hashing），指用于以O(1)时间执行插入、删除和查找的技术，但不支持需要排序信息的树操作，比如findMin、findMax以及在线性时间内按顺序打印整个表都不支持
内容
中心数据结构是散列表
- 实现散列表的几种方法
- 分析比较几种方法
- 介绍散列的多种应用
- 比较散列表与二叉查找树
散列函数
基本思想：将每个键(Key)映射到从[0, TableSize)这个范围中的某个数，并且将其放到适当的单元中，这个映射就称为散列函数。
问题：选择一个函数，决定当两个键散列到同一个值的时候（称为**冲突(collision)**应该做什么以及如何确定散列表的大小。
注：一般使表的大小为素数，有助于避免部分冲突问题
装填因子(load factor)
定义散列表的装填因子 λ 为散列表中的元素个数与散列表大小的比值。
分离链接法
将散列到同一个值的所有元素保留到一个链表中。
一般法则：使 λ ≈ 1，控制链表的长度，若 λ > 1 则通过再散列扩充
开放定址法
不用链表存储，实现分配较大空间，称为探测散列表
hi(x) = (hash(x) + f(i)) mod TableSize, f(0) = 0.
一般 λ > 0.5 就要再散列
- 线性探测 f(i) = i
- 平方探测 f(i) = i^2
- 双散列 f(i) = i * hash2(x), hash2(x) = R - (x mod R) 这样的函数会起作用，其中R为小于TableSize的素数
再散列(rehash)
- 只要表到一半就再散列
- 只有插入失败时才再散列
- 途中策略：当表到达某一个装填因子时进行再散列（最优）