哈希表
散列表(Hash Table),又称哈希表。是一种数据结构,特点是:数据元素的关键字与其存储地址直接相关,通过“散列函数(哈希函数)”:Addr=H(key)。
若不同的关键字通过散列函数映射到同一个值,则称它们为“同义词”
通过散列函数确定的位置已经存放了其他元素,则称这种情况为“冲突”
常见的散列函数
- 除留余数法——H(key)=key%p,散列表表长为m,取一个不大于m但最接近或等于m的质数p
- 直接定址法——H(key)=key 或H(key)=a∗key+b,其中,a和b是常数。这种方法计算最简单,且不会产生冲突。它适合关键字的分布基本连续的情况,若关键字分布不连续,空位较多,则会造成存储空间的浪费。
- 数字分析法——选取数码分布较为均匀的若干位作为散列地址,如手机号码。
- 平方取中法——取关键字的平方值的中间几位作为散列地址。具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系,因此使得散列地址分布比较均匀,适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。如身份证号。
解决冲突
- 拉链法:把所有“同义词”存储在一个链表中,Java中的HashMap、HashSet
- 开放定址法:可存放新表项的空闲地址既向它的同义词表项开放,又向它的非同义词表项开放。其数学递推公式为:Hi=(H(key)+di)%m,i=0,1,2,…,k(k⩽m−1),其中m表示散列表表长;di为增量序列;i可理解为“第i次发生冲突”
- 线性探测法:di=0,1,2,3,…,m−1; 即发生冲突时,每次往后探测相邻的下一个单元是否为空
- 线性探测法很容易造成同义词、非同义词的“聚集(堆积)”现象,严重影响查找效率
- 产生原因——冲突后再探测一定是放在某个连续的位置
- 平方探测法:当 di=02,12,−12,22,−22,…,k2,−k2 时,称为平方探测法,又称二次探测法其中 k≤m/2
- 比起线性探测法更不易产生“聚集(堆积)”问题
- 散列表长度m必须是一个可以表示成4j+3的素数,才能探测到所有位置
- 伪随机序列法:di 是一个伪随机序列,如 di=0,5,24,11,…
- 再散列法:除了原始的散列函数H(key)之外,多准备几个散列函数,当散列函数冲突时,用下一个散列函数计算一个新地址,直到不冲突为止:Hi=RHi(Key)i=1,2,3….,k
STL
- 无序集合:unordered_set
- 无序字典:unordered_map
练习
- 洛谷——P4305 [JLOI2011]不重复数字:需要加快读
- leetcode-1 两数之和 (简单)