“chaos”的算法---之哈希表(HASH)算法详解-阿里云开发者社区

开发者社区> 技术小胖子> 正文

“chaos”的算法---之哈希表(HASH)算法详解

简介:
+关注继续查看

【 声明:版权所有,欢迎转载。  联系信箱:yiluohuanghun@gmail.com】

   在数据查找中我们会想到很多不错的、行之有效的方法,大体分为以下几种,1、对于空间连续的数据采用二分查找法等是比较不错的。2、对于空间不连续的采用排序二叉树也是不错的方法。3、但是对于空间不连续的而且数据量相当大时,如果依然采用上述两种方法显然就有点力不从心了,当然了我们可以采用哈希表查询的方式。哈希表及继承了数组易于定位查找的有点又兼顾了链表易于增删等优点。

什么是Hash:

   Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

   HASH主要用于信息安全领域中加密算法,它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值. 也可以说,hash就是找到一种数据内容和数据存放地址之间的映射关系。

   数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提起的哈希表,哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法——拉链法,我们可以理解为“链表的数组”,如图:

104933537.png

   左边很明显是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。

   元素特征转变为数组下标的方法就是散列法。散列法当然不止一种,下面列出三种

比较常用的:

1,除法散列法

   最直观的一种,上图使用的就是这种散列法,公式:

     index = value % 16

学过汇编的都知道,求模数其实是通过一个除法运算得到的,所以叫“除法散列法”。

2,平方散列法

   求index是非常频繁的操作,而乘法的运算要比除法来得省时(对现在的CPU来说,估计我们感觉不出来),所以我们考虑把除法换成乘法和一个位移操作。公式: index = (value * value) >> 28   (右移,除以2^28。记法:左移变大,是乘。右移变小,是除。)如果数值分配比较均匀的话这种方法能得到不错的结果,但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问题,value如果很大,value * value不会溢出吗?答案是会的,但我们这个乘法不关心溢出,因为我们根本不是为了获取相乘结果,而是为了获取index。

3,斐波那契(Fibonacci)散列法

平方散列法的缺点是显而易见的,所以我们能不能找出一个理想的乘数,而不是拿value本身当作乘数呢?答案是肯定的。

1,对于16位整数而言,这个乘数是40503

2,对于32位整数而言,这个乘数是2654435769

3,对于64位整数而言,这个乘数是11400714819323198485

   这几个“理想乘数”是如何得出来的呢?这跟一个法则有关,叫黄金分割法则,而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列,即如此形式的序列:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 

2584, 4181, 6765, 10946,…。另外,斐波那契数列的值和太阳系八大行星的轨道半

径的比例出奇吻合。

   对我们常见的32位整数而言,公式:

index = (value * 2654435769) >> 28

   如果用这种斐波那契散列法的话,那上面的图就变成这样了:

105501570.png

   很明显,用斐波那契散列法调整之后要比原来的取摸散列法好很多。

适用范围:

   快速查找,删除的基本数据结构,通常需要总数据量可以放入内存。

基本原理及要点:

   hash函数选择,针对字符串,整数,排列,具体相应的hash方法。碰撞处理,一种是open hashing,也称为拉链法;另一种就是closed hashing,也称开地址法,opened addressing。

扩展 :

d-left hashing中的d是多个的意思,我们先简化这个问题,看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半,分别叫做T1和T2,给T1和T2分别配备一个哈希函数,h1和h2。在存储一个新的key时,同 时用两个哈希函数进行计算,得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key]位置和T2中的h2[key]位置,哪一个 位置已经存储的(有碰撞的)key比较多,然后将新key存储在负载少的位置。如果两边一样多,比如两个位置都为空或者都存储了一个key,就把新key 存储在左边的T1子表中,2-left也由此而来。在查找一个key时,必须进行两次hash,同时查找两个位置。







     本文转自 驿落黄昏 51CTO博客,原文链接:http://blog.51cto.com/yiluohuanghun/1258577,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
文件管理命令 | 学习笔记
快速学习文件管理命令。
8 0
文件重定向 | 学习笔记
快速学习文件重定向。
5 0
冬季实战营第一期:从零到一上手玩转云服务器
冬季实战营第一期:从零到一上手玩转云服务器
10 0
Kubernetes + Spring Cloud 集成链路追踪 SkyWalking
分布式系统的应用程序性能监视工具,专为微服务、云原生架构和基于容器(Docker、K8s、Mesos)架构而设计。 提供分布式追踪、服务网格遥测分析、度量聚合和可视化一体化解决方案。
9 0
正则表达式基础 | 学习笔记
快速学习正则表达式基础。
9 0
阿里云无影云电脑,互联网发展史上的重大里程碑!
阿里云最近推出了无影云电脑,冰河作为阿里云的老用户了,也第一时间收到邀请体验这款在互联网发展史上一个里程碑式的产品。今天就给大家分享一下这款互联网发展史上重大里程碑式的产品——阿里云无影云电脑,
17 0
无影云畅享
“无影是阿里云打造的云端一体、安全高效的一站式云上办公空间。无影的云桌面、云应用、应用中心、安全浏览器等一系列的云办公能力,通过流化的技术,提供给终端用户,在算力、安全、成本、敏捷、开放等方面,无影具有超越传统PC的优势。”
11 0
节点表结构 | 学习笔记
快速学习节点表结构。
7 0
21119
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载