`

海量数据处理专题(三)——Hash

阅读更多
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
分享到:
评论

相关推荐

    经典面试题——海量数据库

    以上技术在大数据场景下尤其重要,它们能够在有限的内存资源下处理海量数据,提供高效且节省空间的解决方案。理解和熟练运用这些数据结构和算法是IT专业人员必备的技能。在实际应用中,可以根据具体需求和资源限制...

    SQL数据库对于海量数据面试题及答案.pdf

    "SQL数据库对于海量数据面试题及答案" 本文整理和大家分享一些SQL 数据库对于海量数据面试题及答案给大家,很不错哦,喜欢请收藏一下。 问题 1:找出 a、b 两个文件共同的url 给定 a、b 两个文件,各存放50 亿个 ...

    基于序列密码的GIS矢量数据层次加解密方法

    该方法旨在有效提升GIS矢量数据在保持海量数据处理能力的同时,实现数据的高效快速传输和安全访问。 首先,该方法集成了序列密码与LOD(Level of Detail)技术。序列密码是一种加密技术,它通过产生一个密钥序列来...

    redis分布式 —— 客户端库tinyredis1

    在形态2的基础上,形态3引入了节点容错、数据备份、海量存储以及异地多活等特性,形成了分布式缓存(存储)系统。这个系统通常包含Master集群和存储服务两部分。Master集群负责选举主服务器,监控存储服务的健康状况...

    43源码 11:见缝插针 —— 探索 HyperLogLog 内部(1).md

    HyperLogLog是一种用于计算海量数据中不重复元素个数的近似算法。它在处理大数据时,能够提供高效率与低内存消耗的解决方案。在介绍HyperLogLog时,我们通常会讨论以下几个核心知识点: 1. **基本原理**:...

    分布式关系数据库金融行业创新实践.pptx

    在当今的数字化时代,金融行业面临着海量数据处理和高可用性的挑战。传统的单机数据库已无法满足需求,分布式关系数据库应运而生。其中,TiDB作为一款快速崛起的新一代分布式关系数据库,以其独特的特性在金融行业中...

    Greenplum主要特性介绍.pdf

    这种设计可以提高数据处理速度,使得在处理大数据时能提供高吞吐量。 Greenplum支持在多种计算环境中部署,包括X86物理机、私有云和公有云。它允许用户使用内置的SAS磁盘来存储数据,这种存储方式可以使得数据均匀...

    Redis 实践

    通过合理的数据结构选择和精细的内存管理,即使是面对海量数据的挑战,也能够实现资源的高效利用,提升整体系统的性能与稳定性。在未来的实践中,不断探索和优化,将是每个技术团队的永恒课题。

    Python库 | tencentcloud-sdk-python-tcaplusdb-3.0.460.tar.gz

    TCAPLUSDB是腾讯云推出的一款分布式NoSQL数据库服务,它基于Apache HBase,并结合腾讯云的高性能存储和计算能力,提供了高可用、高性能、低成本的海量数据存储和实时查询能力,广泛应用于大数据分析、互联网+、...

    这可能是最全的高并发、高性能、高可用解决方案总结.docx

    在互联网领域,面对海量用户访问与数据处理需求,实现**高并发(High Concurrency)**、**高性能(High Performance)**及**高可用(High Availability)**成为了系统设计的核心目标之一。本文旨在全面解析针对这...

    分布式高并发.pdf

    大型网站系统具有高并发、高流量、高可用、海量数据、用户分布广泛、网络情况复杂、安全环境恶劣、需求快速变更、发布频繁等特点。 二、大型网站架构演化 大型网站架构演化经历了初始阶段的网站架构、应用服务和...

    提高查询速度--分区

    综上所述,分区技术在现代数据库管理系统中扮演着重要的角色,特别是在处理海量数据时,其对于提高查询性能、简化维护工作等方面具有显著的效果。通过对分区原理及其实现机制的深入理解,我们可以更好地利用这项技术...

    58的分布式存储架构

    随着互联网的发展,海量数据的处理成为了一个重要的挑战。分布式存储技术不仅可以解决单个设备存储空间有限的问题,还能通过增加节点的方式实现近乎无限的存储空间扩展。此外,分布式存储还能够通过复制和分区等机制...

    阿里云产品DRDS

    它能够帮助用户轻松管理和扩展其数据库系统,尤其适用于那些面临大规模数据处理挑战的企业。 #### 二、DRDS的起源与发展 DRDS的诞生源自于阿里巴巴集团内部业务快速发展的需求。随着业务规模的不断扩大,传统的...

    常用数据库对比.docx

    此外,Oracle提供丰富的分析函数,适合进行复杂的数据分析和海量数据查询。 - **挑战与局限**:Oracle数据库的价格相对较高,且在集群扩展时对系统架构设计和DBA技能要求较高,若配置不当可能影响性能。 2. **DB2...

    美团分布式数据库实践.pdf

    分布式数据库是现代互联网技术中不可或缺的一部分,特别是在处理大规模并发访问和海量数据的场景下,它的作用尤为突出。美团作为一家大型的生活服务平台,其在数据库架构上的实践和创新具有极高的参考价值。本篇文章...

    程序员编程艺术第一~二十七章集锦与总结(教你如何编程)

    - **应用场景**:大数据处理、海量日志分析等。 - **第十一章:最长公共子序列(LCS)问题** - **知识点**:动态规划算法、字符串匹配。 - **应用场景**:生物信息学、文本相似度计算等。 - **第十二~十五章:中签...

    用 Python 实现一个大数据搜索引擎 .pdf

    在大数据处理中,搜索引擎是不可或缺的一部分,用于快速检索海量数据中的特定信息。Python 作为一门易读、易学且功能强大的编程语言,非常适合用来构建这样的系统。本篇内容将介绍如何利用 Python 实现一个基本的...

Global site tag (gtag.js) - Google Analytics