`
lt200819
  • 浏览: 187481 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

海量数据处理之三:Hash

 
阅读更多

【什么是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直接存入内存,然后进行统计。

转自:http://blog.csdn.net/hit_kongquan/article/details/6255668

分享到:
评论

相关推荐

    海量数据处理策略.pdf

    接着,文章介绍了海量数据处理策略,包括基于散列(Hash)的分布存储方式和迁移方式扩容两种方法。基于散列的分布存储方式是通过对Key进行散列算法,将不同的用户数据分散在不同的数据库节点上,以实现高效的数据...

    海量数据处理方法

    海量数据处理是指基于海量数据上的存储、处理、操作,解决方案包括巧妙的算法搭配适合的数据结构,如 Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie 树,以及大而化小、分而治之的策略。根据数据处理的场景,...

    海量数据处理:十道面试题与十个海量数据处理方法总结

    ### 海量数据处理知识点详解 #### 一、海量数据处理面试题解析 **1、海量日志数据,提取出某日访问百度次数最多的那个IP** - **问题概述**: 给定一天内的海量日志数据,从中找出访问百度次数最多的IP地址。 - **...

    十道海量数据处理面试题

    海量数据处理是互联网公司技术面试中的一个重要环节,它主要考察应聘者处理大规模数据集的能力,以及对各种存储、计算、排序算法的理解和应用。以下针对提供的文件内容,提炼出相关的知识点。 首先,海量数据处理的...

    海量数据处理

    ### 海量数据处理关键技术解析 #### 一、海量数据处理概述 在当前的大数据时代,数据量的急剧增长使得传统的数据处理技术面临着前所未有的挑战。海量数据处理是指在合理的时间内,对大规模数据集进行高效存储、...

    海量数据处理的方法

    ### 海量数据处理的方法详解 #### 一、Bloom Filter **定义**: Bloom Filter是一种高效的数据结构,用于快速判断一个元素是否在一个集合中。它使用位数组和多个哈希函数来实现。虽然Bloom Filter可能会产生误报...

    教你如何迅速秒杀掉:99%的海量数据处理面试题

    【海量数据处理面试题解析】 在信息技术领域,海量数据处理是一项关键能力,尤其在大数据时代,如何高效地处理和分析海量数据成为企业竞争的核心。本文将深入探讨如何应对99%的海量数据处理面试题,提炼出核心策略...

    99%的海量数据处理面试题

    【海量数据处理】是指在面对数据量巨大,超出单机处理能力的情况下,所采用的一系列技术和方法。这类问题通常涉及到存储、处理和操作大量数据,其中“海量”意味着数据量过大,以至于无法在短时间内直接处理或者无法...

    常用大数据量,海量数据处理方法,算法总结

    海量数据处理方法总结 本文总结了常用的海量数据处理方法,包括 Bloom filter、Hashing 和 bit-map 等。这些方法可以用来解决大数据量的问题,例如数据字典、判重、集合求交集等问题。 Bloom Filter Bloom filter...

    海量数据处理面试题.pdf

    在当前的大数据时代,海量数据处理技术已成为IT行业的重要技术之一。面试中,关于海量数据处理的问题往往占据着举足轻重的地位,特别是在涉及秒杀系统、高并发处理和多线程应用的场景中。本文件《海量数据处理面试题...

    大数据量,海量数据 处理方法总结

    ### 大数据量,海量数据处理方法总结 在IT领域,特别是大数据分析、数据库管理和算法设计方面,处理海量数据的能力是至关重要的技能之一。本文旨在总结处理大数据量、海量数据的有效方法,涵盖从理论基础到实际应用...

    大数据量,海量数据处理

    大数据量、海量数据处理需要使用各种数据结构和算法来解决,例如Hash表、Trie树、Bloom filter、堆排序等。根据不同的问题,选择合适的数据结构和算法是关键。在解决大数据量、海量数据处理问题时,需要充分考虑数据...

    中等规模海量数据处理实例分析

    在IT行业中,面对中等规模的海量数据处理是一项常见的挑战。在这个实例分析中,我们将探讨如何利用一台普通服务器高效地处理近60亿PV(页面浏览量)的数据。这一问题的核心在于优化数据处理策略,充分利用有限的计算...

    常用大数据量、海量数据处理方法__算法总结.pdf

    大数据与海量数据处理算法总结 在当今数据爆炸的时代,大数据处理是IT行业的一个热点。无论是社交网络、电子商务还是搜索引擎公司,都面临着海量数据的存储、查询和分析问题。为了有效应对这些挑战,研究者们提出了...

    海量数据去重的Hash与BloomFilter,bitmap1

    在IT领域,尤其是在大数据处理和分布式系统中,数据去重是一项关键任务。本文将深入探讨两种常用的技术:哈希和布隆过滤器,以及它们在处理海量数据时的应用。 哈希算法是数据去重的基础,它能够将任意大小的数据...

Global site tag (gtag.js) - Google Analytics