Hash表及hash算法的分析

2024-04-29 18:08
文章标签 算法 分析 hash 表及

本文主要是介绍Hash表及hash算法的分析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Hash表中的一些原理/概念,及根据这些原理/概念:

一.       Hash表概念

二.       Hash构造函数的方法,及适用范围

三.       Hash处理冲突方法,各自特征

四.       Hash查找过程

五.       实现一个使用Hash存数据的场景-------Hash查找算法,插入算法

六.       JDK中HashMap的实现

七.       Hash表与HashMap的对比,性能分析


 结构之法,算法之道 从头到尾彻底解析Hash表算法


 一.    Hash表概念 

               在查找表中我们已经说过,在Hash表中,记录在表中的位置和其关键字之间存在着一种确定的关系。这样       我们就能预先知道所查关键字在表中的位置,从而直接通过下标找到记录。使ASL趋近与0.

 

              1)   哈希(Hash)函数是一个映象,即: 将关键字的集合映射到某个地址集合上,它的设置很灵活,只要这个地址集合的大小不超出允许范围即可;

              2)  由于哈希函数是一个压缩映象,因此,在一般情况下,很容易产生“冲突”现象,即: key1¹ key2,而  f (key1) = f(key2)。

              3).  只能尽量减少冲突而不能完全避免冲突,这是因为通常关键字集合比较大,其元素包括所有可能的关键字,而地址集合的元素仅为哈希表中的地址值

            在构造这种特殊的“查找表” 时,除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外;还需要找到一种“处理冲突” 的方法。

 

二 .     Hash构造函数的方法,及适用范围

  • 直接定址法
  • 数字分析法
  • 平方取中法
  • 折叠法
  • 除留余数法
  • 随机数法      

      (1)直接定址法:

                哈希函数为关键字的线性函数,H(key) = key 或者 H(key) = a ´ key + b

              此法仅适合于:地址集合的大小 = = 关键字集合的大小,其中a和b为常数。

     (2)数字分析法:

             假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us),分析关键字集中的全体, 并从中提取分布均匀的若干位或它们的组合作为地址。

             此法适于:能预先估计出全体关键字的每一位上各种数字出现的频度。

     (3)平方取中法:

               以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ,同时平方值的中间各位又能受到整个关键字中各位的影响。

             此法适于:关键字中的每一位都有某些数字重复出现频度很高的现象。

     (4)折叠法:

            将关键字分割成若干部分,然后取它们的叠加和为哈希地址。两种叠加处理的方法:移位叠加:将分割后的几部分低位对齐相加;间界叠加:从一端沿分割界来回折叠,然后对齐相加。

            此法适于:关键字的数字位数特别多。

     (5)除留余数法:

             设定哈希函数为:H(key) = key MOD p   ( p≤m ),其中, m为表长,p 为不大于 m 的素数,或是不含 20 以下的质因子

     (6)随机数法:

           设定哈希函数为:H(key) = Random(key)其中,Random 为伪随机函数

           此法适于:对长度不等的关键字构造哈希函数。

 

         实际造表时,采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态),以及哈希表    长度(哈希地址范围),总的原则是使产生冲突的可能性降到尽可能地小。


三.       Hash处理冲突方法,各自特征

 “处理冲突” 的实际含义是:为产生冲突的关键字寻找下一个哈希地址。

  •   开放定址法
  •   再哈希法
  •   链地址法

      (1)开放定址法:

               为产生冲突的关键字地址 H(key) 求得一个地址序列: H0, H1, H2, …, Hs  1≤s≤m-1,Hi = ( H(key)+di  ) MOD m,其中: i=1, 2, …, s,H(key)为哈希函数;m为哈希表长;

 

      (2)链地址法:


       将所有哈希地址相同的记录都链接在同一链表中。

      (3)再哈希法:

               方法:构造若干个哈希函数,当发生冲突时,根据另一个哈希函数计算下一个哈希地址,直到冲突不再发生。即:Hi=Rhi(key)     i=1,2,……k,其中:Rhi——不同的哈希函数,特点:计算时间增加

 四.       Hash查找过程

        对于给定值 K,计算哈希地址 i = H(K),若 r[i] = NULL  则查找不成功,若 r[i].key = K  则查找成功, 否则 “求下一地址 Hi” ,直至r[Hi] = NULL  (查找不成功)  或r[Hi].key = K  (查找成功) 为止。

 

 五.       实现一个使用Hash存数据的场景-------Hash查找算法,插入算法

         假设我们要设计的是一个用来保存在校学生个人信息的数据表。因为在校学生数量也不是特别巨大(8W?),每个学生的学号是唯一的,因此,我们可以简单的应用直接定址法,声明一个10W大小的数组,每个学生的学号作为主键。然后每次要添加或者查找学生,只需要根据需要去操作即可。

      但是,显然这样做是很脑残的。这样做系统的可拓展性和复用性就非常差了,比如有一天人数超过10W了?如果是用来保存别的数据呢?或者我只需要保存20条记录呢?声明大小为10W的数组显然是太浪费了的。

 

     如果我们是用来保存大数据量(比如银行的用户数,4大的用户数都应该有3-5亿了吧?),这时候我们计算出来的HashCode就很可能会有冲突了, 我们的系统应该有“处理冲突”的能力,此处我们通过挂链法“处理冲突”

 

     如果我们的数据量非常巨大,并且还持续在增加,如果我们仅仅只是通过挂链法来处理冲突,可能我们的链上挂了上万个数据后,这个时候再通过静态搜索来查找链表,显然性能也是非常低的。所以我们的系统应该还能实现自动扩容,当容量达到某比例后,即自动扩容,使装载因子保存在一个固定的水平上


