哈希表（散列表）
散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
散列函数
线程安全的java.util.Hashtable的散列函数是基于除留余数法的方式来计算，其计算代码如下：
1 | Entry<?,?> tab[] = table; // 表存储是采用数组来实现的 |
如果单单只是通过取模来计算映射地址的话，可能会出现冲突问题。
冲突
散列函数可能会把不同的Key值映射到同一个数组下标。
散列函数的要求
- 散列函数的定义域必须包含全部需要存储的Key值，而Value值的范围则依赖于散列表的大小或地址范围。
- 散列函数计算出来的地址应该能等概率、均匀分布在整个地址空间中，从而减少冲突的发生。
- 散列函数应尽量简单，能够在较短时间内计算出任一关键字对应的散列地址。
散列表的构造方法
直接定址法
取关键字或关键字的某个线性函数值为散列地址。
其线性函数可以表示为：Hash(k)=a*k+b（a、b均为常数）。
直接定址法的弊端是，若Key值分布不均衡，Hash(k)计算出来的值也不均衡，会造成空间浪费。
除留余数法
取Key（Java里面是计算Key的hashCode）被某个不大于散列表（HashTable是取其内部table的长度）表长的数p除后所得的余数为散列地址，也就是基于取模运算。
其散列函数公式表示为：Hash(k)=k%p。
p值最好是取最接近或等于表长的质数，这样可以减少冲突（
java.util.Hashtable内部直接使用表长作为p值了）。
数字分析法
假设Key是以r为基的数，并且哈希表中可能出现的Key都是事先知道的，则可取Key的若干数位组成哈希地址。
好比如以下的一组二进制数：
则可只取后面的几位作为散列地址的计算依据或者结果。
只适合Key是已知的集合。