精华内容
下载资源
问答
  • 哈希算法原理和实现

    千次阅读 多人点赞 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-01-22 13:53:11
    此文是数据结构和算法之美学习笔记 哈希算法就是将任意长度的二进制值映射为固定长度的二进制串,这个映射的规则就是哈希算法,原始数据映射之后得到的二进制哈希值。 一般哈希算法的要求: 不能通过哈希值反向推导...

    此文是数据结构和算法之美学习笔记

    哈希算法就是将任意长度的二进制值映射为固定长度的二进制串,这个映射的规则就是哈希算法,原始数据映射之后得到的二进制哈希值。

    一般哈希算法的要求:

    • 不能通过哈希值反向推导出原始数据(哈希算法也叫单向哈希算法)
    • 对输入的数据非常敏感,哪怕原始数据只是修改了一个bit,最后得到的哈希值也大不形同
    • 对不同的原始数据,哈希值相同的概率要非常小,散列冲突的概率要很小。
    • 哈希算法的执行效率要尽量的高效,即使较长的文本也能很快的计算出哈希值

    哈希算法的应用非常多最常见的有安全加密,唯一标识,数据校验,散列函数,负载均衡,数据分片,分布式存储。

    安全加密

    常用于加密的哈希算法是
    MD5(Message-Digest-Algorihm 消息摘要算法)
    SHA(Secure Hash Algorihm 安全散列算法)
    DES(Data Encryption Standard 数据加密标准)
    AES(Advanced Encryption Standard 高级加密标准)

    为什么哈希算法无法做到零冲突?

    有一个数学理论:鸽巢原理(也叫抽屉原理)就是说如果有10个鸽巢,有11个格子,那么肯定有一个鸽巢中有两个鸽子。

    哈希算法产生的哈希值的长度也是有限的,比如MD5的哈希值固定是128位的二进制串,最多能表示2128个数据。而我们需要表示的哈希数是无穷的,当数据大于2128的时候,就必然会出现哈希值相同的情况。

    不过由于2128这个数组已经很大了,出现散列冲突的概率要小于1/2128,相对来说很难破解。

    没有绝对的安全加密,越复杂越难破解的加密算法,需要的计算时间也越长,就想SHA-256比SHA-1要更加复杂也就更安全,相应的计算时间就会更长。

    唯一标识

    比如在海量的图库中怎么搜索一张图片是否存在?

    (1)使用图片名字肯定不行,因为可能有的图片名字不一样但是都是一样的图片
    (2)对比图片的二进制码,这种办法可行,但是比较笨,因为图片很多都很大几MB都是常事,转化成二进制后会很大,对比起来也非常耗时
    (3)可以给每一张图片取一个唯一标识,比如可以从二进制码的开头取100字节,中间取100字节,结尾再取100字节,把这300字节放到一块通过哈希算法比如MD5得到一个哈希字符串,用这个作为图片的唯一标识来判断库中是否有该图片

    当我们向库中插入一个图片的时候,先去散列表中查找唯一标识,如果不存在就说明这个图片不在图库中,如果存在就拿出这个图片和将要插入的图片做全量对比,看是否完全一样。如果一样说明已经存在,如果不一样说明两张图片虽然唯一标识一样但不是相同的图片。

    数据校验

    比如BT下载,一个电影可能会被分割成很多块(比如100块)分别下载,等所有文件都下载完成之后在组装成一个完整的电影文件。

    由于网络传输是不安全的,下载的文件快可能会被宿主几区恶意修改或者下载过程出现了错误导致下载的文件是不完整的。如果下载完不能检测是否出错,就会导致最后合并完的电影无法观看甚至中毒。

    一种校验的思路就是,把这100个快分别取哈希值并且保存在种子文件中,由于哈希算法对原始数据非常敏感,只要文件中有一点点改变最后的哈希值就完全不同,当文件块下载完成后,我们可以通过同样的哈希算法对下载好的文件快一一求哈希值跟种子文件中的哈希值对比。如果不一样说明文件快不完整或者被篡改了,需要重新下载。

    散列函数

    散列表中的散列函数也需要哈希算法,不过相对于其他的应用,它对哈希算法的要求不高,即使出现散列冲突,也可以通过开放寻址法和链表法来解决

    散列函数对哈希算法的要求主要散列后的值能否平均分布,散列函数是否执行很快。

    如何防止数据库中信息被脱库

    可以通过哈希算法,对用户密码进行加密之后在存储不过最好选择相对安全的加密算法比如SHA(MD5据说被破解了)
    不过如果用户的密码设置的很简单比如000000,,13456等简单的数组,黑客可以通过字典攻击很容易的猜中
    针对字典攻击可以引入一个盐(salt)跟用户的密码组合在一起增加其复杂度然后在通过哈希算法加密。比如原始密码是123456,可以在其头部或者尾部加上个字符串bxt变成bxt123456或者123456bxt也可以在中间加。

    区块链现很火,其实其底层也是通过哈希算法

    区块链是一块块的区块组成,每个区块分成区块头和区块体,区块头保存着自己区块体和上一个区块头的哈希值。

    因为这种链式关系和哈希值的唯一性,只要区块链上的任意一个区块被修改过,后面的所有的区块保存的哈希值就不对了。

    区块链使用的是SHA256这种哈希算法,计算哈希值是很耗时的,如果要篡改一个区块,就必须重新计算该区块后面的所有的区块的哈希值,短时间内几乎做不到。

    负载均衡

    负载均衡算法有很多,比如轮训,随机,加权轮询等等。怎么才能实现一个会话粘滞(同一个客户端上,在一次会话中的所有请求都路由到同一个服务器上)的负载均衡呢

    最直接的做法就是维护一张映射表,内容是客户端的IP地址或者会话ID,于服务器编号的映射关系。客户端发出的每次请求都要先在映射表中查找应该路由到哪台服务器,然后在请求对应的服务器。

    不过当客户端很多的时候,映射表会很大,浪费空间。客户端的上线下线服务器的扩容都会导致映射失效,维护成本很大。

    我们可以通过哈希算法,把客户端IP地址或者会话ID计算哈希值,把得到的哈希值跟服务器列表的大小进行取模运算,最终得到的值就是应该被路由到的服务器的编号。

    数据分片

    1、如何统计某个关键词出现的次数

    如果我们有1T的数据,里面记录了用户搜索的关键词,怎么快速的统计出每个关键词被搜索的次数。

    先对数据进行分片,然后采用多台机器处理,提高处理速度。

    为了提高处理速度,我们使用n台机器并行处理,从搜索日志中一次读取出每个搜索关键词,通过哈希函数计算哈希值,然后n取模,得到的值就是应该分配到的机器编号

    这样哈希值相同的关键字就会被分配到同一台机器上,每个机器分别计算出关键词的次数,最后合并起来就是最后结果。

    2、如何快速判断图片是否存在图库中

    假如又一亿张图片,一台机器是无法装下的,这时候就可以给数据分片,然后多机处理。准备n台机器,每台机器只维护某一部分图片对应的散列表。我们每次从图库中读取一个图片,计算唯一标识,然后与机器个数,取模,得到的值就是对应分配的机器标号,然后将这个图片唯一标识和图片路径发往对应的机器构建散列表。

    查找的时候,通过同样的哈希算法计算图片的唯一标识,然后机器个数n取模,得到的值就是对应机器的编号,然后去该机器中寻找。

    分布式存储

    如今的互联网的数据都是海量的,只能分布式的存储在不同的机器上,怎么决定放在哪个机器上呢,跟数据分片一样,通过哈希算法对数据取哈希值,然后对机器取模,值就是对应机器的编号。

    问题:当数据增多,原来的机器无法存储的时候,就需要加机器了。但是这个时候不仅仅是加机器这么简单。

    因为比如原来有10台机器,原来的值是通过10来取模的,当加了一台机器之后,就是按11取模了,最后分配到的机器是不一样的。因此所有的数据都要从新计算哈希值,然后从新搬移到正确的机器上,相当于缓存中的数据全部失效,假如以前是直接请求缓存,现在就是直接去请求数据库,数据库就会被压垮、

    怎么解决这个问题呢,可以使用一致性哈希算法

    什么是一致性哈希算法,假如我们有k台机器数据的哈希值的范围是[0,max],我们把整个范围划分成m个小区间(m远大于k),每个机器负责m/k个小区间。当有新的机器加入的时候,就把某几个小区间的数据从原来的机器中搬移到新的机器中,这样既不用重新哈希搬移数据,也保持了哥哥机器上数据的均衡。

    注意取模的时候不是根据机台的个数k而是跟m取。当然取到的数也许不是机台的编号,这时候就按照顺时针来寻找,把数据放到第一个找到的机器上。

    当然这样做也有可能某台机器上存储的东西太多,不够均匀,怎么办呢,可以引入虚拟结点的概念,每台机器分成m/k份,这样相当于这m个结点上都有一台小机器了,取模之后就可以直接放到这些小机器上了。这样就解决了不均匀的问题了。

    展开全文
  • 1.从哈希值不能反向推导出原始数据(因此哈希算法也叫单向哈希算法)。 2.对输入数据非常敏感,哪怕原始数据只修改了一个Bit,最后得到的哈希值也大不相同。 3.散列冲突的概率要很小,对于不同的原始数据,哈希值...

    最近开始学习王争老师的《数据结构与算法之美》,通过总结再加上自己的思考的形式记录这门课程,文章主要作为学习历程的记录。

    哈希算法的定义是将任意长度的二进制值串映射为固定长度的二进制值串。这个映射规则就是哈希算法。通过原始数据映射后得到的二进制值串就是哈希值。设计一个优秀的哈希算法应满足几点要求:

    1.从哈希值不能反向推导出原始数据(因此哈希算法也叫单向哈希算法)。

    2.对输入数据非常敏感,哪怕原始数据只修改了一个Bit,最后得到的哈希值也大不相同。

    3.散列冲突的概率要很小,对于不同的原始数据,哈希值相同的概率非常小。

    4.哈希算法的执行效率要尽量高效,针对较长的文本,也能快速计算出哈希值。

    举个例子,

    MD5(“今天我来讲哈希算法”) = bb4767201ad42c74e650c1b6c03d78fa

    MD5(“jiajia”) = cd611a31ea969b908932d44d126d195b

    可以看出,无论哈希的文本有多长,多短,通过MD5哈希之后,得到的哈希值长度是相同的,而且得到的哈希值看起来像是一堆随机数,毫无规律,也很难根据哈希值反推回对应的文本。

    哈希算法的应用非常非常多,作者选了最常见的7个,分别是安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片和分布式存储。

    应用一:安全加密

    最常用于加密的哈希算法是MD5(MD5消息摘要算法)和SHA(安全散列算法)。除此之外,还有其他加密算法,比如DES(数据加密算法)、AES(高级加密算法)。

    对于加密的哈希算法,有两点格外重要。第一点是很难根据哈希值反向推导出原始数据,第二点是散列冲突的概率要很小。第一点容易理解,为了防止原始数据泄露。第二点需要对为什么哈希算法无法做到零冲突进行解释一下:哈希算法产生的哈希值的长度是固定且有限的。以MD5为例,哈希值是固定的128位二进制串,能表示的数据是有限的,最多表示2128个数据,而我们要哈希的数据是无穷的。如果对2128+1个数据求哈希值,就必然存在哈希值相同的情况。一般情况下,哈希值越长的哈希算法,散列冲突的概率越低。

    没有绝对安全的加密。越复杂、越难破解的加密算法,需要的计算时间也越长。在实际开发过程中,也需权衡破解难度和计算时间,来决定究竟使用哪种加密算法。

    应用二:唯一标识

    以图片为例,如果要在图库中搜索一张图是否存在,不能单纯地用图片的元信息来比对。比较笨的办法就是拿要查找的图片的二进制码串与图库中所有图片的二进制码串一一比对,但这种比对非常耗时。我们可以给每一个图片取一个唯一标识,或者说信息摘要。比如,我们可以从图片的二进制码串开头取100个字节,从中间取100个字节,从最后再取100个字节。然后将这300个字节放在一起,通过哈希算法(如MD5),得到一个哈希字符串,用它作为图片的唯一标识,这样可以减少很多工作量。

    应用三:数据校验

    以电驴BT下载软件为例,其下载原理是基于P2P协议。从很多机器并行下载一个2GB的电影,这个电影文件可能会被分割成很多文件块。等所有的文件块都下载完成后,再组装成一个完整的电影文件就行了。

    但是网络传输是不安全的,下载过程中可能出现错误,因此需要校验文件块的安全,正确以及完整。具体的BT协议很复杂,校验方法也很多。就说一下其中的一种思路:通过哈希算法,对100个文件块分别取哈希值,并且保存在种子文件中。哈希算法对数据很敏感,只要文件块内容有一些变化,最后计算出的哈希值完全不同。所以,当文件块下载完成后,可以通过相同的哈希算法,对下载好的文件块逐一求哈希值。然后再跟种子文件中保存的哈希值比对。如果不同,则说明文件块在下载过程中出现错误。

    应用四:散列函数

    散列函数也是哈希算法的一种应用。散列函数是设计一个散列表的关键,直接决定了散列冲突的概率和散列表的性能。但相比于哈希表其他应用,散列函数对于散列算法冲突的要求要低很多。即使出现了个别散列冲突,只要不是过于严重,都可以通过开放寻址法或链表法。

    散列函数对于能否反向解密并不关心。它更关注散列后的值能否平均分布。此外,散列函数执行的快慢,也会影响散列表的性能。故散列函数用的散列算法一般都比较简单,比较追求效率。

    应用五:负载均衡

    如何实现一个会话沾滞的负载均衡算法?也就是说,我们需要在同一个客户端上,在一次会话中所有请求都路由到同一个服务器上。

    最直接的方法就是维护一张映射关系表,内容是客户端IP地址或会话ID与服务器编号的映射关系。客户端发出的每次请求,都要先在映射表中查找应该路由到服务器的编号,然后再请求编号对应的服务器,但有几个弊端:

    1、如果客户端很多,映射表可能会很大,比较浪费内存空间。

    2、客户端下线,上线,服务器扩容、缩容都会导致映射失效,这样维护映射表的成本就会很大。

    但是如果借助哈希算法,对客户端IP地址或会话ID计算哈希值,将取得的哈希值与服务器列表的大小进行取模运算,最终得到的值就应该被路由到服务器编号。

    应用六:数据分片

    哈希算法可以用于数据的分片,举两个例子:

    1、如何统计“搜索关键词”出现的次数?

    假如有1T的日志文件,记录了用户的搜索关键词,我们想要快速统计出每个关键词被搜索的次数。这个问题有两个难点:第一个是搜索日志过大,没办法放到一台机器的内存中。第二个是如果只用一台机器来处理这么巨大的数据,处理时间会很长。

    针对这两个难点,我们可以先对数据进行分片,然后采用多台机器处理的方法,来提高处理速度。具体的思路:为了提高处理的速度,我们用n台机器并行处理。我们从搜索记录的日志文件中,依次读出每个搜索关键词,并且通过哈希函数计算哈希值,然后再跟n取模,最终得到的值,就是应该被分配的机器编号。

    这样,哈希值相同的搜索关键词就分配到同一个机器上,每一个机器分别计算关键词出现的次数,合并起来就是最终结果。

    2、如何快速判断图片是否在图库中?

    同样对数据进行分片,采用多机处理。每次从图库中读取一个图片,计算唯一标识,然后与机器个数n求余取模,得到的值就对应要分配的机器编号,然后将这个图片的唯一标识和图片路径发往对应的机器构建散列表。

    当判断一个图片是否在图库中时,同样通过哈希算法,计算这个图片的唯一标识,然后与机器个数n求余取模。假设得到的值是k,那就去编号k的机器构建的散列表中查找。

    估算一下,1亿个图片构建散列表大约需要多少台机器?假设采用MD5来计算哈希值,那长度为128比特,也就是16字节。文件路径长度上限是256字节,我们假设平均长度是128字节。如果用链表法解决冲突,还需要存储指针,指针只占用8个字节。假设一台机器的内存大小为2GB,散列表装载因子为0.75,故大约1000万(2GB0.75/1522GB*0.75/152)张图片构建散列表。

    针对这种海量数据的处理问题,都可以采用多机分布式处理。

    应用七:分布式存储

    为了提高数据的读取、写入能力,一般都采用分布式的方式来存储数据,比如分布式缓存。如果有大量数据需要缓存,需要将数据分布在多台机器上。借用数据分片的思想,即通过哈希算法对数据取哈希值,然后对机器个数取模,这个最终值就是应存储的缓存机器编号。

    但如果数据增多,原来的10个机器已经无法承受,就需要扩容了。比如扩容到11个机器,这时候麻烦就来了。所有的数据都需要重新计算哈希值。然后重新搬移到正确的机器上,这就相当于缓存中的数据一下子就都失效了。所有的数据请求都会穿透缓存,直接去请求数据库,这样就可能压垮数据库。

    因此,需要一种方法,使得在新加入一个机器后,并不需要做大量的数据搬移——一致性哈希算法。

    假设有k个机器,数据的哈希值的范围是[0,MAX]。我们将整个范围划分成m个小区间(m远大于k),每个机器负责m/k个小区间。当有新机器加入的时候,就将某几个小区间数据从原来的机器中搬移到新的机器中,这样,既不用全部重新哈希,搬移数据,也保持了各机器上数据数量均衡。

    参考资料:王争《数据结构与算法之美》

    展开全文
  • 一、什么是哈希算法? 不管 “ 散列” 还是 “哈希” ,这都是中文翻译的差别,英文其实就是 “ Hash” 。所以常听到有人把 “散列表” 叫做 “哈希表”,“Hash表”,把 “哈希算法” ,叫做 “Hash算法” 或者 ...

    一、什么是哈希算法?


    不管 “ 散列” 还是 “哈希” ,这都是中文翻译的差别,英文其实就是 “ Hash” 。所以常听到有人把 “散列表” 叫做 “哈希表”,“Hash表”,把 “哈希算法” ,叫做 “Hash算法” 或者 “散列算法” 那到底什么是哈希算法?

    将任意长度的二进制串映射为固定长度的二进制串,这个映射规则就是哈希算法

    通过原始数据映射之后得到的二进制值串就是哈希值

    需要满足的要求:

    • 从哈希值不能反向推导出原始数据(单向哈希算法)
    • 原始数据有一点变化,哈希值都会发生巨大不同
    • 散列冲突要很小,对于不同的原始数据,哈希值相同的概率要小
    • 计算效率要高,对于很长的文本,也要很快计算出哈希值

    二、哈希算法的应用


    1、安全加密

    最常用于加密的哈希算法:

    • MD5(Message-Digest Algorithm,MD5消息摘要算法)  
    • SHA(Secure Hash Algorithm.安全散列算法)
    • DES(Data Encryption Standard,数据加密标准)
    • AES(Advanced Encryption Standard,高级加密标准)

    对于加密的哈希算法有两点格外重要:

    • 不能从哈希值推导出原始数据
    • 散列冲突的概率要很小

    无论什么哈希算法,我们只能减少碰撞的概率,理论上无法做到完全不冲突。为什么这么说呢?

    基于数学一个基础的理论:鸽巢原理(也叫抽屉原理)。 10个鸽巢,有11个各自,必然有一个鸽巢数量大于一

    2、唯一标识(消息摘要)

    在海量的图库中寻找一张图是否存在?

        给每个图片取一个唯一标识,或者说消息摘要。比如从图片二进制串码开头取100个字节,中间100字节,最好100字节,然后将300个字节放到一块通过哈希算法得到一个哈希字符串作为图片的唯一标识。

       如果想继续提高效率,可以把每个图片的唯一标识,和相应的图片文件在图库中的路径信息都存储在散列表中。当查看某个图片是否在图库中,通过哈希算法取得唯一标识,在散列表中查找比对,找到后在根据路径获取图片进行全量比对,如果不一样说明两张图片尽管唯一标识相同,但是不是相同图片

    3、数据校验(用于检验数据的完整性和正确性)

     BT的下载原理基于P2P协议。从多个机器下载一个2G的文件将会被分成 很多文件块。等所有文件块下载完成在组装成一个完整的电影文件

     我们可以对每个文件块分别取哈希值保存在种子文件中。当文件下载完成之后,通过相同的哈希算法来逐个文件快校验。如果不同,说明文件块不完整

    4、散列函数

    散列函数也是哈希算法的一种应用

     散列函数对于散列算法冲突的要求要低很多。即便出现冲突,也可以通过开放寻执法或链表法解决

    对是否能从哈希值反推导出原始值也不关心。更加关注的是否能均匀分布

     

    三、哈希算法在分布式中的应用


    5、负载均衡

    负载均衡的算法有很多,比如轮询,随机,加权轮询等。如何实现一个会话粘滞的负载均衡算法呢?也就是说需要在同一客户端,在一次会话中的所有请求都路由到同一个服务器上。

     答: 维护一张映射表,表的内容是客户端的IP地址或者会话ID与服务器编号的映射关系。客户端每一次请求都要先在映射表中查找路由到的服务器编号。然后再请求编号对应的服务器。  

    弊端:

    • 如果客户端很多就需要维护更多的映射关系
    • 客户端上线下线,服务器扩容,缩容都会导致映射失败,维护映射表成本大

    借助哈希算法就可以轻松解决。通过哈希算法对客户端IP地址或者会话ID计算哈希值,然后与服务器的大小进行取模运算。最终得到的值就是对应的服务器编号。这样就可以把同一个IP的请求路由到同一个后端服务器上。

    6、数据分片

    两个例子:

     1)如何统计‘搜索关键词’的出现次数?

        假如有1T的日志文件,记录了用户的搜索关键词,如何快速统计每个关键词被搜索的此说呢?

        难点:数据量太大,无法放在一台机器的内存中,如果只有一台机器处理,时间会很长

        因此我们用n台机器并行处理。从搜素记录中依次读取关键词,通过哈希函数计算出哈希值然后跟n取模运算,最终得到的值,就是被分配到的机器号

        这样相同的关键词就被分散到同一机器。每个机器分别计算关键词出现的次数,最后合并就是最终的结果

     2)如何快速判断图片是否在图库中?

         假如有一亿张图片,显然在一台机器构建散列表是行不通的,因为一台机器的内存有限

         我们需要n台机器,用哈希算法取每张图片的唯一标识,在和n求余取模运算,得到 的就是要分到的机器号,然后把唯一标识和路径发往这台机器构建散列表。当我们查找一个图片时,就用同样的哈希算法得到哈希值和n取模运算,假如得到的是k,就去k这台机器寻找

       针对海量的数据,可以用多机分布式处理。借用这中分片的思想,可以突破单机内存,和CPU的限制

    7、分布式存储 

    面对海量的数据和海量的用户,为了提高数据的读取和写入能力,一般都采用分布式来存储数组,比如分布式缓存。海量的数据需要缓存,一个缓存机器肯定是不够的,所以需要将数据分布在多台机器

    借用数据分片的思想,通过哈希算法对数据取哈希值,然后对机器个数取模,这个最终值就是存储的缓存机编号

    但是数据增多,需要扩容,比如扩到11个机器。原来的数据通过与 10 来取模的。比如13这个数组,存储在编号为3机器上。但是新增一个机器,对数据按照11取模,原来这个数据就被分配到2号机器上了

     因此,所以数据都要重新计算哈希值,然后搬移到正确的机器上。缓存中的数据全部失效。所有的数据请求都会穿透缓存,直接取请求数据库。这样就可能发送雪崩效应,压垮数据库

    解决方案是什么?
    ①这时,需要一种方法,使得新加入一个机器后,并不需要做大量的数据搬移。那就是在分布式系统中应用非常广泛的一致性哈希算法。
    ②一致性哈希算法的基本思想是什么呢?为了说清楚这个问题,我们假设有k个机器,数据的哈希值范围是[0-MAX],我们将整个范围划分成m个小区间(m远大于k),每个机器复负责m/k个小区间。当有新机器加入的时候,我们就将某几个小区间的数据,从原来的机器中搬移到新的机器中。这样,既不用全部重新哈希、搬移数据,也保持了各个机器上数据量的均衡。

    一致性哈希算法漫画图解

     

    展开全文
  • 数据结构与算法】哈希算法原理和应用详解!

    千次阅读 多人点赞 2021-06-23 16:01:00
    在程序员的实际开发中,哈希算法常常能用得到,本文以哈希算法原理和应用为核心,和大家详细讲解一下哈希算法的概念、常见算法以及原理、在信息安全的应用等等。 一、概念 哈希表就是一种以 键-值(key-...
  • 数据结构算法哈希

    千次阅读 多人点赞 2020-05-22 19:24:29
    目录数据结构算法哈希表一、哈希原理(一)、概念1. 哈希表定义2. 哈希函数3. 哈希冲突(二)、哈希函数的设计(三)、哈希冲突的解决1. 开放寻址法2. 链表寻址法二、练习实现三、扩展 一、哈希原理 该部分主要...
  • 哈希算法历史悠久,业界著名的哈希算法也有很多,比如MD5、SHA等。那么在实际的开发中,我们该如何用哈希算法解决问题。 二、什么是哈希算法 将任意长度的二进制值映射为固定长度的二进制值串,这个映...
  • 数据结构与算法分析:(十一)散列表(上) 数据结构与算法分析:(十二)散列表(下) 可见散列表的重要性!那讲哈希算法为啥把前两篇的散列表的文章贴出了呢?难道它们有什么关系?没错,有关系,而且关系还很大。...
  • 感知哈希算法原理与实现

    千次阅读 2016-03-27 19:11:18
    今天忽然想做一个图像识别的APP,但是在两张图片相似度的问题上产生了问题,感知哈希算法并不能解决这个问题,只是我在试着解决问题的过程中学到的一点知识。这里的关键技术叫做”感知哈希算法”(Perceptual hash ...
  • 计算与数据结构篇 - 哈希算法 (Hash)

    万次阅读 多人点赞 2020-01-21 14:02:00
    计算与数据结构篇 - 哈希算法 (Hash) 哈希算法的定义和原理非常简单,基本上一句话就可以概括了。将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二...
  • 开篇说明:本文内容大部分出自于极客时间中的《数据结构算法之美》专栏,Mark下来,作为个人笔记,方便日后复习。 在上一篇博客中,讲解了散列表的用法,如果你对散列表还不是很了解,可以点击此链接进行查看:...
  • MySQL索引背后的数据结构算法原理
  • MySQL索引的数据结构以及算法原理

    万次阅读 多人点赞 2018-04-19 22:13:28
    写在前面的话 在编程领域有一句人尽皆知的法则“程序 = 数据结构 + 算法”,我个人是不太赞同这句话(因为我觉得程序不仅仅是数据结构算法),但是在日常的学习和工作中我确认深深感受到数据结构算法的重要性,...
  • MySQL索引背后的数据结构算法原理

    万次阅读 2018-06-26 16:08:13
    特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等。为了避免混乱,本文将只关注于BTree索引,因为这是平常...
  • 数据结构 哈希表的原理和代码实现

    千次阅读 2017-06-11 20:18:36
    哈希法又称散列法、杂凑法以及关键字地址计算法等,相应的表称为哈希表。这种方法的基本思想是:首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f,使得p=f(k),f称为哈希函数。创建哈希表时,把关键字为...
  • 03-一致性哈希算法 java 实现 04-负载均衡算法 java 实现 概念 一致哈希是一种特殊的哈希算法。 在使用一致哈希算法后,哈希表槽位数(大小)的改变平均只需要对 K/n个关键字重新映射,其中K是关键字的数量, n是槽...
  • 哈希算法的定义和原理非常简单,基本上一句话就可以概括了。将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。 哈希算法的应用...
  • Mysql数据结构算法原理

    万次阅读 2018-04-06 21:01:42
    特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等。为了避免混乱,本文将只关注于BTree索引,因为这是平常...
  • 数组也是有一定的缺点的,如果我们不知道某个元素的下标值,而只是知道该元素在数组中,这时我们想要获取该元素就只能对数组进行线性查找,即从头开始遍历,...所以,为了解决上述数组的不足之处,引入了哈希表的概念。
  • 数据结构-哈希原理详解

    千次阅读 2017-08-05 14:05:35
    (摘自百度百科):散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列...
  • 数据结构算法学习笔记

    万次阅读 多人点赞 2018-09-25 13:55:49
    本文是王争老师的《算法数据结构之美》的学习笔记,详细内容请看王争的专栏。有不懂的地方指出来,我做修改。 数据结构算法思维导图 数据结构指的是“一组数据的存储结构”,算法指的是“操作数据的一组...
  • 哈希算法

    万次阅读 多人点赞 2019-01-21 14:51:16
    对于哈希算法,在我们平时的开发中,都是基本上拿来就用就行了,所以这节我们将重点放在如何使用,并不进行哈希算法原理剖析和如何设计一个哈希算法的讲解. 什么是哈希算法? 将任意长度的二进制值串映射为固定...
  •  哈希算法的定义和原理:将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则,就是哈希算法。而通过原始数据映射之后得到的二进制值串就是哈希值。  设计一个优秀的哈希算法,需要满足下面几点...
  • 1 数据结构算法基础1.1 索引的本质 MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。也就是说索引是数据结构 数据库查询是数据库的最主要功能之一。数据本身的组织结构不可能完全...
  • 搞定哈希算法

    千次阅读 2019-10-09 20:01:46
    1、基本概念 哈希算法历史悠久,业界著名的... 从哈希值不能反向推导出原始数据(所有哈希算法也叫单向哈希算法); 对输入数据非常敏感,哪怕原始数据只修改了一个Bit,最后得到的哈希值大小也大不相同; ...
  • 哈希算法原理

    千次阅读 2018-04-22 16:43:48
    原文地址:...基本概念哈希表(Hash Table)是一种根据关键字直接访问内存存储位置的数据结构。通过哈希表,数据元素的存放位置和数据元素的关键字之间建立起某种对应关系,建立这种...
  • python数据结构算法——哈希

    千次阅读 2018-02-26 15:02:11
    python数据结构算法——哈希表 参考翻译自:《复杂性思考》 及对应的online版本:http://greenteapress.com/complexity/html/thinkcomplexity004.html 使用哈希表可以进行非常快速的查找操作,查找时间为常数,...
  • 算法:哈希算法

    2019-05-06 11:26:08
    网站是怎么存储用户的密码这些...所谓哈希算法,其实就是将任意长度的二进制值串映射为固定长度的二进制值串,这个映射的规则就是哈希算法,而通过原始数据映射之后得到的二进制值串就是哈希值。 要设计出一个优...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 66,836
精华内容 26,734
热门标签
关键字:

数据结构哈希算法原理

数据结构 订阅