什么时候ReHash

在介绍HashMap的内部实现机制时提到了两个参数,DEFAULT_INITIAL_CAPACITY和DEFAULT_LOAD_FACTOR,DEFAULT_INITIAL_CAPACITY是table数组的容量,DEFAULT_LOAD_FACTOR则是为了最大程度避免哈希冲突,提高HashMap效率而设置的一个影响因子,将其乘以DEFAULT_INITIAL_CAPACITY就得到了一个阈值threshold,当HashMap的容量达到threshold时就需要进行扩容,这个时候就要进行ReHash操作了,可以看到下面addEntry函数的实现,当size达到threshold时会调用resize函数进行扩容。

[java]  view plain copy 在CODE上查看代码片 派生到我的代码片
  1. void addEntry(int hash, K key, V value, int bucketIndex) {    
  2. ntry<K,V> e = table[bucketIndex];    
  3.       table[bucketIndex] = new Entry<K,V>(hash, key, value, e);    
  4.       if (size++ >= threshold)    
  5.           resize(2 * table.length);    
  6.   }    

在扩容的过程中需要进行ReHash操作,而这是非常耗时的,在实际中应该尽量避免。


常用字符串哈希函数有BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等等。对于以上几种哈希函数,我对其进行了一个小小的评测。

Hash函数数据1数据2数据3数据4数据1得分数据2得分数据3得分数据4得分平均分
BKDRHash 2 0 4774 481 96.55 100 90.95 82.05 92.64
APHash 2 3 4754 493 96.55 88.46 100 51.28 86.28
DJBHash 2 2 4975 474 96.55 92.31 0 100 83.43
JSHash 1 4 4761 506 100 84.62 96.83 17.95 81.94
RSHash 1 0 4861 505 100 100 51.58 20.51 75.96
SDBMHash 3 2 4849 504 93.1 92.31 57.01 23.08 72.41
PJWHash 30 26 4878 513 0 0 43.89 0 21.95
ELFHash 30 26 4878 513 0 0 43.89 0 21.95

其中数据1为100000个字母和数字组成的随机串哈希冲突个数。数据2为100000个有意义的英文句子哈希冲突个数。数据3为数据1的哈希值与1000003(大素数)求模后存储到线性表中冲突的个数。数据4为数据1的哈希值与10000019(更大素数)求模后存储到线性表中冲突的个数。

经过比较,得出以上平均得分。平均数为平方平均数。可以发现,BKDRHash无论是在实际效果还是编码实现中,效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差,但得分相似,其算法本质是相似的。

在信息修竞赛中,要本着易于编码调试的原则,个人认为BKDRHash是最适合记忆和使用的。

各种哈希函数的C语言程序代码

