精华内容
下载资源
问答
  • Hash算法

    2021-01-13 22:19:54
    Hash算法 说到Hash(哈希),开发人员应该不陌生,比如Hash表是一种非常常用的数据结构,通过Hash表能够根据键值快速找到数据。哈希函数将文本(或其他数据)映射为整数,从而能够提高检索效率。 密码学中的Hash算法...

    Hash算法

    说到Hash(哈希),开发人员应该不陌生,比如Hash表是一种非常常用的数据结构,通过Hash表能够根据键值快速找到数据。哈希函数将文本(或其他数据)映射为整数,从而能够提高检索效率。

    密码学中的Hash算法和普通的Hash算法不是同一个概念,从安全的角度考虑,密码学中的Hash算法除了有普通Hash算法的特性之外,还有其他的一些特性。

    密码学Hash算法也通常称作摘要算法,是密码学中的基础算法,是现代密码学中的核心组成部分。2004年山东大学王小云教授发表论文,指出了MD5和SHA-1两种Hash算法的漏洞,引起了业界的恐慌,足以说明Hash算法的重要性。密码学中有很多密码学Hash算法,比如MD5、SHA-1、SHA128、SHA256、SHA512等,国家商用密码中也有一个Hash算法SM3。我们不用理解Hash算法的内部实现原理,更应该关注其特性、用途以及使用中需要注意的点。

    在密码学中,Hash函数将任意大小(例如文本消息)的输入数据转换为固定大小(例如256位)的结果,这称为哈希值(或哈希码、消息摘要)。比如SHA-256和SHA3-256,可将任意输入转换为256位输出。

    在这里插入图片描述

    密码学Hash算法示例

    我们可以借助 OpenSSL 附带的命令行工具计算字符串"hello"的SHA256算法哈希值:

    $ echo -n “hello” | openssl sha256
    (stdin)= 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
    也可以借助开源国密算法库 GmSSL 的命令行工具,计算 SM3 算法的哈希值:

    $ echo -n “hello” | gmssl dgst -sm3
    (stdin)= becbbfaae6548b8bf0cfcad5a27183cd1be6093b1cceccc303d9c61d0a645268

    密码学Hash算法的特点

    设计一个Hash算法并不难,但要设计一个能用于密码学上的Hash算法非常难,需要有非常深厚的数学和密码学功底。一个设计良好的密码学Hash算法需要具有如下特点:

    确定性:相同的消息总是能得到同样的摘要值,特定的Hash算法,不管消息长度是多少,最终的摘要值长度是相同的。
    快速:计算任何给定消息的哈希值应该很快。
    难以分析:对输入消息的微小修改将完全改变输出哈希值。
    不可逆:通过摘要值很难逆向计算出原始消息,Hash算法具备单向性,摘要值是不可逆的,这也是非常重要的特性。为了逆向计算出原始消息,唯一的方法就是采用暴力攻击、字典攻击、彩虹表
    没有碰撞:找到两个具有相同哈希值的不同消息非常困难(或几乎不可能)。
    注意第5点,没有冲突是一种理想情况,考虑到最后生成的摘要值只有固定的有限位,必然存在不同消息具有相同哈希值的情况,但这里强调的是找到它们非常困难。后面谈到 MD5 的破解将会谈到。

    密码学Hash算法的用途

    密码学哈希算法用途很广,下面看看最常见的几个用途:

    文档/消息完整性
    验证文件/文档/消息的完整性。比如我们在网站下载文件时,网站通常会给出文件的 MD5 值或 SHA256 值。

    在这里插入图片描述
    通过对比哈希值,我们可以确保自己下载的文件和服务器上是一致的。

    存储密码
    这个开发人员应该很熟悉,当然也有菜鸟程序员直接往数据库中存储明文密码(从曝光的拖库攻击事件中,发现这么做的公司还不少)。开发人员通常不将纯文本密码保存在数据库中,而保存密码散列值或从密码派生的更复杂的值(例如,Scrypt派生的值)。

    在这里插入图片描述
    上面的示例来自现代 Linux 系统中的 /etc/shadow 文件,里面的密码存储为带盐的多轮SHA-512哈希值。

    采用这种解决方案,即使数据库或数据文件泄露,攻击者也无法通过口令的摘要值计算出原始口令,攻击者很难伪造用户进行攻击。

    系统具体如何校验用户密码呢?大概的步骤如下:

    用户输入用户名和口令登录。

    系统使用Hash算法计算出口令的摘要值。

    系统使用用户名和摘要值在数据库表中进行检索,一旦匹配到就说明该用户输入的口令是正确的。

    生成唯一ID

    生成特定文档/消息的(几乎)唯一ID。密码散列函数几乎根据文档的内容唯一地标识文档。当然从理论上讲,任何哈希函数都可能发生碰撞,但是这种碰撞不太可能发生,因此大多数系统(如Git)都假定它们使用的哈希函数不存在碰撞。

    这样的示例有 git 版本管理系统,其每一个提交通过一个哈希值标记。

    在这里插入图片描述
    这个特性还可以用来比较大文件,通过计算两个文件的Hash值,比较Hash值就可以判断两个文件是否相同。

    伪随机数生成
    伪随机数生成和密钥派生。生成随机序列的一种简单方法是这样的:从随机种子开始(例如键盘单击或鼠标移动)。附加“1”并计算散列以获得第一个随机数,然后附加“2”并计算散列获得第二个随机数,以此类推。

    工作量证明算法
    主要用在比特币,也就是俗称的挖矿。大多数工作量证明算法计算的哈希值大于特定值(称为挖掘难度)。为了找到此哈希值,矿工计算了数十亿个不同的哈希,并采用其中的最大哈希值,因为哈希数是不可预测的。例如,工作证明问题的定义如下:找到一个数字p,以使hash(x + p)的开头保留10个零位。

    Hash算法一览

    在过去,软件开发人员设计了许多密码哈希算法。其中有些已证明不安全(例如 MD5 和 SHA1 ),有些仍被认为是安全的(例如 SHA-2 、SHA-3 和 BLAKE2 )。下面让我们了解一下目前广泛使用的加密哈希算法。

    MD5
    MD5是一种比较常用的Hash算法,摘要值长度固定是 128 比特, MD5 算法目前被证明已经不安全了,不建议使用。

    SHA-1
    SHA-1算法类似于MD5算法,输出的长度固定是160比特。SHA-1算法在严谨的加密学中已经被证明是不安全的,但在实际中仍然有使用,因为在现实世界中要构造出碰撞还是非常困难的,需要经过大量的运算。当然在新的应用中要避免使用。

    SHA-2
    SHA-2是一系列强大的密码哈希函数:SHA-256(256位哈希)、SHA-384(384位哈希)、SHA-512(512位哈希)等。SHA-2算法是目前建议使用的Hash算法,在美国作为官方加密标准发布。

    从设计上讲,哈希输出的位数越多,一般而言具有更高的安全性和更高的抗冲突性。通常,128位哈希函数要比256位哈希函数要弱,而256位哈希函数要比512位哈希函数弱。因此,SHA-512比SHA-256更强大。

    SHA-3
    SHA-3算法并不是为了取代SHA-2算法,而是一种在设计上和SHA-2完全不同的算法,主要有四种算法,分别是SHA3-256、SHA3-512、SHA3-224、SHA3-384,输出的长度分别是256比特、512比特、224比特、384比特。

    在相同的哈希长度下,SHA-3比SHA-2更安全。例如,SHA3-256比SHA-256提供更多的加密强度。

    SHA-3被认为是高度安全的,在美国作为官方推荐的加密标准发布。

    SM3
    SM3是国密密码杂凑算法标准,由国家密码管理局于2010年12月公布。SM3的输出杂凑值长度为256比特(32字节),与国际标准SHA-256等长。SM3设计安全性为128比特,安全性与256比特椭圆曲线/SM2、SM4/SMS4、AES-128等同。

    小知识:王小云院士真的破解了 MD5 吗?

    2004年8月,在美国加州圣巴巴拉召开的国际密码大会上,王小云宣读了自己和研究团队对于MD4、MD5、HAVAL-128和RIPEMD四个国际著名密码算法的破译结果。

    这被认为是2004年密码学界最具突破性的结果,堪称学术界的一场强烈地震。当年国际密码大会总结报告上写道:我们该怎么办?MD5被重创了,它即将从应用中淘汰。

    2005年,美国《新科学家》杂志在一篇文章中,用了颇具震撼力的标题——《崩溃!密码学的危机》,报道了王小云团队花10年时间取得的学术成果。

    所谓的“破解”其实误导了很多人,并不是说扔给王小云一个 MD5 散列值,然后她马上就能算出一个原文来。从密文推算出明文理论上是不可能的,所以王小云的研究成果并不能通过 MD5 的散列值逆向推算出明文。即给定 Hash 值,王小云不能逆向计算出 M。

    MD5(M)=Hash
    其中 M 指密码的明文,Hash 表示密码散列后的密文。

    实际上,王小云的研究成果如下:

    MD5(M1)=MD5(M2)
    即给定消息 M1,能够计算获取 M2,使得 M2 产生的散列值与 M1 产生的散列值相同。如此,MD5 的抗碰撞性就已经不满足了,使得 MD5 不再是安全的散列算法。这样一来,MD5 用于数字签名将存在严重问题,因为可以篡改原始消息,而生成相同的 Hash 值。

    这里,简单地用王教授的碰撞法给大家举个简单的例子。假如用户 A 给 B 写了个 Email 内容为 Hello,然后通过王教授的碰撞法,可能得到 Fuck 这个字符串的摘要信息和 Hello 这个字符串产生的摘要信息是一样的。如果 B 收到的 Email 内容为 Fuck,经过 MD5 计算后的,B 也将认为 Email 并没有被修改!但事实并非如此。

    王小云院士的研究报告表明,MD4,MD5,HAVAL-128,RIPEMD 和 SHA-1 均已被证实存在上面的漏洞,即给定消息 M1,能够找到不同消息 M2 产生相同的散列值,即产生 Hash 碰撞。

    展开全文
  • hash算法原理详解

    万次阅读 多人点赞 2016-05-19 22:35:01
    一.概念 哈希表就是一种以 键-值(key-indexed) 存储数据的结构,我们只要输入待查找的值即key,即可查找到其对应的值。 哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为...

    一.概念

    哈希表就是一种以 键-值(key-indexed) 存储数据的结构,我们只要输入待查找的值即key,即可查找到其对应的值。

    哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值。这是对于简单的键的情况,我们将其扩展到可以处理更加复杂的类型的键。

    使用哈希查找有两个步骤:

    1. 使用哈希函数将被查找的键转换为数组的索引。在理想的情况下,不同的键会被转换为不同的索引值,但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况。所以哈希查找的第二个步骤就是处理冲突

    2. 处理哈希碰撞冲突。有很多处理哈希碰撞冲突的方法,本文后面会介绍拉链法和线性探测法。

    哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制,那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1);如果没有时间限制,那么我们可以使用无序数组并进行顺序查找,这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。

     

     

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

     

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

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

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

     

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

    二.Hash构造函数的方法

     

       1.直接定址法:

                             

     直接定址法是以数据元素关键字k本身或它的线性函数作为它的哈希地址,即:H(k)=k  或 H(k)=a×k+b ; (其中a,b为常数)

      例1,有一个人口统计表,记录了从1岁到100岁的人口数目,其中年龄作为关键字,哈希函数取关键字本身,如图(1):

    地址

    A1

    A2

    ……

    A99

    A100

    年龄

    1

    2

    ……

    99

    100

    人数

    980

    800

    ……

    495

    107

    可以看到,当需要查找某一年龄的人数时,直接查找相应的项即可。如查找99岁的老人数,则直接读出第99项即可。

     

    地址

    A0

    A1

    ……

    A99

    A100

    年龄

    1980

    1981

    ……

    1999

    2000

    人数

    980

    800

    ……

    495

    107

     

    如果我们要统计的是80后出生的人口数,如上表所示,那么我们队出生年份这个关键字可以用年份减去1980来作为地址,此时f(key)=key-1980

    这种哈希函数简单,并且对于不同的关键字不会产生冲突,但可以看出这是一种较为特殊的哈希函数,实际生活中,关键字的元素很少是连续的。用该方法产生的哈希表会造成空间大量的浪费,因此这种方法适应性并不强。[2]

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

     

    2.数字分析法:

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

    数字分析法是取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法。即当关键字的位数很多时,可以通过对关键字的各位进行分析,丢掉分布不均匀的位,作为哈希值。它只适合于所有关键字值已知的情况。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间。

       例2,要构造一个数据元素个数n=80,哈希长度m=100的哈希表。不失一般性,我们这里只给出其中8个关键字进行分析,8个关键字如下所示:

    K1=61317602      K2=61326875      K3=62739628      K4=61343634

    K5=62706815      K6=62774638      K7=61381262      K8=61394220

    分析上述8个关键字可知,关键字从左到右的第1、2、3、6位取值比较集中,不宜作为哈希地址,剩余的第4、5、7、8位取值较均匀,可选取其中的两位作为哈希地址。设选取最后两位作为哈希地址,则这8个关键字的哈希地址分别为:2,75,28,34,15,38,62,20。           

     

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

                 

    3.折叠法:

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

    所谓折叠法是将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位),这方法称为折叠法。这种方法适用于关键字位数较多,而且关键字中每一位上数字分布大致均匀的情况。

      折叠法中数位折叠又分为移位叠加和边界叠加两种方法,移位叠加是将分割后是每一部分的最低位对齐,然后相加;边界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加。

    例4,当哈希表长为1000时,关键字key=110108331119891,允许的地址空间为三位十进制数,则这两种叠加情况如图:

           移位叠加                                 边界叠加

           8 9 1                                     8 9 1

           1 1 9                                     9 1 1

           3 3 1                                     3 3 1

           1 0 8                                     8 0 1

        +  1 1 0                                   + 1 1 0              

       (1) 5 5 9                                  (3)0 4 4

                     图(2)由折叠法求哈希地址

         用移位叠加得到的哈希地址是559,而用边界叠加所得到的哈希地址是44。如果关键字不是数值而是字符串,则可先转化为数。转化的办法可以用ASCⅡ字符或字符的次序值。

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

     

    4.平方取中法

      这是一种常用的哈希函数构造方法。这个方法是先取关键字的平方,然后根据可使用空间的大小,选取平方数是中间几位为哈希地址。

    哈希函数 H(key)=“key2的中间几位”因为这种方法的原理是通过取平方扩大差别,平方值的中间几位和这个数的每一位都相关,则对不同的关键字得到的哈希函数值不易产生冲突,由此产生的哈希地址也较为均匀。

    例5,若设哈希表长为1000则可取关键字平方值的中间三位,如图所示:

    关键字

    关键字的平方

    哈希函数值

    1234

    1522756

    227

    2143

    4592449

    924

    4132

    17073424

    734

    3214

    10329796

    297 

      

    下面给出平方取中法的哈希函数

         //平方取中法哈希函数,结设关键字值32位的整数

         //哈希函数将返回key * key的中间10位

           Int  Hash (int key)

             {

         //计算key的平方

          Key * = key ;

         //去掉低11位

         Key>>=11;

         // 返回低10位(即key * key的中间10位)

           Return key %1024;

              }

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


    5.减去法

    减去法是数据的键值减去一个特定的数值以求得数据存储的位置。

    例7,公司有一百个员工,而员工的编号介于1001到1100,减去法就是员工编号减去1000后即为数据的位置。编号1001员工的数据在数据中的第一笔。编号1002员工的数据在数据中的第二笔…依次类推。从而获得有关员工的所有信息,因为编号1000以前并没有数据,所有员工编号都从1001开始编号。

     

    6.基数转换法

      将十进制数X看作其他进制,比如十三进制,再按照十三进制数转换成十进制数,提取其中若干为作为X的哈希值。一般取大于原来基数的数作为转换的基数,并且两个基数应该是互素的。

     

    例Hash(80127429)=(80127429)13=8*137+0*136+1*135+2*134+7*133+4*132+2*131+9=(502432641)10如果取中间三位作为哈希值,得Hash(80127429)=432

     为了获得良好的哈希函数,可以将几种方法联合起来使用,比如先变基,再折叠或平方取中等等,只要散列均匀,就可以随意拼凑。

     

     

      7.除留余数法:

                

    假设哈希表长为mp为小于等于m的最大素数,则哈希函数为

    hk=k  %  p ,其中%为模p取余运算。

    例如,已知待散列元素为(18756043549046),表长m=10p=7,则有

        h(18)=18 % 7=4    h(75)=75 % 7=5    h(60)=60 % 7=4   

        h(43)=43 % 7=1    h(54)=54 % 7=5    h(90)=90 % 7=6   

        h(46)=46 % 7=4

    此时冲突较多。为减少冲突,可取较大的m值和p值,如m=p=13,结果如下:

        h(18)=18 % 13=5    h(75)=75 % 13=10    h(60)=60 % 13=8    

        h(43)=43 % 13=4    h(54)=54 % 13=2    h(90)=90 % 13=12   

        h(46)=46 % 13=7

    此时没有冲突,如图8.25所示。

     

         1      2     3     4     5      6     7     8     9     10     11    12

     

     

     

    54

     

    43

    18

     

    46

    60

     

    75

     

    90

                          


    除留余数法求哈希地址

     

    理论研究表明,除留余数法的模p取不大于表长且最接近表长m素数时效果最好,且p最好取1.1n~1.7n之间的一个素数(n为存在的数据元素个数)

     

     

    8.随机数法:

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

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

     

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

     

    9.随机乘数法

      亦称为“乘余取整法”。随机乘数法使用一个随机实数f,0≤f<1,乘积f*k的分数部分在0~1之间,用这个分数部分的值与n(哈希表的长度)相乘,乘积的整数部分就是对应的哈希值,显然这个哈希值落在0~n-1之间。其表达公式为:Hash(k)=「n*(f*k%1)」其中“f*k%1”表示f*k 的小数部分,即f*k%1=f*k-「f*k」

      例10,对下列关键字值集合采用随机乘数法计算哈希值,随机数f=0.103149002 哈希表长度n=100得图:

     

    k

    f*k

    n*((f*k)的小数部分)

    Hash(k)

    319426

    32948.47311

    47.78411

    47

    718309

    74092.85648

    86.50448

    86

    629443

    64926.41727

    42.14427

    42

    919697

    84865.82769

    83.59669

    83

      此方法的优点是对n的选择不很关键。通常若地址空间为p位就是选n=2p.Knuth对常数f的取法做了仔细的研究,他认为f取任何值都可以,但某些值效果更好。如f=(-1)/2=0.6180329...比较理想。


    10.字符串数值哈希法

    在很都情况下关键字是字符串,因此这样对字符串设计Hash函数是一个需要讨论的问题。下列函数是取字符串前10个字符来设计的哈希函数

    Int Hash _ char (char *X)

    {

      int I ,sum

      i=0;

      while (i 10 && X[i])

      Sum +=X[i++];

      sum%=N;      //N是记录的条数

      }

    这种函数把字符串的前10个字符的ASCⅡ值之和对N取摸作为Hash地址,只要N较小,Hash地址将较均匀分布[0,N]区间内,因此这个函数还是可用的。对于N很大的情形,可使用下列函数

    int ELFhash (char *key )

    {

     Unsigned long h=0,g;

    whie (*key)

    {

    h=(h<<4)+ *key;

    key++;

    g=h & 0 xF0000000L;

    if (g) h^=g>>24;

    h & =~g;

    }

    h=h % N

    return (h);

    }

      这个函数称为ELFHash(Exextable and Linking Format ,ELF,可执行链接格式)函数。它把一个字符串的绝对长度作为输入,并通过一种方式把字符的十进制值结合起来,对长字符串和短字符串都有效,这种方式产生的位置不可能不均匀分布。


    11.旋转法

      旋转法是将数据的键值中进行旋转。旋转法通常并不直接使用在哈希函数上,而是搭配其他哈希函数使用。

      例11,某学校同一个系的新生(小于100人)的学号前5位数是相同的,只有最后2位数不同,我们将最后一位数,旋转放置到第一位,其余的往右移。

    新生学号

    旋转过程

    旋转后的新键值

    5062101

    5062101

    1506210

    5062102

    5062102

    2506210

    5062103

    5062103

    3506210

    5062104

    5062104

    4506210

    5062105

    5062105

    5506210

                        如图

     运用这种方法可以只输入一个数值从而快速地查到有关学生的信息。

     

     

    在实际应用中,应根据具体情况,灵活采用不同的方法,并用实际数据测试它的性能,以便做出正确判定。通常应考虑以下五个因素 

    l 计算哈希函数所需时间 (简单)。

    l 关键字的长度。

    l 哈希表大小。

    l 关键字分布情况。

    l 记录查找频率

     



    三.Hash处理冲突方法

       通过构造性能良好的哈希函数,可以减少冲突,但一般不可能完全避免冲突,因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突,两种情况下解决冲突的方法应该一致。下面以创建哈希表为例,说明解决冲突的方法。常用的解决冲突方法有以下四种:

     通过构造性能良好的哈希函数,可以减少冲突,但一般不可能完全避免冲突,因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突,两种情况下解决冲突的方法应该一致。下面以创建哈希表为例,说明解决冲突的方法。常用的解决冲突方法有以下四种:

    1.         开放定址法

    这种方法也称再散列法其基本思想是:当关键字key的哈希地址p=Hkey)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,直到找出一个不冲突的哈希地址pi 将相应元素存入其中。这种方法有一个通用的再散列函数形式:

              Hi=Hkey+di% m   i=12…,n

        其中Hkey)为哈希函数,为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。主要有以下三种:

    l         线性探测再散列

        dii=123m-1

    这种方法的特点是:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。

    l         二次探测再散列

        di=12-1222-22k2-k2    ( k<=m/2 )

        这种方法的特点是:冲突发生时,在表的左右进行跳跃式探测,比较灵活。

    l         伪随机探测再散列

        di=伪随机数序列。

    具体实现时,应建立一个伪随机数发生器,(如i=(i+p) % m),并给定一个随机数做起点。

    例如,已知哈希表长度m=11,哈希函数为:Hkey= key  %  11,则H47=3H26=4H60=5,假设下一个关键字为69,则H69=3,与47冲突。如果用线性探测再散列处理冲突,下一个哈希地址为H1=3 + 1% 11 = 4,仍然冲突,再找下一个哈希地址为H2=3 + 2% 11 = 5,还是冲突,继续找下一个哈希地址为H3=3 + 3% 11 = 6,此时不再冲突,将69填入5号单元,参图8.26 (a)。如果用二次探测再散列处理冲突,下一个哈希地址为H1=3 + 12% 11 = 4,仍然冲突,再找下一个哈希地址为H2=3 - 12% 11 = 2,此时不再冲突,将69填入2号单元,参图8.26 (b)。如果用伪随机探测再散列处理冲突,且伪随机数序列为:259……..,则下一个哈希地址为H1=3 + 2% 11 = 5,仍然冲突,再找下一个哈希地址为H2=3 + 5% 11 = 8,此时不再冲突,将69填入8号单元,参图8.26 (c)

     

     

                                                           10    

     

     

     

     

    47

    26

    60

    69

     

     

     

     

             a 用线性探测再散列处理冲突

     

     

                                                           10    

     

     

     

    69

    47

    26

    60

     

     

     

     

     

             b 用二次探测再散列处理冲突

     

     

                                                           10    

     

     

     

     

    47

    26

    60

     

     

    69

     

     

             c 用伪随机探测再散列处理冲突

     

                          8.26开放地址法处理冲突

    从上述例子可以看出,线性探测再散列容易产生“二次聚集”,即在处理同义词的冲突时又导致非同义词的冲突。例如,当表中i, i+1 ,i+2三个单元已满时,下一个哈希地址为i, i+1 ,i+2,或i+3的元素,都将填入i+3这同一个单元,而这四个元素并非同义词。线性探测再散列的优点是:只要哈希表不满,就一定能找到一个不冲突的哈希地址,而二次探测再散列和伪随机探测再散列则不一定。

    2. 再哈希法

        这种方法是同时构造多个不同的哈希函数:

        Hi=RH1key  i=12k

    当哈希地址Hi=RH1key)发生冲突时,再计算Hi=RH2key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。

    3. 链地址法

        这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

    例如,已知一组关键字(324036531646712742244964),哈希表长度为13,哈希函数为:Hkey= key % 13,则用链地址法处理冲突的结果如图

     



     
      哈希表及处理冲突的方法(转) - 另一片天空 - 仰望天空
     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     


    链地址法处理冲突时的哈希表

    本例的平均查找长度 ASL=(1*7+2*4+3*1)=1.5

    4.建立公共溢出区

    这种方法的基本思想是:将哈希表分为基本表溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表



     hash算法就学习总结到这里了,今天度过了22岁生日,晚上还是坚持完成了写这篇博客,今天暂时不写了,明天来总结Java中的hashcode和equals方法,

    转载请指明出处http://blog.csdn.net/tanggao1314/article/details/51457585

    参考资料

    大话数据结

    算法导论


    展开全文
  • hash算法

    2013-09-17 17:25:50
    * Hash算法大全 * 推荐使用FNV1算法 * * @algorithm None * @author Goodzzp 2006-11-20 * @lastEdit Goodzzp 2006-11-20 * @editDetail Create */ public class HashAlgorithms { /** * 加法hash * ...
    /**
     * Hash算法大全<br>
     * 推荐使用FNV1算法
     * 
     * @algorithm None
     * @author Goodzzp 2006-11-20
     * @lastEdit Goodzzp 2006-11-20
     * @editDetail Create
     */
    public class HashAlgorithms {
    
    	/**
    	 * 加法hash
    	 * 
    	 * @param key
    	 *            字符串
    	 * @param prime
    	 *            一个质数
    	 * @return hash结果
    	 */
    	public static int additiveHash(String key, int prime) {
    		int hash, i;
    		for (hash = key.length(), i = 0; i < key.length(); i++)
    			hash += key.charAt(i);
    		return (hash % prime);
    	}
    
    	/**
    	 * 旋转hash
    	 * 
    	 * @param key
    	 *            输入字符串
    	 * @param prime
    	 *            质数
    	 * @return hash值
    	 */
    	public static int rotatingHash(String key, int prime) {
    		int hash, i;
    		for (hash = key.length(), i = 0; i < key.length(); ++i)
    			hash = (hash << 4) ^ (hash >> 28) ^ key.charAt(i);
    		return (hash % prime);
    		// return (hash ^ (hash>>10) ^ (hash>>20));
    	}
    
    	// 替代:
    	// 使用:hash = (hash ^ (hash>>10) ^ (hash>>20)) & mask;
    	// 替代:hash %= prime;
    
    	/**
    	 * MASK值,随便找一个值,最好是质数
    	 */
    	static int M_MASK = 0x8765fed1;
    
    	/**
    	 * 一次一个hash
    	 * 
    	 * @param key
    	 *            输入字符串
    	 * @return 输出hash值
    	 */
    	public static int oneByOneHash(String key) {
    		int hash, i;
    		for (hash = 0, i = 0; i < key.length(); ++i) {
    			hash += key.charAt(i);
    			hash += (hash << 10);
    			hash ^= (hash >> 6);
    		}
    		hash += (hash << 3);
    		hash ^= (hash >> 11);
    		hash += (hash << 15);
    		// return (hash & M_MASK);
    		return hash;
    	}
    
    	/**
    	 * Bernstein's hash
    	 * 
    	 * @param key
    	 *            输入字节数组
    	 * @param level
    	 *            初始hash常量
    	 * @return 结果hash
    	 */
    	public static int bernstein(String key) {
    		int hash = 0;
    		int i;
    		for (i = 0; i < key.length(); ++i)
    			hash = 33 * hash + key.charAt(i);
    		return hash;
    	}
    
    	/**
    	 * Universal Hashing
    	 */
    	public static int universal(char[] key, int mask, int[] tab) {
    		int hash = key.length, i, len = key.length;
    		for (i = 0; i < (len << 3); i += 8) {
    			char k = key[i >> 3];
    			if ((k & 0x01) == 0)
    				hash ^= tab[i + 0];
    			if ((k & 0x02) == 0)
    				hash ^= tab[i + 1];
    			if ((k & 0x04) == 0)
    				hash ^= tab[i + 2];
    			if ((k & 0x08) == 0)
    				hash ^= tab[i + 3];
    			if ((k & 0x10) == 0)
    				hash ^= tab[i + 4];
    			if ((k & 0x20) == 0)
    				hash ^= tab[i + 5];
    			if ((k & 0x40) == 0)
    				hash ^= tab[i + 6];
    			if ((k & 0x80) == 0)
    				hash ^= tab[i + 7];
    		}
    		return (hash & mask);
    	}
    
    	/**
    	 * Zobrist Hashing
    	 */
    	public static int zobrist(char[] key, int mask, int[][] tab) {
    		int hash, i;
    		for (hash = key.length, i = 0; i < key.length; ++i)
    			hash ^= tab[i][key[i]];
    		return (hash & mask);
    	}
    
    	// LOOKUP3
    	// 见Bob Jenkins(3).c文件
    
    	// 32位FNV算法
    	static int M_SHIFT = 0;
    
    	/**
    	 * 32位的FNV算法
    	 * 
    	 * @param data
    	 *            数组
    	 * @return int值
    	 */
    	public static int FNVHash(byte[] data) {
    		int hash = (int) 2166136261L;
    		for (byte b : data)
    			hash = (hash * 16777619) ^ b;
    		if (M_SHIFT == 0)
    			return hash;
    		return (hash ^ (hash >> M_SHIFT)) & M_MASK;
    	}
    
    	/**
    	 * 改进的32位FNV算法1
    	 * 
    	 * @param data
    	 *            数组
    	 * @return int值
    	 */
    	public static int FNVHash1(byte[] data) {
    		final int p = 16777619;
    		int hash = (int) 2166136261L;
    		for (byte b : data)
    			hash = (hash ^ b) * p;
    		hash += hash << 13;
    		hash ^= hash >> 7;
    		hash += hash << 3;
    		hash ^= hash >> 17;
    		hash += hash << 5;
    		return hash;
    	}
    
    	/**
    	 * 改进的32位FNV算法1
    	 * 
    	 * @param data
    	 *            字符串
    	 * @return int值
    	 */
    	public static int FNVHash1(String data) {
    		final int p = 16777619;
    		int hash = (int) 2166136261L;
    		for (int i = 0; i < data.length(); i++)
    			hash = (hash ^ data.charAt(i)) * p;
    		hash += hash << 13;
    		hash ^= hash >> 7;
    		hash += hash << 3;
    		hash ^= hash >> 17;
    		hash += hash << 5;
    		return hash;
    	}
    
    	/**
    	 * Thomas Wang的算法,整数hash
    	 */
    	public static int intHash(int key) {
    		key += ~(key << 15);
    		key ^= (key >>> 10);
    		key += (key << 3);
    		key ^= (key >>> 6);
    		key += ~(key << 11);
    		key ^= (key >>> 16);
    		return key;
    	}
    
    	/**
    	 * RS算法hash
    	 * 
    	 * @param str
    	 *            字符串
    	 */
    	public static int RSHash(String str) {
    		int b = 378551;
    		int a = 63689;
    		int hash = 0;
    
    		for (int i = 0; i < str.length(); i++) {
    			hash = hash * a + str.charAt(i);
    			a = a * b;
    		}
    
    		return (hash & 0x7FFFFFFF);
    	}
    
    	/* End Of RS Hash Function */
    
    	/**
    	 * JS算法
    	 */
    	public static int JSHash(String str) {
    		int hash = 1315423911;
    
    		for (int i = 0; i < str.length(); i++) {
    			hash ^= ((hash << 5) + str.charAt(i) + (hash >> 2));
    		}
    
    		return (hash & 0x7FFFFFFF);
    	}
    
    	/* End Of JS Hash Function */
    
    	/**
    	 * PJW算法
    	 */
    	public static int PJWHash(String str) {
    		int BitsInUnsignedInt = 32;
    		int ThreeQuarters = (BitsInUnsignedInt * 3) / 4;
    		int OneEighth = BitsInUnsignedInt / 8;
    		int HighBits = 0xFFFFFFFF << (BitsInUnsignedInt - OneEighth);
    		int hash = 0;
    		int test = 0;
    
    		for (int i = 0; i < str.length(); i++) {
    			hash = (hash << OneEighth) + str.charAt(i);
    
    			if ((test = hash & HighBits) != 0) {
    				hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
    			}
    		}
    
    		return (hash & 0x7FFFFFFF);
    	}
    
    	/* End Of P. J. Weinberger Hash Function */
    
    	/**
    	 * ELF算法
    	 */
    	public static int ELFHash(String str) {
    		int hash = 0;
    		int x = 0;
    
    		for (int i = 0; i < str.length(); i++) {
    			hash = (hash << 4) + str.charAt(i);
    			if ((x = (int) (hash & 0xF0000000L)) != 0) {
    				hash ^= (x >> 24);
    				hash &= ~x;
    			}
    		}
    
    		return (hash & 0x7FFFFFFF);
    	}
    
    	/* End Of ELF Hash Function */
    
    	/**
    	 * BKDR算法
    	 */
    	public static int BKDRHash(String str) {
    		int seed = 131; // 31 131 1313 13131 131313 etc..
    		int hash = 0;
    
    		for (int i = 0; i < str.length(); i++) {
    			hash = (hash * seed) + str.charAt(i);
    		}
    
    		return (hash & 0x7FFFFFFF);
    	}
    
    	/* End Of BKDR Hash Function */
    
    	/**
    	 * SDBM算法
    	 */
    	public static int SDBMHash(String str) {
    		int hash = 0;
    
    		for (int i = 0; i < str.length(); i++) {
    			hash = str.charAt(i) + (hash << 6) + (hash << 16) - hash;
    		}
    
    		return (hash & 0x7FFFFFFF);
    	}
    
    	/* End Of SDBM Hash Function */
    
    	/**
    	 * DJB算法
    	 */
    	public static int DJBHash(String str) {
    		int hash = 5381;
    
    		for (int i = 0; i < str.length(); i++) {
    			hash = ((hash << 5) + hash) + str.charAt(i);
    		}
    
    		return (hash & 0x7FFFFFFF);
    	}
    
    	/* End Of DJB Hash Function */
    
    	/**
    	 * DEK算法
    	 */
    	public static int DEKHash(String str) {
    		int hash = str.length();
    
    		for (int i = 0; i < str.length(); i++) {
    			hash = ((hash << 5) ^ (hash >> 27)) ^ str.charAt(i);
    		}
    
    		return (hash & 0x7FFFFFFF);
    	}
    
    	/* End Of DEK Hash Function */
    
    	/**
    	 * AP算法
    	 */
    	public static int APHash(String str) {
    		int hash = 0;
    
    		for (int i = 0; i < str.length(); i++) {
    			hash ^= ((i & 1) == 0) ? ((hash << 7) ^ str.charAt(i) ^ (hash >> 3))
    					: (~((hash << 11) ^ str.charAt(i) ^ (hash >> 5)));
    		}
    
    		// return (hash & 0x7FFFFFFF);
    		return hash;
    	}
    
    	/* End Of AP Hash Function */
    
    	/**
    	 * JAVA自己带的算法
    	 */
    	public static int java(String str) {
    		int h = 0;
    		int off = 0;
    		int len = str.length();
    		for (int i = 0; i < len; i++) {
    			h = 31 * h + str.charAt(off++);
    		}
    		return h;
    	}
    
    	/**
    	 * 混合hash算法,输出64位的值
    	 */
    	public static long mixHash(String str) {
    		long hash = str.hashCode();
    		hash <<= 32;
    		hash |= FNVHash1(str);
    		return hash;
    	}
    }
    


    展开全文
  • 在讲redis的hash slot之前,先讲一讲最常见的hash算法和一致性hash算法做个比较 hash算法 最常见的hash算法就是直接取模了,假如这是我们有三台redis服务器,这时来了一个key,我们会先对key进行hash计算,然后...

    这篇文章我们来了解一下各种数据分布算法,以redis作为数据分布的机器来举例

    1. hash算法
      首先是最简单的hash算法,假如我们有三台redis服务器,这时来了一个key,我们会先对key进行hash计算,然后根据机器数量进行取模,得出的结果就是机器的一个编号,就将key发送到这台机器上去
      如果这时突然有一台机器宕机了,那么一时间这台机器上所有的缓存都失效了,那么请求就会直接打到MySQL上,如果数据量太大,会导致MySQL也宕机
      即使MySQL抗住了这些请求,之后的key在进行hash算法的时候,也需要重新进行取模,因为机器的数量变了,从而导致大部分的缓存都会失效,大量的key重新分配
      hash算法
    2. 一致性hash算法
      一致性hash算法有一个hash环的概念,每个key的hash值会对2^32 进行取模,最终保证每个计算出的值都在这个hash环上
      而我们的redis机器也会根据ip地址的hash值对2^32进行取模,最后也是在这个hash环上,计算出的key值在hash环上顺时针找到的第一个机器,key就会发到这台机器上
      在遇到上面的hash算法的节点宕机问题时,原先节点上的key会顺时针的找到下一个节点,只有原先在这个节点上的key会失效,大部分的key并不会受到影响
      这里还有一个问题就是hash环的数据倾斜问题,当节点都集中在hash环的某一块时,会导致大量的key都会集中在其中的某一个机器上,极端情况下,如果这个机器宕机了,同样会造成系统崩溃
      为了解决这个问题,会使用虚拟节点,将各个机器虚拟出一些节点出来,均匀的分布在hash环上,让key顺时针可以找到这些虚拟节点,从而使得key更加均匀的分布到各台机器上
      一致性hash算法
    3. hash slot算法
      redis cluster中使用的是hash slot算法,redis cluster有固定的16384个hash slot,对每个key计算CRC16值,然后对16384取模,就得到了每个key对应的hash slot,即HASH_SLOT = CRC16(key) mod 16384
      redis cluster中的master都会持有一部分的hash slot,类似于分布式存储,如果你的集群有三个节点,那么每个节点都会有5000多个hash slot
      当节点增加或者减少的时候,hash slot也会对应的移动,并且移动hash slot的成本非常低,这种方式减轻了其他hash算法重新计算hash值的开销,且使用CRC16算法计算出来的key可以在16384个槽中均匀分布
      当key写入到了某个节点的hash slot,之后读取的时候,如果正好读取到了这个节点,那么就直接处理后返回即可;如果读取的key在其他节点的hash slot上时,就返回一个moved error,让客户端重定向到hash slot所在的节点去读取数据
      每次读取缓存的时候都是去找的hash slot,即使找的节点不对,也会重定向到新的节点去寻找,不会造成缓存失效的问题
      hash slot
    展开全文
  • HASH 算法

    千次阅读 2012-06-30 15:16:52
    Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间...
  • Hash算法和一致性Hash算法

    千次阅读 2019-06-20 18:34:09
    Hash算法在路由算法应用中,为了保证数据均匀的分布,例如有3个桶,分别是0号桶,1号桶和2号桶;现在有12个球,怎么样才能让12个球平均分布到3个桶中呢?使用Hash算法的做法是,将12个球从0开始编号,得到这样的一个...
  • 分布式数据存储的核心算法,数据分布的算法主要有三种算法:hash算法、一致性hash算法、hash slot算法。 hash算法 -> 一致性hash算法(memcached使用) -> hash slot算法(redis cluster 使用) ​ redis ...
  • Hash算法及其应用

    2019-08-30 14:43:40
    Hash算法 其实hash和散列表示的一个意思,所以hash表就是散列表,hash算法就是散列算法,hash函数就是散列函数。 这说的hash算法,什么是hash算法?有一句很easy的总结:将任意长度的二进制串映射为固定长度的二...
  • Hash算法特点

    千次阅读 2020-04-15 16:22:47
    2.2 Hash算法有什么特点 一个优秀的 hash 算法,将能实现: 正向快速:给定明文和 hash 算法,在有限时间和有限资源内能计算出 hash 值。 逆向困难:给定(若干) hash 值,在有限时间内很难(基本不可能)逆推出...
  • 一致性hash算法

    千次阅读 2019-04-27 22:47:14
    一致性hash算法Hash算法的作用Hash算法的冲突一致性hash算法一致性hash算法的原理容错性虚拟节点 Hash 算法也叫做散列算法,他可以让任意长度的数据M映射成为长度固定的值H。 Hash算法的作用 Hash算法的第一个作用...
  • 浅显理解 hashcode 和 hash 算法

    万次阅读 多人点赞 2017-12-30 23:06:07
    HashMap 的 hash 算法的实现原理(为什么右移 16 位,为什么要使用 ^ 位异或) HashMap 为什么使用 &amp; 与运算代替模运算? HashMap 的容量为什么建议是 2的幂次方? 我们自定义 HashMap 容量最好是多少? 前
  • Hash算法详解

    万次阅读 2018-06-26 20:16:00
    Hash算法,简称散列算法,也成哈希算法(英译)。是将一个大文件映射成一个小串字符。
  • GeoHash 算法

    千次阅读 2019-04-26 01:08:26
    业界比较通用的地理位置距离排序算法是 GeoHash 算法,Redis 也使用 GeoHash 算法。GeoHash 算法将二维的经纬度数据映射到一维的整数,这样所有的元素都将在挂载到一条线上,距离靠近的二维坐标映射到一维后的点之间...
  • 一致性hash算法是在redis 分片中使用,hash槽在redis cluster(集群)中使用 hash槽: redis集群(cluster)并没有使用一致性hash算法,而是使用hash槽(slot)这个概念, 因为一致性hash算法对于数据的分布,节点...
  • Hash算法与加密算法对比

    千次阅读 2018-05-31 11:09:00
    转载自:https://blog.csdn.net/lucky_greenegg/article/details/51897647HASH 算法是一种消息摘要算法,不是一种加密算法,但由于其单向运算,具有一定的不可逆性,成为加密算法中的一个构成部分,完整的加密机制不...
  • hash算法比较

    千次阅读 2017-01-13 17:42:37
    常用的hash算法有BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等。
  • FNV Hash算法

    千次阅读 2015-06-11 18:41:22
    FNV Hash算法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 25,193
精华内容 10,077
关键字:

hash算法