哈希表
哈希表
---- 清华大学出版社（数据结构 C语言版）251页
哈希函数也就是是一个映像，以达到O（1）时间查找到一个数据。
哈希冲突
如果不同的关键字得到相同的哈希地址，那么就叫做哈希冲突。
具有相同的函数值的关键字对该哈希函数来说称作同义词。
哈希函数的构造方法
- 直接定址法
- 数字分析法
- 平方取中法
- 折叠法
- 除留余数法
- 随机数法
处理哈希冲突的方法
- 开放定址法
Hi = (H(key) + di) MOD m ，i=1,2,3,……,k(k<=m-1)
(1) di=1,2,3,……,m-1 称为线性再散列。(2) di=12,-12,22,-22,……, ±k^2(k<=m/2)称二次探测再散列。
(3)d=伪随机数序列，称为随即探测再散列
- 再哈希法
Hi = RHi(key) i=1,2,3,……,k
RHi 均是不同的哈希函数，即在同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。这种方式不发生聚集，但是时间上有所增加。
- 链地址法
将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函数产生的哈希地址在区间 [0, m-1] 上，则设立一个指针型向量
Chain ChainHash[m]; 其每个分量的初始状态都是空指针。凡哈希地址为i的记录都插入到头指针为ChainHash[i] 的链表中。在链表中的插位置可以在表头或表尾；也可以在中间，以保持同义词在同一线性链表中按关键字有序。
通俗来将：哈希表的每一块都是一个指针，指向一个链表，链表中存数据。
- 建立一个公共溢出区
假设哈希函数的值域为[0, m-1]，则设向量HashTable[0, m-1]为基本表，每一个分量存放一个记录，另设立向量OverTable[0……v]为溢出表。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。
再建立一个额外的空间来存储溢出后的元素。