哈希表是根据设定的哈希函数及处理冲突的方式,将一系列离散的记录映射到一段有限的、连续的存储空间上。
在哈希表中:
key1 ≠ key2,但是 hash(key1) = hash(key2),这种现象叫冲突,key1 和 key2 是同义词
哈希表本质是一个压缩映像,所以冲突不可避免,只能尽量减少。当哈希表中的记录数与表长的比例(也叫装装载因子)达到一定阈值时,需要对其进行扩容(rehash):
由此可见:
因为哈希表的底层存储结构是顺序存储结构,支持随机存取,所以在忽略冲突的情况下,哈希表的插入和查找的时间复杂度是 O(1)
构造哈希表的过程主要是:
H(key) = key 或者 H(key) = a * key + b
数字分析法
平方取中法
折叠法
除留余数法
取关键字被某个不大于哈希表表长 m 的数 p 除所得的余数作为哈希地址。除留取余法是最常用的构造哈希函数的方法。
H(key) = key MOD p, p <= m
开放寻址法
当关键字 key 对应的哈希地址 H0 发生冲突时,以 H0 为基础产生另一个哈希地址 H1,如果 H1 仍然冲突,再以 H0 为基础产生另一个哈希地址 H2,...,直到找出一个不冲突的哈希地址 Hi。这种方法有一种通用的再散列函数形式:
Hi = (H0 + di) MOD m, i = 1, 2, 3, ..., m - 1
其中,H0 为 hash(key),m 为表长,di 为增量序列。增量序列的取值方式不同,相应的再散列方式也不同,主要有以下四种:
再哈希法
同时构造多个哈希函数,当一个哈希函数产生的哈希地址发生冲突时,使用下一个哈希函数计算哈希地址,直到解决冲突
建立公共溢出区
将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入到溢出表
链地址法
将所有关键字为同义词的记录存储到同一个线性表中,这个线性表叫同义词子表,哈希表中只存储同义词子表的头节点。
查询时,先根据记录的关键字和哈希函数,计算出哈希地址,然后根据哈希地址找到哈希桶,最后再遍历哈希桶。