散列表的相关概念和内容
散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。
也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。
这个映射函数称做散列函数，存放记录的数组称做散列表。
基本概念
- 关键字为$k$的值存储在$f(k)$的存储位置中，称映射$f$为散列函数，按照这个思想建立的表称为散列表。
- 对不同的关键字可能得到同一散列地址，即$k_1 \neq k_2$，而$f(k_1) = f(k_2)$，这种现象称为冲突（Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。
- 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数，这就使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。
构造散列函数的方法
若采用求余的方法，采用质数可以在一定程度上解决冲突问题。
处理冲突的方法
- 开放定址法
- 避免聚集：
- 单独链表法
- 再散列
Reference
- Computer Science: An Overview, § 9.5 Traditional File Structures.