精华内容
下载资源
问答
  • 常见散列函数

    2020-11-02 16:44:49
    MD5(Message Digest Algorithm 5):是RSA数据安全公司开发... MAC(Message Authentication Code):消息认证代码,是一种使用密钥的单向函数,可以用它们在系统上或用户之间认证文件或消息,常见的是HMAC(用于消..
    • MD5(Message Digest Algorithm 5):是RSA数据安全公司开发的一种单向散列算法,MD5被广泛使用,可以用来把不同长度的数据块进行暗码运算成一个128位的数值。

    • SHA(Secure Hash Algorithm)这是一种较新的散列算法,可以对任意长度的数据运算生成一个160位的数值。

    • MAC(Message Authentication Code):消息认证代码,是一种使用密钥的单向函数,可以用它们在系统上或用户之间认证文件或消息,常见的是HMAC(用于消息认证的密钥散列算法)。

    • CRC(Cyclic Redundancy Check):循环冗余校验码,CRC校验由于实现简单,检错能力强,被广泛使用在各种数据校验应用中。占用系统资源少,用软硬件均能实现,是进行数据传输差错检测地一种很好的手段(CRC 并不是严格意义上的散列算法,但它的作用与散列算法大致相同,所以归于此类)。

    展开全文
  • 哈希 哈希(Hash)也称为散列,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,这个输出值就是散列值。 哈希算法 哈希表 ...这个映射函数叫做散列函数,存放记录的数组叫做散列表。 ...

    1 散列函数的设计原则

      作为好的散列函数hash(),首先必须具有确定性。无论所含数据项如何,词条E在散列表中的映射地址hash(E.key)必须完全取决于其关键码key。其次映射过程资深不能过于复杂,唯此房能保证散列地址的计算可快速完成,从而保证查询或修改操作整体的O(1)期望执行时间。再次,所有关键码经映射后尽量覆盖整个地址空间[0,M),方可充分利用有限空间。也就是说,函数hash()最好是满射。
      由于定义域规模远远大于取值域规模,hash()不可能是单射。这就意味着,不同的词条可能被映射到同一散列地址(散列冲突)难以避免。所以设计和选择散列函数阶段要做好充分的考量,以便尽可能地降低冲突发生的概率
      在此,最为重要的一条原则就是,关键码映射到各桶的概率应尽量相等,这等效于将关键码“均匀地”映射到散列地址空间,从而避免导致极端低效的情况,比如,关键码集中分布于某一区间,而加剧散列冲突。
      总而言之,随机越强、规律性越弱的散列函数越好

    2 常见设计方法

    2.1 除余法

    设计方法

      符合上述设计原则的一种最简单的映射方法,就是将散列表长度M取作素数,并将关键码key映射至key关于M整除的余数:
        hash(key) = key mod M

    一般散列表的长度M与词条关键码间隔T之间的最大公约数越大,发生冲突的可能性也将越大,因此将M取作素数

    实例分析

      以校园电话簿为例,取M=90001,则以下关键码{6278-5001,5153-1876,6277-0211}—>{54304,51304,38514}
    在这里插入图片描述

    不足之处

      以素数为表长的除余法尽管可在一定程度上保证词条的均匀分布,但从关键码空间到散列地址空间映射的角度看,依然残留某种连续性。比如,相邻关键码所对应的散列地址,总是彼此相邻;极小的关键码,通常都被集中映射到散列表的起始区段一一其中特别是0值居然是一个“不动点”,其散列地址总是0。

    2.2 MAD法

    设计方法

      所谓的MAD法是multply-add-divide的缩写,其将关键码key映射至key与常数a之积再于常数b之和对M求余数(M的取值方法与除余法相同):
        hash(key) = (a x key + b) mod M
      MAD法尽管运算量略有增加,但只要常数a和b选取得当可以很好地克服除余法原有的连续性缺陷。

    实例分析

      当取a=31和b=2时,关键码集合a{2011,2012,2013,2014,2015,2016},经过散列函数得出集合b{1,4,6,9,12,15}。连续的关键码经过散列后并不连续,各关键码散列的均匀性和随机性有了很大的改善。
    在这里插入图片描述

    2.3 数字分析法

    设计方法

      数字分析法从关键码key特定进制的展开中抽取出特定的若干位,构成一个整型地址。比如,取十进制展开中奇位数,则有
        hash(123456789) = 13579

    2.4 平方取中法

    设计方法

      平方取中法,从关键码key的平方的十进制或二进制展开中取居中的若干位,构成一个整型地址。比如,去平方后十进制展开中居中的三位,则有
        hash(123) = 512 (1232=15129)

    2.5 折叠法

    设计方法

      折叠法,是将关键码的十进制或二进制展开分割成等宽的若干段,取其总和作为散列地址。比如,若以三个数位为分割单位,则有
        hash(123456789) = 123 + 456 + 789 = 1368

    2.6 位异或法

    设计方法

      位异或法,是将关键码的二进制展开分割成等宽的若干段,经异或运算得到散列地址。比如,仍以三个数位为分割单位,则有
        hash(411) = hash(110011011b) = 110 ^ 011 ^ 011 = 110b = 6

    3 散列冲突解决方案

    冲突的普遍性

      无论散列函数设计得如何巧妙,也不可能保证不同的关键码之间互不冲突。事实上在实际应用中,不发生任何冲突的概率远远低于我们的想象。我们来看下面这个例子,某课堂的所有学生中,是否有某两位生日相同?需要多少学生才能是这样的概率大于50%呢?
      不难证明上述的答案是,只要学生人数大于23,生日相同的概率将大于50%。若将全年各天视作365个桶,并将学生视作词条,则可按生日将他们组织为散列表,则该问题便可转化为:若长度为365的散列表中存在n个词条,则至少发生一次冲突的概率是多大?由此可见,解决散列冲突是涉及散列表中非常重要的部分。

    3.1 多槽位法

      最简单的解决冲突策略是,将彼此冲突的每一组词条组织为一个小规模的子词典,分别存放他们共同对应的桶单元。多槽位法是将各桶细分为更小的槽位,每一组槽位使用向量存储数据。
    在这里插入图片描述
      多槽位法优点是速度快,但是使用向量需要提前申请空间,导致空间利用率低。

    3.2 独立链法

      独立链法与多槽位法是同样的策略,不过子词典采用链表结构。
    在这里插入图片描述
      采用独立链法可以有效避免向量的空间浪费问题,缺点是操作时间增加。

    3.3 公共溢出区法

      公共溢出区法的思路是,在原散列表职位另设一个词典结构,相当于一个公共缓存区,一旦发生冲突就将该词条转存至公共缓存区。
    在这里插入图片描述
      该策略构思简单、易于实现,在冲突不甚频繁的场合不失为一种好的选择。

    闭散列策略

      尽管逻辑结构而言,独立链等策略便捷而紧凑,但绝非上策。比如需要引进次级关联结构,在查找过程中将需要做更多地I/O操作,时间成本大大增加。实际上仅仅依靠基本的散列表结构就地解决冲突,反而是更好的选择。
      闭散列策略,即当词条存在冲突时,只允许在散列表内部为其寻找另一空桶。因闭散列策略不得使用附加控件,装填因子需要适度降低,通常取λ≤0.5

    3.4 线性试探法

      线程试探法采用闭散列策略,当关键码key词条插入时,发现桶单元hash(key)已被占用,则转而试探下一个桶单元hask(key)+1, 如此不断试探,直到发现一个可用空桶。当然为确保桶地址的合法,最后还需要统一对M取模。
      在查找过程中只有查找到对应关键码或第一个空桶才停止,否则须转入下一个桶单元继续试探。
      在删除时采用假删除策略,将被删除的桶单元关键码改为特定的数(如-1)表示删除,以便查找时不至于找不到关键码。
    在这里插入图片描述
      线性试探法在物理上保持了一定的连贯性,具有良好的数据局部性,故系统缓存的作用可以充分发挥。尽管闭散列策略同时也会一定程度上增加冲突发生的可能,但只要散列表的规模不是很小,装填因子不大,则相对于I/O的负担降低而言,这些问题都微不足道。

    3.5 平方试探法

      由于数据的局部性,数据往往会聚集在散列表中的某个地方,采用MAD散列函数可缓解一定的聚集现象。而平方试探法,则是更为有效的一种方法。
      在发生冲突时,按如下规则确定第j次试探的桶地址:
        ( hash(key) + j2 ) mod M   (j=0,1,2……)
      平方试探法的删除和查找策略与线性试探法大致相同。
    在这里插入图片描述
      平方试探法能很好解决词条的聚集现象,但线性试探法中,只要散列表中尚有空桶,则试探过程必将会终止。而平方试探法是否能保证这一点呢?
      事实上平方试探法无法保证有空桶必将终止,但是能保证散列表长度M为素数且装填因子λ≤50%时,必将终止于某个空桶。

    3.6 再散列法

      在散列法也是一个解决聚集现象的有效办法。为此,需要选取一个适宜的二级散列函数hash2(),一旦在插入词条时发现桶单元hash(key)已被占用,则以hash2(key)为偏移增量继续尝试,直到发现一个空桶。如此,被尝试的桶地址依次应为:
        [ hash(key) + 1 x hash2(key) ] % M
        [ hash(key) + 2 x hash2(key) ] % M
        [ hash(key) + 3 x hash2(key) ] % M
      可见再散列法也是一种线性试探,只不过不同的key的增量不同。

    本文内容来自 邓俊辉老师的 《数据结构与算法》

    展开全文
  • 常见散列函数

    2017-09-17 17:49:00
    散列函数 在以下的讨论中,我们假设处理的是值为整型的关键码,否则我们总可以建立一种关键码与正整数之间的一一对应关系,从而把该关键码的检索转化为对与其对应的正整数的检索;同时,进一步假定散列函数的值落...
    散列函数
     
    在以下的讨论中,我们假设处理的是值为整型的关键码,否则我们总可以建立一种关键码与正整数之间的一一对应关系,从而把该关键码的检索转化为对与其对应的正整数的检索;同时,进一步假定散列函数的值落在0到M-1之间。散列函数的选取原则是:运算尽可能简单;函数的值域必须在散列表的范围内;尽可能使得结点均匀分布,也就是尽量让不同的关键码具有不同的散列函数值。需要考虑各种因素:关键码长度、散列表大小、关键码分布情况、记录的检索频率等等。下面我们介绍几种常用的散列函数。
    1、除余法
    顾名思义,除余法就是用关键码x除以M(往往取散列表长度),并取余数作为散列地址。除余法几乎是最简单的散列方法,散列函数为: h(x) = x mod M。
     
    2、乘余取整法
    使用此方法时,先让关键码key乘上一个常数A (0< A < 1),提取乘积的小数部分。然后,再用整数n乘以这个值,对结果向下取整,把它做为散列的地址。散列函数为: hash ( key ) = _LOW( n × ( A × key % 1 ) )。 其中,“A × key % 1”表示取 A × key 小数部分,即: A × key % 1 = A × key - _LOW(A × key), 而_LOW(X)是表示对X取下整。
     
    3、平方取中法
    由于整数相除的运行速度通常比相乘要慢,所以有意识地避免使用除余法运算可以提高散列算法的运行时间。平方取中法的具体实现是:先通过求关键码的平方值,从而扩大相近数的差别,然后根据表长度取中间的几位数(往往取二进制的比特位)作为散列函数值。因为一个乘积的中间几位数与乘数的每一数位都相关,所以由此产生的散列地址较为均匀。
     
    4、数字分析法
    设有 n 个 d 位数,每一位可能有 r 种不同的符号。这 r 种不同的符号在各位上出现的频率不一定相同,可能在某些位上分布均匀些,每种符号出现的几率均等; 在某些位上分布不均匀,只有某几种符号经常出现。可根据散列表的大小,选取其中各种符号分布均匀的若干位作为散列地址。
     
    5、基数转换法
     
    将关键码值看成另一种进制的数再转换成原来进制的数,然后选其中几位作为散列地址。
     
    6、折叠法
    有时关键码所含的位数很多,采用平方取中法计算太复杂,则可将关键码分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为散列地址,这方法称为折叠法。
     
    7、ELFhash字符串散列函数
    ELFhash函数在UNIX系统V 版本4中的“可执行链接格式”( Executable and Linking Format,即ELF )中会用到,ELF文件格式用于存储可执行文件与目标文件。ELFhash函数是对字符串的散列。它对于长字符串和短字符串都很有效,字符串中每个字符都有同样的作用,它巧妙地对字符的ASCII编码值进行计算,ELFhash函数对于能够比较均匀地把字符串分布在散列表中。

    转载于:https://www.cnblogs.com/anzhi/p/7536448.html

    展开全文
  • 1、散列表(hash table) ,也叫哈希表,是根据关键码而直接进行访问的数据结构。也就是说,它通过把关键码映射到表中一个位置 来访问记录,以加快查找的速度...这个映射函数叫做散列函数,存放记录的数组叫做散列表。

    1、散列表(hash table) ,也叫哈希表,是根据关键码而直接进行访问的数据结构。也就是说,它通过把关键码映射到表中一个位置

    来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

    2、若结构中存在关键码为x的记录,则必定在hash(x)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系hash

    为散列函数(hash function),按这个思想建立的表为散列表。

    3、散列函数是一个压缩映象函数。关键码集合比散列表地址集合大得多。因此有可能经过散列函数的计算,把不同的关键码映射到

    同一个散列地址上,这就产生了冲突 (Collision)。即key1≠ key2,而hash(key1)=hash(key2),这种现象称冲突。我们将key1与key2称

    做同义词。

    4、由于关键码集合比地址集合大得多,冲突很难避免。所以对于散列方法,需要讨论以下两个问题:

    对于给定的一个关键码集合,选择一个计算简单且地址分布比较均匀的散列函数,避免或尽量减少冲突;

    拟订解决冲突的方案。

    5、散列函数的选择有两条标准:简单和均匀

    简单指散列函数的计算简单快速,能在较短时间内计算出结果。

    均匀指散列函数计算出来的地址能均匀分布在整 个地址空间。若key是从关键字码集合中随机抽取的一个关键码,散列函数能

    以等概率均匀地分布在表的地址集{0,1,…,m-1}上,以使冲突最小化。

    二,散列函数的构造方法

    (一)、直接定址法

    此类函数取关键码的某个线性函数值作为散列地址:hash ( key ) = a * key + b      { a, b为常数 }

    这类散列函数是一对一的映射,一般不会产生冲突。但是,它要求散列地址空间的大小与关键码集合的大小相同。


    (二)、数字分析法

    构造:对关键字进行分析,取关键字的若干位或其组合作哈希地址。
    适于关键字位数比哈希地址位数大,且可能出现的关键字事先知道的情况。

    例:  有80个记录,关键字为8位十进制数,哈希地址为2位十进制数

    (三)、平方取中法

    取关键字平方后中间几位作哈希地址。适于关键字位数不定情况。

    具体方法:先通过求关键字的平方值扩大相近数的差别,然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间

    几位数和乘数的每一位都相关,所以由此产生的散列地址较为均匀

    (四)、折叠法

    此方法把关键码自左到右分成位数相等的几部分,每一部分的位数应与散列表地址位数相同,只有最后一部分的位数可以短一些。

    把这些部分的数据叠加起来,就可以得到具有该关键码的记录的散列地址。有两种叠加方法:

    移位法 — 把各部分的最后一位对齐相加;

    分界法 — 各部分不折断,沿各部分的分界来回折叠,然后对齐相加,将相加的结果当做散列地址。

    一般当关键码的位数很多,而且关键码每一位上数字的分布大致比较均匀时,可用这种方法得到散列地址。

    (五)、随机数法

    选择一个随机函数,取关键字的随机函数值为它的散列地址,即 hash(key) = random(key) ;其中random为伪随机函数,但要保证函

    数值是在0到m-1之间。


    (六)、除留余数法

    设散列表中允许的地址数为 m, 散列函数为:

     hash ( key ) = key % p    p <=  m

    若p取100,则关键字159、259、359互为同义词。我们选取的p值应尽可能使散列函数计算得到的散列地址与各位相关,根据经

    验,p最好取一个不大于 m,但最接近于或等于 m 的质数 p,  或选取一 个不小于 20 的质因数的合数作为除数(比如8 = 2*2*2,2 是 

    8 的质因数,8 是合数)

    示例:有一个关键码 key = 962148,散列表大小 m = 25,即 HT[25]。取质数 p= 23。散列函数 hash ( key ) = key % p。则散列地址

    hash ( 962148 ) = 962148 % 23 = 12

    可以按计算出的地址存放记录。需要注意的是,使用上面的散列函数计算出来的地址范围是 0到 22,因此,从23到24这几个散列地

    址实际上在一开始是不可能用散列函数计算出来的,只可能在处理溢出时达到这些地址。


    (七)、乘余取整法

    使用此方法时,先让关键码 key 乘上一个常数  A (0 < A < 1),提取乘积的小数部分。然后,再用整数 n 乘以这个值,对结果向下取

    整,把它做为散列的地址。


    常见散列函数 请查看 链接:http://blog.csdn.net/makenothing/article/details/40894603

    展开全文
  • 单向散列函数

    万次阅读 2020-01-16 11:15:57
    文章目录单向散列函数单向散列函数的性质单向散列函数的实现对单向散列算法的攻击 单向散列函数 在介绍单向散列函数之前,我们先了解一下什么情况下需要使用到单向散列函数。 如果你需要从国外的网站上下载一个软件...
  • 若不同的关键字通过散列函数映射到同⼀个值,则称它们为“同义词” 通过散列函数确定的位置已经存放了其他元素,则称这种情况为“冲突” (二)处理冲突的方法——拉链法 用拉链法(又称链接法、链地址法)处理...
  • 本文探讨拉链表解决哈希冲突的方式和几种常见散列函数。  首先,什么是散列表?  对于一个数组,我们在O(1)时间复杂度完成可以完成其索引的查找,现在我们想要存储一个key value的键值对,我们可以根据key生成...
  • 漫谈散列函数

    千次阅读 2020-07-30 16:59:32
    简介:说到散列,一般对应于散列表(哈希表)和散列函数。 我们今天不谈哈希表,仅谈下散列函数。 说到散列,一般对应于散列表(哈希表)和散列函数。我们今天不谈哈希表,仅谈下散列函数。定义引一段百度百科关于...
  • 概观散列函数

    2018-07-31 20:50:00
    这篇文章里我们将要讨论一般的实现散列思想最重要的技术——散列函数的设计,这里会讨论一些常见散列函数。但他们自存在之初就一个固有的缺陷:无法杜绝的冲突,更糟糕的是从理论上讲这一缺陷无法根本地消除。...
  • 几种常见的哈希函数(散列函数)构造方法 直接定址法 取关键字或关键字的某个线性函数值为散列地址。 即 H(key) = key 或 H(key) = a*key + b,其中a和b为常数。 比如 除留余数法 取关键字被某个不大于散...
  • 目录1、基本概念:2、完美散列函数(1)概念:(2)常见散列函数:(3)python自带的散列函数库:(4)用途:3、区块链技术(1)概念:(2)工作量证明:(3)有效散列函数值难算出的原因:(4)为什么要抢先?...
  • 散列函数的构造方法

    2020-03-24 16:46:02
    散列函数的构造方法
  • 散列函数

    2015-05-23 21:39:39
    常见的Hash算法 General Hash Function Source Code CGeneral Hash Function Source Code CGeneral Hash Function Source Code Pascal Object PascalGeneral Hash Function Source Code JavaGeneral Hash
  • 参考来源 ...什么是单向散列函数 单向散列函数,又被称为消息摘要函数,哈希函数。...常见的几种单向散列函数 1.MD4、MD5 产生128bit的散列值,MD就是Message Digest的缩写,目前已经不安全。 2.SHA-1
  • 单向散列函数(one-way hash function)是指对不同的输入值,通过单向散列函数进行计算,得到固定长度的输出值。这个输入值称为消息(message),输出值称为散列值(hash value)。 单向散列函数也被称为消息摘要...
  • 散列函数,(也叫哈希函数,台湾称杂凑函数)是一个将(通常)较大的定义域内容映射到一个(通常)较小的值域内的函数,散列函数是一个公开的函数,它将任意长的信息映射到一个固定长度的信息的函数。 构造散列函数的目标是...
  • 一个好的散列函数一般要考虑以下两个因素:1、计算简便,以便提高转换速度 2、关键词对应的地址空间分布均匀,以尽量减少冲突散列函数的常用方法关键词为数字1、直接定址法取关键词的某个线性线性函数作为散列地址...
  • Hash(散列函数),一般翻译做"散列",也直接音译为"哈希"的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。由于散列函数的应用的多样性,它们经常...
  • 散列函数的实现很多种,其中一种常见散列函数即 除法散列法,h(k) = k mod m,通过取 k 除以 m 的余数,将关键字 k 映射到 m 个槽上。由于只需做一次除法操作,所以除法散列法是非常快的。 当我们使用除法散列...
  • 常用的构造散列函数的方法

    千次阅读 2019-05-08 21:30:14
    常用的构造散列函数的方法 散列函数能使对一个数据序列的访问过程更加迅速有效,通过散列函数,数据元素将被更快地定位: 1. 直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a?...
  • 一、散列表基本概念 1、散列表(hash table) ,也叫哈希表,是根据关键码而直接进行访问的数据结构。也就是说,它通过把关键码映射到表中一个位置 来访问记录,以加快查找的速度。...为散列函数
  • 构造散列函数的方法

    千次阅读 热门讨论 2016-09-24 16:13:18
    好的散列函数要求:(1)花费时间段,计算简单。(2)计算的散列地址分布均匀,提高地址的利用率。 1. 直接定址法  取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b,其中a和b...
  • 散列函数的应用

    2020-05-29 18:32:17
    前身:对于在M个预查询的数中每个数在N个数中出现的次数类型题目,空间换时间的方法来减少时间复杂度,用一个标记函数标记好M中每个元素,然后在N中输入时,直接把输入的数作为标记函数的下标对这个数的性质进行统计...
  • 单向散列函数 文章目录单向散列函数前言单向散列函数原理1.场景举例2.函数性质3.函数应用实现方法1.MD算法家族2.SHA算法家族SHA2561.预处理2.哈希计算mbedtls示例1.接口描述 前言 我本人是一名物联网代码搬运工,...
  • 散列函数是区块链最为基础部分。在密码体系中地位也十分重要。Filecoin作为新一代的区块链,在散列函数采用上也十分大胆
  • 1.单向散列函数One-way hash function 1.1 定义 1.2 术语 1.3 特性 1.3.1 散列值长度固定 1.3.2 散列值计算快速 1.3.3 散列值抗碰撞性极强 1.3.4 散列值计算是单向不可逆 1.4 应用 1.5 常见类型 2.go语言...
  • 散列函数安全性扩展

    2019-09-29 02:01:21
    散列函数的具体应用: 1,数据校验 HASH函数类似数据冗余校验类似的功能,但是它比简单的冗余校验碰撞的概率要小得多,顾而在现在密码学中总是用HASH来做关键数据的验证。 2,单向性的运用 利用HASH函数的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 32,197
精华内容 12,878
关键字:

常见的散列函数有哪些