unsigned int SDBMHash(char *str)
{unsigned int hash = 0;while (*str){// equivalent to: hash = 65599*hash + (*str++);hash = (*str++) + (hash << 6) + (hash << 16) - hash;}return (hash & 0x7FFFFFFF);
}// RS Hash Function
unsigned int RSHash(char *str)
{unsigned int b = 378551;unsigned int a = 63689;unsigned int hash = 0;while (*str){hash = hash * a + (*str++);a *= b;}return (hash & 0x7FFFFFFF);
}// JS Hash Function
unsigned int JSHash(char *str)
{unsigned int hash = 1315423911;while (*str){hash ^= ((hash << 5) + (*str++) + (hash >> 2));}return (hash & 0x7FFFFFFF);
}// P. J. Weinberger Hash Function
unsigned int PJWHash(char *str)
{
unsigned int BitsInUnignedInt=(unsigned int)(sizeof(unsigned int) * 8);
unsigned int ThreeQuarters=(unsigned int)((BitsInUnignedInt  * 3) / 4);unsigned int OneEighth  = (unsigned int)(BitsInUnignedInt / 8);
 unsigned int HighBits= (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);unsigned int hash   = 0;unsigned int test   = 0;while (*str){hash = (hash << OneEighth) + (*str++);if ((test = hash & HighBits) != 0){hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));}}return (hash & 0x7FFFFFFF);
}// ELF Hash Function
unsigned int ELFHash(char *str)
{unsigned int hash = 0;unsigned int x    = 0;while (*str){hash = (hash << 4) + (*str++);if ((x = hash & 0xF0000000L) != 0){hash ^= (x >> 24);hash &= ~x;}}return (hash & 0x7FFFFFFF);
}// BKDR Hash Function
unsigned int BKDRHash(char *str)
{unsigned int seed = 131; // 31 131 1313 13131 131313 etc..unsigned int hash = 0;while (*str){hash = hash * seed + (*str++);}return (hash & 0x7FFFFFFF);
}// DJB Hash Function
unsigned int DJBHash(char *str)
{unsigned int hash = 5381;while (*str){hash += (hash << 5) + (*str++);}return (hash & 0x7FFFFFFF);
}// AP Hash Function
unsigned int APHash(char *str)
{unsigned int hash = 0;int i;for (i=0; *str; i++){if ((i & 1) == 0){hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));}else{hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));}}return (hash & 0x7FFFFFFF);
}


这篇关于Hash表及hash算法的分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/946789

相关文章

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Springboot中分析SQL性能的两种方式详解

《Springboot中分析SQL性能的两种方式详解》文章介绍了SQL性能分析的两种方式:MyBatis-Plus性能分析插件和p6spy框架,MyBatis-Plus插件配置简单,适用于开发和测试环... 目录SQL性能分析的两种方式:功能介绍实现方式:实现步骤:SQL性能分析的两种方式:功能介绍记录

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

C#使用DeepSeek API实现自然语言处理,文本分类和情感分析

《C#使用DeepSeekAPI实现自然语言处理,文本分类和情感分析》在C#中使用DeepSeekAPI可以实现多种功能,例如自然语言处理、文本分类、情感分析等,本文主要为大家介绍了具体实现步骤,... 目录准备工作文本生成文本分类问答系统代码生成翻译功能文本摘要文本校对图像描述生成总结在C#中使用Deep

Redis主从/哨兵机制原理分析

《Redis主从/哨兵机制原理分析》本文介绍了Redis的主从复制和哨兵机制,主从复制实现了数据的热备份和负载均衡,而哨兵机制可以监控Redis集群,实现自动故障转移,哨兵机制通过监控、下线、选举和故... 目录一、主从复制1.1 什么是主从复制1.2 主从复制的作用1.3 主从复制原理1.3.1 全量复制

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

Redis主从复制的原理分析

《Redis主从复制的原理分析》Redis主从复制通过将数据镜像到多个从节点,实现高可用性和扩展性,主从复制包括初次全量同步和增量同步两个阶段,为优化复制性能,可以采用AOF持久化、调整复制超时时间、... 目录Redis主从复制的原理主从复制概述配置主从复制数据同步过程复制一致性与延迟故障转移机制监控与维

Redis连接失败:客户端IP不在白名单中的问题分析与解决方案

《Redis连接失败:客户端IP不在白名单中的问题分析与解决方案》在现代分布式系统中,Redis作为一种高性能的内存数据库,被广泛应用于缓存、消息队列、会话存储等场景,然而,在实际使用过程中,我们可能... 目录一、问题背景二、错误分析1. 错误信息解读2. 根本原因三、解决方案1. 将客户端IP添加到Re

Redis主从复制实现原理分析

《Redis主从复制实现原理分析》Redis主从复制通过Sync和CommandPropagate阶段实现数据同步,2.8版本后引入Psync指令,根据复制偏移量进行全量或部分同步,优化了数据传输效率... 目录Redis主DodMIK从复制实现原理实现原理Psync: 2.8版本后总结Redis主从复制实