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。

相关文章

Spring6 源码分析-ioc

Spring6 源码分析-ioc

（1）IDEA开发工具：2022.1.2 （2）JDK：Java17（Spring6要求JDK最低版本是Java17） （3）Spring：6.0.2 <dependencies><!--spring context依赖--><!--当你引入Spring Context依赖之后，表示将Spring的基础依赖引入了--><dependency><groupId>org.springframew
阅读更多...
Spring整体流程源码分析

Spring整体流程源码分析

DisableEncodeUrlFilter 防止sessionId被泄露 包装器模式 WebAsyncManagerIntegrationFilter WebAsyncManagerIntegrationFilter通常与Spring MVC的异步请求处理机制一起使用，确保在使用Callable或DeferredResult等异步处理方式时，安全上下文能够正确传播。 默认情况下，
阅读更多...
OpenCV自学笔记29. lsd直线检测算法(未完)

OpenCV自学笔记29. lsd直线检测算法(未完)

lsd直线检测算法 LSD是一种直线检测分割算法，它能在线性的时间内得出亚像素级精度的检测结果。该算法被设计成可以在任何数字图像上都无需参数调节。 参考：http://blog.csdn.net/lien0906/article/details/38417191 1、lsd算法的步骤(未完) LSD算法的步骤如下： 1、图像缩放2、梯度计算3、梯度排序4、阈值检测5、区域增长6、矩
阅读更多...
关于WindowManager在Android N和Android N以下表现差异的分析总结

关于WindowManager在Android N和Android N以下表现差异的分析总结

1. 问题描述 通过WindowManager往窗口里添加浮动按钮，在Android7.0时该按钮可以全局保留，直至进程被杀掉。而Android7.0以下（以Android4.4为例）浮动按钮随Activity的onStop()方法被覆盖。 以下为浮动按钮的实现代码： WindowManager mWm = (WindowManager)mContext.getSystemService(C
阅读更多...
常见加解密算法02 - RC4算法分析

常见加解密算法02 - RC4算法分析

RC4是一种广泛使用的流密码，它以其简洁和速度而闻名。区别于块密码，流密码特点在于按位或按字节来进行加密。 RC4由Ron Rivest在1987年设计，尽管它的命名看起来是第四版，实际上它是第一个对外发布的版本。 RC4算法的实施过程简洁明了，主要包括初始化和生成密钥流这两个阶段。 下面我们就一边解析算法，一边分析其代码实现。 初始化 该阶段的核心任务是利用一个可变长度的密钥来初始化一
阅读更多...
算法训练营第二十八天 | LeetCode 77 组合（剪枝优化）、LeetCode 216 组合总和III、LeetCode 17 电话号码的字母组合

算法训练营第二十八天 | LeetCode 77 组合（剪枝优化）、LeetCode 216 组合总和III、LeetCode 17 电话号码的字母组合

LeetCode 77 组合（剪枝优化） 当我们到达某一层，后面的结点数已经不能满足条件时。可以进行剪枝操作。 代码如下： class Solution {private:vector<int> path;vector<vector<int>> res;void backtracking(int n, int index, int k) {if (path.size() == k) {re
阅读更多...
回溯算法（Backtracking Algorithm）

回溯算法（Backtracking Algorithm）

回溯算法（Backtracking Algorithm）是一种试探性的解决问题方法，主要用于解决约束满足问题。这类问题通常存在多个可能的解，且解的空间可以被形式化地表示出来。回溯算法通过逐步构造候选解并检验其合法性的方式来探索解空间，当遇到无效解或不符合约束条件的情况时，会撤销（回溯）部分或全部已作出的选择，然后转向其他可能的解路径继续搜索。 回溯算法的核心特点和步骤如下： 定义解空间：确定
阅读更多...
python对排列三的分析

python对排列三的分析

对排列三（一种常见的彩票游戏）进行分析，我们通常关注其号码组合的可能性、中奖概率以及可能的号码趋势或模式。然而，由于排列三是基于随机抽取的，因此没有一种方法可以预测下一个中奖号码，但我们可以通过Python来分析历史数据和统计信息。 以下是一个简单的Python脚本示例，用于分析排列三的一些基本统计信息： python复制代码 from collections import Counte
阅读更多...
HashMap扩容时的rehash方法中(e.hash oldCap) == 0算法推导

HashMap扩容时的rehash方法中(e.hash oldCap) == 0算法推导

PS:由于文档是我在本地编写好之后再复制过来的，有些文本格式没能完整的体现，故提供下述图片，供大家阅览，以便有更好的阅读体验： HashMap在扩容时，需要先创建一个新数组,然后再将旧数组中的数据转移到新数组上来 此时，旧数组上的数据就会根据(e.hash & oldCap) 是否等于0这个算法,被很巧妙地分为2类: ① 等于0时，则将该头节点放到新数组时的索引位置等于其在旧数组时的索引位置,
阅读更多...
点云算法源代码及解析专栏目录

点云算法源代码及解析专栏目录

1、轮廓线提取及简化 1.1  道格拉斯普克算法(DP)的点云轮廓线简化-CSDN博客 1.2  alpha shapes提取边缘点函数调用（API） 1.3 基于KNN-凸包提取轮廓点（matlab） 1.4 基于公共转点的Alpha shapes有序边缘点提取 1.5  一元线性回归分析（参数解算） 2、三维重建 2.1 简单场景下点云分类（地面、植被、建筑物）及三维重建
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2