哈希表就是散列表(HashTable).
基本思想: 以关键字key为自变量, 使用哈希函数映射到地址集合, 那么根据哈希函数就能直接找到包含该关键字key的集合的存储地址.

• 换句话说到这个存储地址上对应的存储数据里面, 存放了key也存放了value;

哈希函数

哈希函数应该做到: 分布均匀, 有效利用空间, 计算简单;

1. 直接定址
   H(key) = a*key + b
   适用: 较小的关键字集合, 若较大的关键字集合会占用过多地址空间;

2. 数字分析法
   选取关键码上分布比较均匀的若干位数构成Hash地址.
   适用: 已知关键码的概率分布;

3. 平方取中法
   对key进行平方后, 取中间的若干位作为Hash地址.
   适用: 事先不知道关键码的概率分布, 而且关键码位数不是特别大.

4. 取余数
   H(key) = key%p
   p人为选定的, 接近表长且最好为质数, 比如Len(dict) = 2000, p = 1999;
   适用: 事先不知道关键码的概率分布, 简单而且常用;

冲突处理方法

1. 开放定址法: 左右空位;
2. 拉链法: 每个单元往下建立链表 (这是最常用的!)
3. 建立公共溢出区域: 专门设一块区域存放溢出的;