http://blog.redfox66.com/post/2010/09/24/mass-data-topic-3-hash.aspx
【什么是Hash】
Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
HASH主要用于信息安全领域中加密算法,它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值. 也可以说,hash就是找到一种数据内容和数据存放地址之间的映射关系。
数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构?答案是肯定的,这就是我们要提起的哈希表,哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法——拉链法,我们可以理解为“链表的数组”,如图:
左边很明显是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。
元素特征转变为数组下标的方法就是散列法。散列法当然不止一种,下面列出三种比较常用的。
1,除法散列法
最直观的一种,上图使用的就是这种散列法,公式:
index = value % 16
学过汇编的都知道,求模数其实是通过一个除法运算得到的,所以叫“除法散列法”。
2,平方散列法
求index是非常频繁的操作,而乘法的运算要比除法来得省时(对现在的CPU来说,估计我们感觉不出来),所以我们考虑把除法换成乘法和一个位移操作。公式:
index = (value * value) >> 28
如果数值分配比较均匀的话这种方法能得到不错的结果,但我上面画的那个图的各个元素的值算出来的index都是0——非常失败。也许你还有个问题,value如果很大,value * value不会溢出吗?答案是会的,但我们这个乘法不关心溢出,因为我们根本不是为了获取相乘结果,而是为了获取index。
3,斐波那契(Fibonacci)散列法
平方散列法的缺点是显而易见的,所以我们能不能找出一个理想的乘数,而不是拿value本身当作乘数呢?答案是肯定的。
1,对于16位整数而言,这个乘数是40503
2,对于32位整数而言,这个乘数是2654435769
3,对于64位整数而言,这个乘数是11400714819323198485
这几个“理想乘数”是如何得出来的呢?这跟一个法则有关,叫黄金分割法则,而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列,如果你还有兴趣,就到网上查找一下“斐波那契数列”等关键字,我数学水平有限,不知道怎么描述清楚为什么,另外斐波那契数列的值居然和太阳系八大行星的轨道半径的比例出奇吻合,很神奇,对么?
对我们常见的32位整数而言,公式:
i ndex = (value * 2654435769) >> 28
如果用这种斐波那契散列法的话,那我上面的图就变成这样了:
很明显,用斐波那契散列法调整之后要比原来的取摸散列法好很多。
【适用范围】
快速查找,删除的基本数据结构,通常需要总数据量可以放入内存。
【基本原理及要点】
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,同时查找两个位置。
【问题实例】
1).海量日志数据,提取出某日访问百度次数最多的那个IP。
IP的数目还是有限的,最多2^32个,所以可以考虑使用hash将ip直接存入内存,然后进行统计。
- 大小: 16.9 KB
- 大小: 18.8 KB
分享到:
相关推荐
MD5值检验工具——hash,还可以检验SHA1和CRC32值,小而精干
常用的海量数据面试笔试题处理方法,hash,trie,红黑树等。
海量数据处理中常用到的技术 1. Bloom Filtering基本的Bloom Filtering支持快速的插入和查找操作,是一种hash表技术。基本的数据结构非常简单,容量为m的位数组,k个hash函数,将输入的n个元素存储在位数组里面。...
背景分布式一致性 hash 算法将哈希空间组织成一个虚拟的圆环,圆环的大小是,最终会得到一个 [0,] 之间的一个无符号整型,这个整数代表服务器的编号;多个服务
算法之一致性hash(csdn)————程序
想挑战百度、腾讯、Google,海量数据处理面试集锦,理论结合具体事例分析!
9应用 8:近水楼台 —— GeoHash(1)
HASH 索引——用C语言实现,让你充分了解DBMS中索引的实现
hash表线性探测再散列,c语言编写,可直接运行
《数据结构与算法分析》课程设计教学任务书 通讯录系统设计: 设计要求 ...contacts.dat —— 数据存储文件(二进制形式) Contacts.cbp ——CodeBlocks工程文件,如有CodeBlocks,可直接打开工程。
大数据常用的处理算法总结,包括hash算法,分治算法,bloom filter,等等
另外,探讨一下Hash算法在海量数据处理方案中的通用性。最后,从源代码出发,具体分析一下Hash算法在MapReduce框架的中的应用。Hash可以通过散列函数将任意长度的输入变成固定长度的输出,也可以将不同的输入映射...
Sybase ASE15中新增的磁盘数据加密功能可以有效地对介质(如磁盘)上的数据进行加密,只有合法的用户才能在数据库管理下,访问到这些数据。Sybase ASE15通过自身的数据库安全机制管理数据的加解密工作,无需修改应用...
一个简单的使用hash来实现从海量IP地址中查询是否存在待查找的IP地址。主要特点有: (1)使用批处理,一键自动编译,处理;可直接运行。 (2)完美的展示了hash在查询中的使用方法。
校验HD5工具1.04版。
海量用户GoRedis(hash)
hash partitioning, list partitioning, interval partitioning, reference partitioning, composite partitioning等,相应的还有分区索引,借助分区技术,数据库设计人员和后期维护管理员解决因海量数据数据部署和...
3维hashin失效准则~复合材料层合板
yxy版c++教程 Hash 浅谈哈希算法(csdn)————程序