（20200813修改）
- 散列表（哈希表）
基本概念：
散列函数：可由关键字得到散列地址的函数；
散列地址：数据存储的地址
散列表：一个有限连续的地址空间，通常是一维数组，数组的下标是散列地址，存储的是数据
(1) 构造散列函数的方法
① 数字分析法：将关键字列出进行比较，舍去无变化或变化很小的几位，留下随机变化的几位作散列地址；比如同一书店的ISBN的前几位都一样，那就将前几位舍去，只保留后几位。
② 平方取中法：key值平方后取中间几个数，因为中间几个数与数的每一位都相关。
③ 折叠法：
概念：将关键字分割成长度相同的几部分，允许最后一部分长度不够，将各部分叠加，舍去进位，得到散列地址。
1) 移位叠加：每一次取数是按顺序取数。比如：75315948623（按3位分割），分割的各部分为：753,159,486,23。
2) 边界叠加：取数是按顺序和逆序交替取数。比如：75315948623（按3位分割），分割的各部分为：753,951,486,32。
④ 除留取余法（最简单，最常用）
概念：选一个不大于散列表表长的数m，将key是对m取余（key%m）得到散列地址
注：实际应用可以是前三种方法和第四种的组合
(2) 处理冲突的方法
① 开放地址法
1) 线性探测法：1,2,3,4,5,6
2) 二次探测法：1^2,-1^2,2^2,-2^2,3^2,-3^2
3) 伪随机法：产生一个伪随机数进行相加
② 链地址法：相同散列地址的记录放在同一个单链表中，数组存放链表的头指针
(3) 散列表的查找
① 开放地址法的线性探测法会有二次聚集现象发生，例如当i,i+1,i+2位置都存了记录时，当这三个地址发生冲突时都会竞争i+3这个位置
② 装填因子(α)=表中填入的记录数/散列表的长度