精华内容
下载资源
问答
  • 哈希算法原理和实现
    千次阅读 多人点赞
    2020-09-13 10:32:32

    哈希算法原理和实现

    前言

    当我们在编程过程中,往往需要对线性表进行查找操作。在顺序表中查找时,需要从表头开始,依次遍历比较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);如果没有时间限制,那么我们可以使用无序数组并进行顺序查找,这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。

    更多相关内容
  • 十分钟掌握一致性哈希原理

    声明:

    本次文章内容以本人公司技术分享的PPT为基础。

    若需要PPT内容,欢迎联系。

    前言

    在进行一致性哈希介绍前,先思考2个问题:

    1. 什么是Hash

    2. 一致性Hash和Hash的关系是什么

    对于第一个问题Hash的定义

    Hash也成散列,基本原理就是把任意长度的输入,通过hash算法变成固定长度的输出。

    对于第二个问题,下面我们进行详细介绍。

    引出问题

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

    场景描述

    对于3万张图片的处理,第一种随机存储,可以满足我们的要求吗?可以。但是如果这样做,当我们需要访问某个缓存项时,则需要遍历3台缓存服务器,从3万个缓存项中找到我们需要访问的缓存,遍历的过程效率太低,时间太长,当我们找到需要访问的缓存项时,时长可能是不能被接受的,也就失去了缓存的意义。

    那么就是第二种方式,进行Hash取模算法。

     

    似乎,Hash取模算法可以满足我们的使用场景了,但是,上面还是会出现一些缺陷的,试想一下,如果3台缓存服务器已经不能满足我们的缓存需求,需要对服务器进行扩容,假设,我们增加了一台缓存服务器,那么缓存服务器数量由3台变为4台。此时,如果仍然使用上述方法对同一张图片进行缓存,那么这张图片所在的服务器编号必定与原来3台服务器时所在的服务器编号不同,因为除数由3变为了4,被除数不变的情况下,余数肯定不同,这种情况带来的结果就是当服务器数量变动时,所有缓存的位置都要发生改变,换句话说,当服务器数量发生改变时,所有缓存在一定时间内是失效的,当应用无法从缓存中获取数据时,则会向后端服务器请求数据。数据库减少时,场景同理。

     

    正式上述所述问题,由于大量缓存在同一时间失效,造成了缓存的雪崩,此时前端缓存已经无法起到承担部分压力的作用,后端服务器将会承受巨大的压力,整个系统很有可能被压垮,所以,我们应该想办法不让这种情况发生,但是由于上述HASH算法本身的缘故,使用取模法进行缓存时,这种情况是无法避免的,为了解决这些问题,一致性哈希算法诞生了。

    我们来回顾一下Hash算法会出现的问题。

    问题1:当缓存服务器数量发生变化时,会引起缓存的雪崩,可能会引起整体系统压力过大而崩溃(大量缓存同一时间失效)。

    问题2:当缓存服务器数量发生变化时,几乎所有缓存的位置都会发生改变,怎样才能尽量减少受影响的缓存呢?

    其实,上面两个问题是一个问题,那么,一致性哈希算法能够解决上述问题吗?

    我们现在就来了解一下一致性哈希算法

    一致性哈希算法的基本概念

     

     

     

    一致性哈希算法的优点

    经过上述描述,大家应该已经明白了一致性哈希算法的原理了,但是话说回来,一致性哈希算法能够解决之前出现的问题吗,我们说过,如果简单的对服务器数量进行取模,那么当服务器数量发生变化时,会产生缓存的雪崩,从而很有可能导致系统崩溃,那么使用一致性哈希算法,能够避免这个问题吗?我们来模拟一遍,即可得到答案。

    如上优点所述,这就是一致性哈希算法的优点,如果使用之前的hash算法,服务器数量发生改变时,所有服务器的所有缓存在同一时间失效了,而使用一致性哈希算法时,服务器的数量如果发生改变,并不是所有缓存都会失效,而是只有部分缓存会失效,前端的缓存仍然能分担整个系统的压力,而不至于所有压力都在同一时间集中到后端服务器上。

     hash环的偏斜

    上述内容,我们理想化的将3台服务器均匀映射到hash环上了,但是,我们想象的与实际情况往往不一样。很有可能大部分集中缓存到某一台服务器上,我们称这种现象为数据倾斜:

    虚拟节点

    所谓虚拟节点就是凭空的让服务器节点多起来,既然没有多余的真正的物理服务器节点,我们就只能将现有的物理节点通过虚拟的方法复制出来,这些由实际节点虚拟复制而来的节点被称为”虚拟节点”。加入虚拟节点以后的hash环如下。

     

    以上为一致性哈希算法的原理。

     以上为全部内容。

    欢迎关注10W+的微信公众号:

    技术难点欢迎咨询,如有需要加我微信:1106915848。

    星光不问赶路人,时光不负有心人

     

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

    千次阅读 多人点赞 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

    展开全文
  • 针对非局部均值(NLM)算法度量邻域块相似度不够准确的缺点,提出了一种基于差异哈希算法与汉明距离的改进NLM算法。传统算法通过欧氏距离度量邻域块之间的相似度,保持边缘和细节的能力较弱,易导致滤波后的图像模糊失真...
  • 一致性哈希算法原理

    2020-09-01 15:11:19
    一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT...

    1. 背景

    一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用。

    但现在一致性hash算法在分布式系统中也得到了广泛应用,研究过memcached缓存数据库的人都知道,memcached服务器端本身不提供分布式cache的一致性,而是由客户端来提供,具体在计算一致性hash时采用如下步骤:

    • 首先求出memcached服务器(节点)的哈希值,并将其配置到0~232的圆(continuum)上。
    • 然后采用同样的方法求出存储数据的键的哈希值,并映射到相同的圆上。
    • 然后从数据映射到的位置开始顺时针查找,将数据保存到找到的第一个服务器上。如果超过232仍然找不到服务器,就会保存到第一台memcached服务器上。

    在这里插入图片描述
    从上图的状态中添加一台memcached服务器。余数分布式算法由于保存键的服务器会发生巨大变化而影响缓存的命中率,但Consistent Hashing中,只有在圆(continuum)上增加服务器的地点逆时针方向的第一台服务器上的键会受到影响,如下图所示:
    在这里插入图片描述

    2. 性质

    考虑到分布式系统每个节点都有可能失效,并且新的节点很可能动态的增加进来,如何保证当系统的节点数目发生变化时仍然能够对外提供良好的服务,这是值得考虑的,尤其实在设计分布式缓存系统时,如果某台服务器失效,对于整个系统来说如果不采用合适的算法来保证一致性,那么缓存于系统中的所有数据都可能会失效(即由于系统节点数目变少,客户端在请求某一对象时需要重新计算其hash值(通常与系统中的节点数目有关),由于hash值已经改变,所以很可能找不到保存该对象的服务器节点),因此一致性hash就显得至关重要,良好的分布式cahce系统中的一致性hash算法应该满足以下几个方面:

    • 平衡性(Balance)
      平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

    • 单调性(Monotonicity)
      单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲区加入到系统中,那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去,而不会被映射到旧的缓冲集合中的其他缓冲区。简单的哈希算法往往不能满足单调性的要求,如最简单的线性哈希:x = (ax + b) mod §,在上式中,P表示全部缓冲的大小。不难看出,当缓冲大小发生变化时(从P1到P2),原来所有的哈希结果均会发生变化,从而不满足单调性的要求。哈希结果的变化意味着当缓冲空间发生变化时,所有的映射关系需要在系统内全部更新。而在P2P系统内,缓冲的变化等价于Peer加入或退出系统,这一情况在P2P系统中会频繁发生,因此会带来极大计算和传输负荷。单调性就是要求哈希算法能够应对这种情况。

    • 分散性(Spread)
      在分布式环境中,终端有可能看不到所有的缓冲,而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时,由于不同终端所见的缓冲范围有可能不同,从而导致哈希的结果不一致,最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的,因为它导致相同内容被存储到不同缓冲中去,降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生,也就是尽量降低分散性。

    • 负载(Load)
      负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中,那么对于一个特定的缓冲区而言,也可能被不同的用户映射为不同的内容。与分散性一样,这种情况也是应当避免的,因此好的哈希算法应能够尽量降低缓冲的负荷。

    • 平滑性(Smoothness)
      平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的。

    3. 原理

    一致性哈希算法(Consistent Hashing)最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。简单来说,一致性哈希将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0-2^32-1(即哈希值是一个32位无符号整形),整个哈希空间环如下:

    在这里插入图片描述

    整个空间按顺时针方向组织。0232-1在零点中方向重合。

    下一步将各个服务器使用Hash进行一个哈希,具体可以选择服务器的ip或主机名作为关键字进行哈希,这样每台机器就能确定其在哈希环上的位置,这里假设将上文中四台服务器使用ip地址哈希后在环空间的位置如下:
    在这里插入图片描述
    接下来使用如下算法定位数据访问到相应服务器:将数据key使用相同的函数Hash计算出哈希值,并确定此数据在环上的位置,从此位置沿环顺时针“行走”,第一台遇到的服务器就是其应该定位到的服务器。

    例如我们有Object A、Object B、Object C、Object D四个数据对象,经过哈希计算后,在环空间上的位置如下:
    在这里插入图片描述

    根据一致性哈希算法,数据A会被定为到Node A上,B被定为到Node B上,C被定为到Node C上,D被定为到Node D上。

    下面分析一致性哈希算法的容错性和可扩展性。现假设Node C不幸宕机,可以看到此时对象A、B、D不会受到影响,只有C对象被重定位到Node D。一般的,在一致性哈希算法中,如果一台服务器不可用,则受影响的数据仅仅是此服务器到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器)之间数据,其它不会受到影响。

    下面考虑另外一种情况,如果在系统中增加一台服务器Node X,如下图所示:
    在这里插入图片描述
    此时对象Object A、B、D不受影响,只有对象C需要重定位到新的Node X 。一般的,在一致性哈希算法中,如果增加一台服务器,则受影响的数据仅仅是新服务器到其环空间中前一台服务器(即沿着逆时针方向行走遇到的第一台服务器)之间数据,其它数据也不会受到影响。

    综上所述,一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据,具有较好的容错性和可扩展性。

    另外,一致性哈希算法在服务节点太少时,容易因为节点分部不均匀而造成数据倾斜问题。例如系统中只有两台服务器,其环分布如下,
    在这里插入图片描述
    此时必然造成大量数据集中到Node A上,而只有极少量会定位到Node B上。为了解决这种数据倾斜问题,一致性哈希算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。具体做法可以在服务器ip或主机名的后面增加编号来实现。例如上面的情况,可以为每台服务器计算三个虚拟节点,于是可以分别计算 “Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B#2”、“Node B#3”的哈希值,于是形成六个虚拟节点:
    在这里插入图片描述
    同时数据定位算法不变,只是多了一步虚拟节点到实际节点的映射,例如定位到“Node A#1”、“Node A#2”、“Node A#3”三个虚拟节点的数据均定位到Node A上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中,通常将虚拟节点数设置为32甚至更大,因此即使很少的服务节点也能做到相对均匀的数据分布。

    展开全文
  • 感知哈希算法原理与实现

    千次阅读 2016-03-27 19:11:18
    今天忽然想做一个图像识别的APP,但是在两张图片相似度的问题上产生了问题,感知哈希算法并不能解决这个问题,只是我在试着解决问题的过程中学到的一点知识。这里的关键技术叫做”感知哈希算法”(Perceptual hash ...
  • 一致性哈希 安装 go get -u github.com/junhaideng/consistent 使用 c := consistent.New() ips := []string{"192.168.0.1", "192.168.0.2", "192.168.0.3", "192.168.0.4"} for _, ip := range ips { c.Add(ip) ...
  •  一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的,设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得...
  • 一致性哈希算法是将每个Node节点映射到同一个圆上。将各Node的key采用hash计算,可得到一个整数数组。将该数组排序后,首尾相连即是一个圆。如下图所示 简单来说,一致性Hash算法将整个哈希值空间组织成一个...
  • 什么是哈希算法?哈希是一种加密算法,也称为散列函数或杂凑函数。哈希函数是一个公开函数,可以将任意长度的消息M映射成为一个长度较短且长度固定的值H(M),称H(M)为哈希值、散列值(Hash Value)、杂凑值或者...
  • 一致性哈希算法原理与实现

    万次阅读 多人点赞 2018-08-13 14:08:29
    而一致性哈希算法中,当节点个数变动时,映射关系失效的对象非常少,迁移成本也非常小。本文总结了一致性哈希的算法原理和Java实现,并列举了其应用。 作者:王克锋 出处:https://kefeng.wang/2018/08/1...
  • 最通俗易懂的一致性哈希算法原理

    千次阅读 2019-01-08 01:05:52
    再讨论一致性哈希之前,我们先来回顾一下缓存的演化历史: 当我们的系统还是一个非常小的时候,对于用户的请求我们直接访问数据库就好了。当访问量到了一定数量的时候,我们使用缓存服务器,缓存一部分热数据来减轻...
  • 图片识别——均值哈希算法

    千次阅读 2020-05-18 19:34:44
    均值哈希算法(Average hash algorithm,AHA)第一次是从著名的阮一峰阮老师的博文《相似图片搜索的原理》看到的。而此篇文章与阮老师也很类似Looks Like It - The Hacker Factor Blog。这里不对原谅做摘抄,有兴趣的...
  • 感知哈希算法

    千次阅读 2020-11-04 18:13:43
    感知哈希算法是一类哈希算法的总称,其作用在于生成每张图像的“指纹”(fingerprint)字符串,比较不同图像的指纹信息来判断图像的相似性。结果越接近图像越相似。感知哈希算法包括均值哈希(aHash)、感知哈希...
  • 图片识别——感知哈希算法

    千次阅读 2020-05-18 19:37:44
    所谓感知哈希算法(Perceptual hash algorithm,PHA),它是用于对多种格式的数据生成一个指纹的算法。当然本文只讨论图片格式。感知哈希不同于密码哈希(如md5云云),它对于相似特征的输入,会有相似的输出;而...
  • 差异哈希算法(Different Hash Algorithms,dHash),像aHash和pHash一样,dHash易于实现,相比于它的简单,其实它的识别更为准确。作为一种感知算法的实现,dHash比aHash相近,但比aHash效果更好。aHash关注于平均...
  • 哈希算法、哈希表的作用与原理

    千次阅读 2019-09-23 14:58:15
    闲谈Hash 由于以前对hash的理解就不是很...哈希算法的最初是为了验证两条信息是否相同,可能你会认为这很简单啊,所有的编程语言都提供的有比较的方法,直接用不就可以了吗,确实,是可以直接用一些类似于equals...
  • 图像相似度比较哈希算法: 什么是哈希(Hash)? • 散列函数(或散列算法,又称哈希函数,英语:Hash Function)是一种从任何一种数据中创建小 的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变...
  • 图像相似度比较哈希算法 相似图像搜索的哈希算法有三种: 1.均值哈希算法 2.差值哈希算法 3.感知哈希算法 什么是哈希(Hash) • 散列函数(或散列算法,又称哈希函数,英语: Hash Function )是一种从任何一种数据...
  • 03-一致性哈希算法 java 实现 04-负载均衡算法 java 实现 概念 一致哈希是一种特殊的哈希算法。 在使用一致哈希算法后,哈希表槽位数(大小)的改变平均只需要对 K/n个关键字重新映射,其中K是关键字的数量, n是槽...
  • 在程序员的实际开发中,哈希算法常常能用得到,本文以哈希算法原理和应用为核心,和大家详细讲解一下哈希算法的概念、常见算法以及原理、在信息安全的应用等等。    一、概念  哈希表就是一种以 键-值(key...
  • 哈希算法的用途

    千次阅读 2019-05-25 21:35:44
    什么是哈希算法 一说到哈希算法, 我瞬间就想到了哈希函数、哈希表, 其实他们并不是一回事. 简单来说, 哈希算法就是将任意长度的字符串通过计算转换为固定长度的字符串, 不对, 不光字符串, 应该说是将任意长度的二...
  • 局部敏感哈希算法介绍

    千次阅读 2018-12-08 23:35:25
    人为的选取一些具有上述性质的函数来作为哈希函数,使得相邻的数据映射后处在哈希表的同一个位置,这样就可以轻松的找到与该数据相似的数据集了。即,通过选取的哈希函数的映射变换能够将原始的数据集划分为若干较小...
  • MD5哈希算法及其原理

    千次阅读 2018-05-02 08:23:42
    “MD5算法介绍。”MD5消息摘要算法(MD5 Message-Digest Algorithm),是在计算机领域被广泛使用的一种哈希算法,用来对信息进行完整性保护。它...
  • 最近陆续造了一批哈希算法的轮子,包括MD家族(包括MD2/MD4/MD5), SHA1, SHA2家族(SHA224, SHA256, SHA384, SHA512),SHA3家族(SHA3-224, SHA3-256, SHA3-384, SHA3-512, SHAKE128, SHAKE256)以及国密SM3算法。...
  • 【数据结构与算法】哈希算法原理和应用详解!

    千次阅读 多人点赞 2021-06-23 16:01:00
    在程序员的实际开发中,哈希算法常常能用得到,本文以哈希算法原理和应用为核心,和大家详细讲解一下哈希算法的概念、常见算法以及原理、在信息安全的应用等等。 一、概念 哈希表就是一种以 键-值(key-...
  • 本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题场景,借此介绍一致性哈希算法以及这个算法如何解决此问题;接...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 103,295
精华内容 41,318
关键字:

哈希算法的原理