精华内容
下载资源
问答
  • 哈希运算原理
    2018-04-01 12:18:29

    一.概念

    哈希表就是一种以 键-值(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所示。

     

    0      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)

     

     

    0        1       2      3      4      5       6      7      8       9      10    

     

     

     

     

    47

    26

    60

    69

     

     

     

     

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

     

     

    0        1       2      3      4      5       6      7      8       9      10    

     

     

     

    69

    47

    26

    60

     

     

     

     

     

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

     

     

    0        1       2      3      4      5       6      7      8       9      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个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

    更多相关内容
  • 哈希算法原理和实现

    万次阅读 多人点赞 2020-09-13 10:32:32
    哈希算法原理和实现 前言 当我们在编程过程中,往往需要对线性表进行查找操作。在顺序表中查找时,需要从表头开始,依次遍历比较a[i]与key的值是否相等,直到相等才返回索引i;在有序表中查找时,我们经常使用的是二...

    哈希算法原理和实现

    前言

    当我们在编程过程中,往往需要对线性表进行查找操作。在顺序表中查找时,需要从表头开始,依次遍历比较a[i]与key的值是否相等,直到相等才返回索引i;在有序表中查找时,我们经常使用的是二分查找,通过比较key与a[i]的大小来折半查找,直到相等时才返回索引i。最终通过索引找到我们要找的元素。
       但是,这两种方法的效率都依赖于查找中比较的次数。我们有一种想法,能不能不经过比较,而是直接通过关键字key一次得到所要的结果呢?这时,就有了散列表查找(哈希表)。

    1、什么是哈希表

    要说哈希表,我们必须先了解一种新的存储方式—散列技术。
        散列技术是指在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每一个关键字都对应一个存储位置。即:存储位置=f(关键字)。这样,在查找的过程中,只需要通过这个对应关系f 找到给定值key的映射f(key)。只要集合中存在关键字和key相等的记录,则必在存储位置f(key)处。我们把这种对应关系f 称为散列函数或哈希函数。
        按照这个思想,采用散列技术将记录存储在一块连续的存储空间中,这块连续的存储空间称为哈希表。所得的存储地址称为哈希地址或散列地址。

    2、哈希表查找步骤

    ①、存储数据时,将数据存入通过哈希函数计算所得哪那个地址里面。
       ②、查找时,使用同一个哈希函数通过关键字key计算出存储地址,通过该地址即可访问到查找的记录。

    3、哈希冲突

    在理想的情况下,每一个 关键字,通过哈希函数计算出来的地址都是不一样的。但是在实际情况中,我们常常会碰到两个关键字key1≠key2,但是f(key1) = f(key2), 这种现象称为冲突,并把key1和key2称为这个散列函数的同义词。
      冲突的出现会造成查找上的错误,具体解决方法会在后文提到。

    4、哈希函数的构造方法

    (1)原则

    ①、计算简单;
      ②、散列地址分布均匀。

    (2)构造方法

    ①、直接定址法:不常用
        取关键字或关键字的某个线性函数值为哈希地址:
        即:H(key) = key 或 H(key) = a*key+b
        优点:简单,均匀,不会产生冲突;
        缺点:需要实现直到关键字的分布情况,适合查找表比较小且连续的情况。
      
      ②、数字分析法
       数字分析法用于处理关键字是位数比较多的数字,通过抽取关键字的一部分进行操作,计算哈希存储位置的方法。
       例如:关键字是手机号时,众所周知,我们的11位手机号中,前三位是接入号,一般对应不同运营商的子品牌;中间四位是HLR识别号,表示用户号的归属地;最后四位才是真正的用户号,所以我们可以选择后四位成为哈希地址,对其在进行相应操作来减少冲突。
       数字分析法适合处理关键字位数比较大的情况,事先知道关键字的分布且关键字的若干位分布均匀。
       
      ③、平方取中法
       具体方法很简单:先对关键字取平方,然后选取中间几位为哈希地址;取的位数由表长决定,适用于不知道关键字的分布,而位数又不是很大的情况。
      
      ④、折叠法
       将关键字分成位数相同的几部分(最后一部分位数 可以不同),然后求这几部分的叠加和(舍去进位),并按照散列表的表长,取后几位作为哈希地址。
       适用于关键字位数很多,而且关键字每一位上数字分布大致均匀。
      
       ⑤、除留余数法
       此方法为最常用的构造哈希函数方法。对于哈希表长为m的哈希函数公式为:
       f(key) = key mod p (p <= m)
       此方法不仅可以对关键字直接取模,也可以在折叠、平方取中之后再取模。
       所以,本方法的关键在于选择合适的p,若是p选择的不好,就可能产生 同义词;根据前人经验,若散列表的表长为m,通常p为小于或等于表长(最好接近m)的最小质数或不包含小于20质因子的合数。
      
       ⑥、随机数法
       选择一个随机数,取关键字的随机函数值作为他的哈希地址。
       即:f(key) = random (key)
       当关键字的长度不等时,采用这个方法构造哈希函数较为合适。当遇到特殊字符的关键字时,需要将其转换为某种数字。

    (3)、参考因素

    在实际应用过程中,应该视不同的情况采用不同的哈希函数。下列是一些参考因素:
        ①计算哈希地址所需的时间;
        ②关键字的长度;
        ③哈希表的大小;
        ④关键字的分布情况;
        ⑤查找的频率。
       选择哈希函数时,我们应该综合以上因素,选择合适的构建哈希函数的方法。

    5、哈希冲突的解决

    前文提到,哈希冲突不能避免,所以我们需要找到方法来解决它。
       哈希冲突的解决方案主要有四种:开放地址法;再哈希;链地址法;公共溢出区法。

    (1)、开放地址法

    开放地址法就是指:一旦发生了冲突就去寻找下一个空的哈希地址,只要哈希表足够大,空的散列地址总能找到,并将记录存入。
       公式:Hi=(H(*key) + Di) mod m (i = 1,2,3,….,k k<=m-1)
       其中:H(key)为哈希函数;m为哈希表表长;Di为增量序列,有以下3中取法:
         ①Di = 1,2,3,…,m-1, 称为线性探测再散列;
         ②Di = 1²,-1²,2²,-2²,。。。,±k²,(k<= m/2)称为二次探测再散列
         ③Di = 伪随机数序列,称为伪随机数探测再散列。
         例如:在长度为12的哈希表中插入关键字为38的记录:
         这里写图片描述
         从上述线性探测再散列的过程中可以看出一个现象:当表中i、i+1位置上有记录时,下一个哈希地址为i、i+1、i+2的记录都将填入i+3的位置,这种本不是同义词却要争夺同一个地址的现象叫“堆积“。即在处理同义词的冲突过程中又添加了非同义词的冲突;但是,用线探测再散列处理冲突可以保证:只要哈希表未填满,总能找到一个不发生冲突的地方。

    (2)、再哈希法

    公式:Hi = RHi(key) i = 1,2,…,k
         RHi均是不同的哈希函数,意思为:当繁盛冲突时,使用不同的哈希函数计算地址,直到不冲突为止。这种方法不易产生堆积,但是耗费时间。

    (3)、链地址法

    将所有关键字为同义字的记录存储在一个单链表中,我们称这种单链表为同义词子表,散列表中存储同义词子表的头指针。
         如关键字集合为{19,14,23,01,68,20,84,27,55,11,10,79},按哈希函数H(key) = key mod 13;
         这里写图片描述
         链地址法解决了冲突,提供了永远都能找到地址的保证。但是,也带来了查找时需要遍历单链表的性能损耗。

    (4)、公共溢出区法

    即设立两个表:基础表和溢出表。将所有关键字通过哈希函数计算出相应的地址。然后将未发生冲突的关键字放入相应的基础表中,一旦发生冲突,就将其依次放入溢出表中即可。
         在查找时,先用给定值通过哈希函数计算出相应的散列地址后,首先 首先与基本表的相应位置进行比较,如果不相等,再到溢出表中顺序查找。

    6、哈希表查找算法的实现

    首先定义一个散列表的结构以及一些相关的常数。其中,HashTables是散列表结构。结构当中的elem为一个动态数组。

    #define SUCCESS 1
    #define UNSUCCESS 0
    #define HASHSIZE 12    /*定义哈希表长为数组的长度*/
    #define NULLKEY -32768
    {
        int *elem;        /*数组元素存储基址,动态分配数组*/
        int count;        /*当前数据元素的个数*/
    }HashTable;
    int m = 0;            
    123456789
    

    初始化哈希表

    /*初始化哈希表*/
    Status InitHashTable(HashTable *H)
    {
        int i;
        m = HASHSIZE;
        H->count = m;
        H->elem = (int *)malloc(m*sizeof(int));
        for(i = 0;i<m;i++)
            H->elem[i] = NULLKEY;
    
        return OK;
    }   
    123456789101112
    

    定义哈希函数

    /*哈希函数*/
    int Hash(int key)
    {
        return key % m;     /*除留取余法*/
    }
    12345
    

    插入操作

    /*将关键字插入散列表*/
    void InsertHash(HashTable *H,int key)
    {
         int addr = Hash(Key);             /*求哈希地址*/
         while(H->elem[addr] != NULLKEY)         /*如果不为空则冲突*/
             addr = (addr + 1) % m;           /*线性探测*/
         H->elem[addr] = key;            /*直到有空位后插入关键字*/        
    }   
    12345678
    

    查找操作

    /*查找*/
    Status SearchHash(HashTable H,int key,int *addr)
    {
        *addr = Hash(key);        /*求哈希地址*/
        while(H.elem[*addr] != key)        /*若不为空,则冲突*/
        {
            *addr = (*addr + 1) % m;         /*线性探测*/
            if(H.elem[*addr) == NULLKEY || *addr == Hash(key))
            {/*如果循环回到原点*/
                return UNSUCCESS;        /*则说明关键字不存在*/
            }
        }
        return SUCCESS;
    }   
    1234567891011121314
    

    7、总结

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

    展开全文
  • 哈希原理

    千次阅读 2019-07-08 18:05:07
    哈希表是最常用的数据结构之一,对于其用法,大家都非常熟悉,这里详细探讨一下其原理哈希表的底层实际上是基于数组来存储的,当插入键值对时,并不是直接插入该数组中,而是通过对键进行Hash运算得到Hash值,然后...

    哈希表是最常用的数据结构之一,对于其用法,大家都非常熟悉,这里详细探讨一下其原理。哈希表的底层实际上是基于数组来存储的,当插入键值对时,并不是直接插入该数组中,而是通过对键进行Hash运算得到Hash值,然后和数组容量取模,得到在数组中的位置后再插入。取值时,先对指定的键求Hash值,再和容量取模得到底层数组中对应的位置,如果指定的键值与存贮的键相匹配,则返回该键值对,如果不匹配,则表示哈希表中没有对应的键值对。这样做的好处是在查找、插入、删除等操作可以做到 O ( 1 ) O(1) O(1),最坏的情况是 O ( n ) O(n) O(n),当然这种是最极端的情况,极少遇到。
    image
    不管哪门语言,实现一个HashMap的过程均可分为三大步骤:

    • 实现一个Hash函数
    • 合理解决Hash冲突
    • 实现HashMap的操作方法

    Hash函数

    Hash函数非常重要,一个好的Hash函数不仅性能优越,而且还会让存储于底层数组中的值分配的更加均匀,减少冲突发生。之所以是减少冲突,是因为取Hash的过程,实际上是将输入键(定义域)映射到一个非常小的空间中,所以冲突是无法避免的,能做的只是减少Hash碰撞发生的概率。具体实现时,哈希函数算法可能不同,在Rust及很多语言的实现中,默认选择SipHash哈希算法。

    默认情况下,Rust的HashMap使用SipHash哈希算法,其旨在防止哈希表碰撞攻击,同时在各种工作负载上提供合理的性能。虽然 SipHash 在许多情况下表现出竞争优势,但其中一个比其它哈希算法要慢的情况是使用短键,例如整数。这就是为什么 Rust 程序员经常观察到 HashMap 表现不佳的原因。在这些情况下,经常推荐 FNV 哈希,但请注意,
    它不具备与 SipHash 相同的防碰撞性。

    影响Hash碰撞(冲突)发生的除了Hash函数本身意外,底层数组容量也是一个重要原因。很明显,极端情况下如果数组容量为1,哪必然发生碰撞,如果数组容量无限大,哪碰撞的概率非常之低。所以,哈希碰撞还取决于负载因子。负载因子是存储的键值对数目与数组容量的比值,比如数组容量100,当前存贮了90个键值对,负载因子为0.9。负载因子决定了哈希表什么时候扩容,如果负载因子的值太大,说明存储的键值对接近容量,增加碰撞的风险,如果值太小,则浪费空间。

    所以,既然冲突无法避免,就必须要有解决Hash冲突的机制方法。

    处理冲突的几种方法

    主要有四类处理冲突的方法:

    • 外部拉链法(常用)
    • 开放定址法(常用)
    • 公共溢出区(不常用)
    • 再Hash法(不常用)

    外部拉链法

    主要思想是基于数组和链表的组合来解决冲突,桶(Bucket)中不直接存储键值对,每个Bucket都链接一个链表,当发生冲突时,将冲突的键值对插入链表中。外部拉链法的有点在于方法简单,非同义词之间也不会产生聚集现象(相比于开放定址法),并且其空间结构是动态申请的,所以比较适合无法确定表长的情况:缺点是链表指针需要额外的空间,遇到碰撞拒绝服务时会退化为单链表。

    同义词:两个元素通过Hash函数得到了相同的索引地址,这两个元素就叫做同义词。

    下面是外部拉链法的两种实现方法,主要区别在于桶(Bucket)中是否存储数据。
    image

    image

    开放定址法

    主要思想是发生冲突时,直接去寻找下一个空的地址,只要底层的表足够大,就总能找到空的地址。这个寻找下一个地址的行为,叫做探测。 h a s h i = ( h a s h ( k e y ) + d i )     m o d    m , i = 1 , 2... k   ( k ≤ m − 1 ) {hash_{i}=(hash(key)+d_{i})\,{\bmod {\,}}m}, i=1,2...k\,(k\leq m-1) hashi=(hash(key)+di)modmi=1,2...k(km1)`,其中 h a s h ( k e y ) hash(key) hash(key)为哈希函数, m m m为哈希表长, d i d_{i} di为增量序列, i i i为已发生冲突的次数。根据增量序列取法的不同有多种探测方法:

    • d i = 1 , 2 , 3... ( m − 1 ) d_{i}=1,2,3...(m-1) di=1,2,3...(m1)称为线性探测(Linear Probing);即 d i = i d_{i}=i di=i,或者为其他线性函数。相当于逐个探测存放地址的表,直到查找到一个空单元,把散列地址存放在该空单元。
    • d i = ± 1 2 , ± 2 2 , ± 3 2 . . . ± k 2 ( k ≤ m / 2 ) d_{i}=\pm 1^{2},\pm 2^{2},\pm 3^{2}...\pm k^{2} (k\leq m/2) di=±12,±22,±32...±k2(km/2)称为平方探测(Quadratic Probing)。相对线性探测,相当于发生冲突时探测间隔$ d_{i}=i^{2}$个单元的位置是否为空,如果为空,将地址存放进去。
    • d i = 伪 随 机 数 序 列 d_{i}=伪随机数序列 di=,称为伪随机探测。

    下图为线性探测:

    image

    公共溢出区

    主要思想是建立一个独立的公共区,把冲突的键值对都放在其中。不常用,这里不再细述。

    再Hash法

    主要思想是有冲突时,换另外一个Hash函数来算Hash值。不常用,这里不再细述。

    实现哈希表的操作方法

    主要是:

    • insert
    • remove
    • get
    • contains_key
    • …等等…

    其中最重要的是插入、查找、删除这三个操作。

    参考文档Hash table

    展开全文
  • 一致性哈希算法原理详解

    万次阅读 多人点赞 2021-10-17 18:31:32
    (1)一致性哈希算法将整个哈希值空间按照顺时针方向组织成一个虚拟的圆环,称为 Hash 环; (2)接着将各个服务器使用 Hash 函数进行哈希,具体可以选择服务器的IP或主机名作为关键字进行哈希,从而确定每台机器在...

    一、普通 hash 算法 (取模算法):

            在了解一致性哈希算法之前,我们先了解一下缓存中的一个应用场景,了解了这个应用场景之后,再来理解一致性哈希算法,就容易多了,也更能体现出一致性哈希算法的优点,那么,我们先来描述一下这个经典的分布式缓存的应用场景。

    1、普通 hash算法 与 使用场景描述:

            假设我们有三台缓存服务器,用于缓存图片,我们为这三台缓存服务器编号为 0号、1号、2号,现在有3万张图片需要缓存,我们希望这些图片被均匀的缓存到这3台服务器上,以便它们能够分摊缓存的压力。也就是说,我们希望每台服务器能够缓存1万张左右的图片,那么我们应该怎样做呢?常见的做法是对缓存项的键进行哈希,将hash后的结果对缓存服务器的数量进行取模操作,通过取模后的结果,决定缓存项将会缓存在哪一台服务器上

            我们举例说明,以刚才描述的场景为例,假设图片名称是不重复的,那我们就可以使用图片名称作为访问图片的key,使用如下公式,计算出图片应该存放在哪台服务器上。

    hash(图片名称)% N

            当我们对同一个图片名称做相同的哈希计算时,得出的结果应该是不变的,如果我们有3台服务器,使用哈希后的结果对3求余,那么余数一定是0、1或者2;如果求余的结果为0, 就把当前图片缓存在0号服务器上,如果余数为1,就缓存在1号服务器上,以此类推;同理,当我们访问任意图片时,只要再次对图片名称进行上述运算,即可得出图片应该存放在哪一台缓存服务器上,我们只要在这一台服务器上查找图片即可,如果图片在对应的服务器上不存在,则证明对应的图片没有被缓存,也不用再去遍历其他缓存服务器了,通过这样的方法,即可将3万张图片随机的分布到3台缓存服务器上了,而且下次访问某张图片时,直接能够判断出该图片应该存在于哪台缓存服务器上,我们暂时称上述算法为 HASH 算法或者取模算法,取模算法的过程可以用下图表示:

     2、普通 hash 算法的缺陷:

            上述HASH算法时,会出现一些缺陷:如果服务器已经不能满足缓存需求,就需要增加服务器数量,假设我们增加了一台缓存服务器,此时如果仍然使用上述方法对同一张图片进行缓存,那么这张图片所在的服务器编号必定与原来3台服务器时所在的服务器编号不同,因为除数由3变为了4,最终导致所有缓存的位置都要发生改变,也就是说,当服务器数量发生改变时,所有缓存在一定时间内是失效的,当应用无法从缓存中获取数据时,则会向后端服务器请求数据;同理,假设突然有一台缓存服务器出现了故障,那么我们则需要将故障机器移除,那么缓存服务器数量从3台变为2台,同样会导致大量缓存在同一时间失效,造成了缓存的雪崩,后端服务器将会承受巨大的压力,整个系统很有可能被压垮。为了解决这种情况,就有了一致性哈希算法。

            

    二、一致性哈希算法:

     1、什么是一致性 hash 算法:

            一致性哈希算法也是使用取模的方法,但是取模算法是对服务器的数量进行取模,而一致性哈希算法是对 2^32 取模,具体步骤如下:

    • 步骤一:一致性哈希算法将整个哈希值空间按照顺时针方向组织成一个虚拟的圆环,称为 Hash 环;
    • 步骤二:接着将各个服务器使用 Hash 函数进行哈希,具体可以选择服务器的IP或主机名作为关键字进行哈希,从而确定每台机器在哈希环上的位置
    • 步骤三:最后使用算法定位数据访问到相应服务器:将数据key使用相同的函数Hash计算出哈希值,并确定此数据在环上的位置,从此位置沿环顺时针寻找,第一台遇到的服务器就是其应该定位到的服务器

    下面我们使用具体案例说明一下一致性哈希算法的具体流程:

    (1)步骤一:哈希环的组织:

            我们将 2^32 想象成一个圆,像钟表一样,钟表的圆可以理解成由60个点组成的圆,而此处我们把这个圆想象成由2^32个点组成的圆,示意图如下:

            圆环的正上方的点代表0,0点右侧的第一个点代表1,以此类推,2、3、4、5、6……直到2^32-1,也就是说0点左侧的第一个点代表2^32-1,我们把这个由 2^32 个点组成的圆环称为hash环。

    (2)步骤二:确定服务器在哈希环的位置:

    哈希算法:hash(服务器的IP) % 2^32

            上述公式的计算结果一定是 0 到 2^32-1 之间的整数,那么上图中的 hash 环上必定有一个点与这个整数对应,所以我们可以使用这个整数代表服务器,也就是服务器就可以映射到这个环上,假设我们有 ABC 三台服务器,那么它们在哈希环上的示意图如下:

     (3)步骤三:将数据映射到哈希环上:

            我们还是使用图片的名称作为 key,所以我们使用下面算法将图片映射在哈希环上:hash(图片名称) % 2^32,假设我们有4张图片,映射后的示意图如下,其中橘黄色的点表示图片:

            那么,怎么算出上图中的图片应该被缓存到哪一台服务上面呢?我们只要从图片的位置开始,沿顺时针方向遇到的第一个服务器就是图片存放的服务器了。最终,1号、2号图片将会被缓存到服务器A上,3号图片将会被缓存到服务器B上,4号图片将会被缓存到服务器C上。

     2、一致性 hash 算法的优点:

            前面提到,如果简单对服务器数量进行取模,那么当服务器数量发生变化时,会产生缓存的雪崩,从而很有可能导致系统崩溃,而使用一致性哈希算法就可以很好的解决这个问题,因为一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据,只有部分缓存会失效,不至于将所有压力都在同一时间集中到后端服务器上,具有较好的容错性和可扩展性

            假设服务器B出现了故障,需要将服务器B移除,那么移除前后的示意图如下图所示:

            在服务器B未移除时,图片3应该被缓存到服务器B中,可是当服务器B移除以后,按照之前描述的一致性哈希算法的规则,图片3应该被缓存到服务器C中,因为从图片3的位置出发,沿顺时针方向遇到的第一个缓存服务器节点就是服务器C,也就是说,如果服务器B出现故障被移除时,图片3的缓存位置会发生改变,但是,图片4仍然会被缓存到服务器C中,图片1与图片2仍然会被缓存到服务器A中,这与服务器B移除之前并没有任何区别,这就是一致性哈希算法的优点。

     3、hash 环的倾斜与虚拟节点:

            一致性哈希算法在服务节点太少的情况下,容易因为节点分部不均匀而造成数据倾斜问题,也就是被缓存的对象大部分集中缓存在某一台服务器上,从而出现数据分布不均匀的情况,这种情况就称为 hash 环的倾斜。如下图所示:

             hash 环的倾斜在极端情况下,仍然有可能引起系统的崩溃,为了解决这种数据倾斜问题,一致性哈希算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点,一个实际物理节点可以对应多个虚拟节点,虚拟节点越多,hash环上的节点就越多,缓存被均匀分布的概率就越大,hash环倾斜所带来的影响就越小,同时数据定位算法不变,只是多了一步虚拟节点到实际节点的映射。具体做法可以在服务器ip或主机名的后面增加编号来实现,加入虚拟节点以后的hash环如下:


    相关阅读:

    常见的服务器架构入门:从单体架构、EAI 到 SOA 再到微服务和 ServiceMesh

    常见分布式理论(CAP、BASE)和一致性协议(Gosssip协议、Raft一致性算法)

    一致性哈希算法原理详解

    Nacos注册中心的部署与用法详细介绍

    Nacos配置中心用法详细介绍

    SpringCloud OpenFeign 远程HTTP服务调用用法与原理

    什么是RPC?RPC框架dubbo的核心流程

    服务容错设计:流量控制、服务熔断、服务降级

    sentinel 限流熔断神器详细介绍

    Sentinel 规则持久化到 apollo 配置中心

    Sentinel-Dashboard 与 apollo 规则的相互同步

    Spring Cloud Gateway 服务网关的部署与使用详细介绍

    Spring Cloud Gateway 整合 sentinel 实现流控熔断

    Spring Cloud Gateway 整合 knife4j 聚合接口文档

    常见分布式事务详解(2PC、3PC、TCC、Saga、本地事务表、MQ事务消息、最大努力通知)

    分布式事务Seata原理

    RocketMQ事务消息原理


     参考文章:https://www.zsythink.net/archives/1182

    展开全文
  • 哈希算法的原理和用途详解

    千次阅读 2021-04-20 13:27:53
    什么是哈希算法?哈希是一种加密算法,也称为散列函数或杂凑函数。哈希函数是一个公开函数,可以将任意长度的消息M映射成为一个长度较短且长度固定的值H(M),称H(M)为哈希值、散列值(Hash Value)、杂凑值或者...
  • 一致性哈希算法原理

    2021-04-02 16:12:26
    一致性哈希算法是通过将哈希空间分为1-2^32-1的圆环,我们把cache节点和我们的object对象数据hash运算以后分别映射到圆环上,然后会把对象的数据按照顺时针绑定到最近的一个cache节点,实现数据与节点的绑定,这样做...
  • 哈希原理与常见哈希函数

    千次阅读 多人点赞 2020-01-09 18:11:06
    一,什么是哈希 哈希是将任意长度的数据转换为一个数字的过程。这个数字是在一个固定的范围之内的。 转换的方法称为哈希函数,原值经过哈希函数计算后得到的值称为哈希值。 1.哈希特点 (1)一致性:同一个值每次经过...
  • 9张图,带你了解一致性哈希原理

    千次阅读 多人点赞 2021-10-19 21:35:10
    为了由文件名(假设文件名称不重复)能得到存储的机器,考虑先对文件名做hash运算,接着对3取余,得到的余数即为所在机器的编号。 这套系统运行了很久,后来文件数量慢慢增多,3台机器存不下了,现在我们考虑扩充...
  • 自学数据结构与算法之哈希
  • 哈希表实现原理

    2022-03-17 20:55:32
    哈希表底层是数组,键值对存储,当插入数据时,对键值进行hash运算得到value,value对数组取余,存入数组下标位置,所以哈希表的插入,删除,查找时间复杂度为O(1), 实现哈希函数 解决哈希冲突 外部拉链法: 基于...
  • 区块链中最基础的密码学原理就是哈希算法,以下为哈希函数的简单介绍: 哈希函数是一种只只能加密但是不能解密的算法,哈希函数可以将任意长度的信息转化为固定长度的字符串。类似“8b46ec792e943de34605981980751...
  • 哈希表的原理

    2022-01-28 17:24:21
    一.介绍 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。...答案是肯定的,这就是我们要提起的哈希表,哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法
  • 计算机组测原理实验:MIPS运算
  • 主要讲解哈希原理、冲突、扩容的相关知识
  • 认识一下31这个神奇的数, 31是一个奇素数(即是奇数又是素数) 31 * i 可以写成(i << 5)- i (JVM可以把31 * i ...哈希表类似数组一样,根据索引去存放值,添加、搜索、删除的都可以达到O(1)的级别,索引的计...
  • 最通俗易懂的一致性哈希算法原理

    千次阅读 2019-01-08 01:05:52
    再讨论一致性哈希之前,我们先来回顾一下缓存的演化历史: 当我们的系统还是一个非常小的时候,对于用户的请求我们直接访问数据库就好了。当访问量到了一定数量的时候,我们使用缓存服务器,缓存一部分热数据来减轻...
  • 哈希算法的原理及其 Java 实现一、目的二、运行环境三、基本原理及步骤(I)各种加密算法的原理:① DES 数据加密标准(Data Encryption Standard):算法介绍算法流程优点缺点破解方式适用场景安全性② 3DES(DES ...
  • HMAC算法原理 HMAC算法是一种基于密钥的报文完整性的验证方法,其安全性是建立在Hash加密算法基础上的。它要求通信双方共享密钥、约定算法...一句话总结:HMAC是密钥相关的哈希运算消息认证码(Hash-based Message...
  • 讲解哈希函数,哈希表的原理以及常用运算。 是常用的数据结构
  • 最近陆续造了一批哈希算法的轮子,包括MD家族(包括MD2/MD4/MD5), SHA1, SHA2家族(SHA224, SHA256, SHA384, SHA512),SHA3家族(SHA3-224, SHA3-256, SHA3-384, SHA3-512, SHAKE128, SHAKE256)以及国密SM3算法。...
  • 目录1....想要学习一门技术能够大概了解它的原理其实已经差不多了,但是面试官往往会刨根问底,追问你put流程,resize过程,为什么负载因子是0.75之类的…… 其实这些都还好,最让人头疼的是哈希
  • 散列表的英文名称为 hash table,因此散列表又被称为哈希表,散列函数又被称为哈希函数,函数的实现步骤被称为散列算法/哈希算法。 对于其他查找算法和数据结构比如二分查找、插值查找、二叉排序树、AVL树等还不...
  • 哈希表(散列表)原理详解

    万次阅读 多人点赞 2018-07-03 19:40:58
    什么是哈希表? 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数...
  • Python算法系列-哈希算法

    千次阅读 多人点赞 2020-04-12 23:11:10
    哈希算法一、常见数据查找算法简介二、什么是哈希三、实例:两个数字的和1.问题描述2.双指针办法解决3.哈希算法求解四、总结 哈希算法又称散列函数算法,是一种查找算法。就是把一些复杂的数据通过某种映射关系。...
  • 详解Python字典的底层原理————哈希表(Python面试必备) 作者:Loren no hurry 2019-06-9 Python面试经常会被问到: 你能说一说Python字典的底层实现原理吗? 这个问题可以从三个方面来回答: 1.python字典及其...
  • 哈希哈希

    2021-10-31 23:54:34
    atoi只能将数字类型的字符串转换为字符串格式,因此要借助一些其他的算法来实现取模的运算,有住专门设计的字符串哈希算法等。 实现一个简单的哈希桶 #pragma once #include #include"Common.h" #include using ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 48,914
精华内容 19,565
热门标签
关键字:

哈希运算原理