Hash 哈希表和算法思路详解
概述
- 哈希表是一种可以满足快速查找数据结构,时间复杂度接近O(1)。
- 哈希函数是无限集到有限集的映射。
- 处理数据量大,查找效率要求高时推荐使用hash容器。
- 问题:
- 什么情况下考虑使用哈希容器?
- 常用的哈希思路有哪些?
- 评判哈希算法标准有哪些?
- 哈希冲突是如何产生的?如何解决?
- 如何构造一个hash算法?应注意哪些问题?
评判哈希算法标准
- 效率高。
- 映射分布均匀。
基础hash思路
直接寻址法:
取关键字key,使用线性函数 Hash(key) = a * key + b。
数字分析法:
在一个班级里,同龄学生很多。在取学生年龄作为key时,应避免以年份作为key组成部分。
平方取中法:
key取平方,截取中间的几位作为新的key。数学计算的性质乘积中间几位和乘数每一位都有关,充分混合key每一位对生成的哈希值的影响,使映射分布更均匀。
取余法:
Hash(key) = key % m
相乘取整法:
Hash(key) = floor(frac(key * A), m), 0<A<1
- floor 取整,frac 取小数
- 此法避免像除余法中结果对m过于依赖。
随机数法
Hash(key) = rand(key)
- 据我所知C#的object采用此方法,使用元数据中的几位存hash值。
折叠法:
将关键字按固定长度分成几段然后相加。
- 如:Hash(1234,m = 2) = 46。
- 关键字较长时可以考虑使用此方法。
哈希冲突
产生原因
由于哈希函数是无限集到有限集的映射,换而言之,有限集的元素对应n个无限集的元素,哈希碰撞是不可避免的。
解决办法
开放地址法
当关键字key的哈希地址p=H(key)出现冲突时,递归调用p = Hi(p)直到没有冲突。
Hi=(H(key)+di)Hi=(H(key)+di) % m i=1,2,,3....,ni=1,2,,3....,n
- H(key) 为哈希函数
- m 为表长
- di 为增量序列
根据增量序列di的不同,又分为:
- 线性探测:di = 1,2,3,......
- 二次探测: di = ±1^2, ±2^2,.......
- 随机探测: di = random(di,seed)
- random 为 无状态的伪随机发生函数(所谓无状态,即无论多少次调用,random(a) = b不变)
- seed 一个确定不变的随机数种子
链式地址法
结构示意
pos1
pos2 -> val -> val
pos3 -> val
pos4
...
无限集映射到有限集,有限集的每个元素对应一个链表,链表存储无限集映射到有限集的n个元素。
再哈希法
Hi=RHi(key)i=1,2,…,k
递归调用哈希函数序列中的函数,直到没有冲突。
建立公共溢出区法
建立溢出链表,如发生哈希碰撞,则使用溢出链表。
哈希冲突解决方法优缺点分析
开放散列:链式地址法(桶链法)
- 优点:
- 添加删除方便,避免动态调整开销
- 桶链表内存动态分配,减少内存浪费
- 当哈希表size很大时,指针的性能消耗可以忽略
- 缺点:
- 动态分配内存,内存不紧凑,随机访问性差,序列化性能差。
- 对于预先知道所有元素,可以实现没有冲突的完美hash函数,此时效率会远低于封闭散列。
封闭散列:开放地址法,再哈希法 ...
- 优点:
- 内存紧凑,随机访问性能好,序列化性能好。
- 预先知道所有元素e,可以实现完美hash函数,此时效率远高于开放散列。
- 缺点:
- 所有条目数量不能超过数组的长度,扩容/收紧频繁,性能消耗大。
- 碰撞探测消耗性能。
- 当数组长度很大时,有内存浪费。
哈希算法进阶实例分析
这是取自lua5.4的
-- lua 5.4
unsigned int luaS_hash (const char *str, size_t l, unsigned int seed,
size_t step) {
unsigned int h = seed ^ cast_uint(l);
for (; l >= step; l -= step)
h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1]));
return h;
}
#define lmod(s,size) \
(check_exp((size&(size-1))==0, (cast_int((s) & ((size)-1)))))
(h << 5) + (h >> 2)
= (((h << 5) << 2) + ((h >> 2) << 2) >> 2)
= ((h << 7) + h) >> 2
= (129 * h) >> 2
和伪随机数生成算法一样,要让生成的数尽量随机--二进制数的每一个位取0或1的概率都是50%。
移位,异或运算充分混合每一位的影响,而加法运算引起多个位的反转,使hash值的每一个位更加不可预测,以接近不可逆的单向函数。
(h << 5) + (h >> 2) = (129 * h) >> 2。 乘法可以被拆分为加法和移位的组合(即(h << 7)+h ),以混合哈希值。不过(h << 7 - h) = 127h 会更好些,127是梅森素数(2^n -1)。与线性同余算法(LCG)生成伪随机数一样,梅森素数127,只需一次移位运算和一次加法运算,且不会被分解,随机数分布更加均匀。
- 非素数会被分解成更小的素数的乘积,参与运算时容易被分解,上例中a和c可以提取公因数d,周期 = n = c/d。
a%b = a&(b-1) 当 b = 2^n 时等式成立,lua哈希表的长度保证符合等式成立的条件,lmod使用位运算代替取余运算,效率更高。
算法实际应用详情请参考我的文章
进阶哈希算法
下面是一些进阶哈希算法的思路,需要花费一些时间学习。
最新文章
- Redis 哨兵模式实现主从故障互切换
- tabelView右滑选择进行删除
- 大新闻!HoloLens即将入华商用
- IOS - CORE DATA的目录(xcode6)
- Open source packages on self-driving car
- JavaScript判断文件的大小
- as3资源加载-Loader和URLLoader
- winform属性
- ASP.NET MVC 学习笔记-2.Razor语法
- MFC读写配置ini文件
- 具体解释MVP矩阵之ViewMatrix
- [原]ZolltyMVC框架简介
- 控制台输出 mybatis 中的sql语句
- 一些NLP相关的JD,作参考
- PHP标准库SPL
- 【MVC】View与Control之间数据传递
- Android ContentResolver
- CentOS虚拟机断电或强制关机,再开机出现问题:Entering emergency mode. Exit the shell to continue.
- linux sheel script demo
- 【bzoj3682】Phorni
热门文章
- STM8S103F3P6 开发环境笔记
- java.time包 时间处理类
- OAuth2密码模式已死,最先进的Spring Cloud认证授权方案在这里
- 【FAQ】分析服务导出的事件数据和概览页面展示的数据不一致该如何解决?
- TENSEAL: A LIBRARY FOR ENCRYPTED TENSOR OP- ERATIONS USING HOMOMORPHIC ENCRYPTION 解读
- 【单片机】CH32V103v8t6 - PA5-外部中断测试程序
- Border性质习题与证明
- prop传值
- HTML行内元素与块级元素有哪些及区别详解
- .NET C#基础(4):属性 - 本质是方法