精华内容
下载资源
问答
  • 哈希查找算法

    2021-10-11 10:21:16
    哈希查找算法适用于大多数场景,既支持在有序序列中查找目标元素,也支持在无序序列中查找目标元素。讲解哈希查找算法之前,我们首先要搞清楚什么是哈希表。 哈希表是什么 哈希表(Hash table)又称散列表,是一种...

    哈希查找算法又称散列查找算法,是一种借助哈希表(散列表)查找目标元素的方法,查找效率最高时对应的时间复杂度为 O(1)。

    哈希查找算法适用于大多数场景,既支持在有序序列中查找目标元素,也支持在无序序列中查找目标元素。讲解哈希查找算法之前,我们首先要搞清楚什么是哈希表。

    哈希表是什么

    哈希表(Hash table)又称散列表,是一种存储结构,通常用来存储多个元素。

    和其它存储结构(线性表、树等)相比,哈希表查找目标元素的效率非常高。每个存储到哈希表中的元素,都配有一个唯一的标识(又称“索引”或者“键”),用户想查找哪个元素,凭借该元素对应的标识就可以直接找到它,无需遍历整个哈希表。

    多数场景中,哈希表是在数组的基础上构建的,下图给大家展示了一个普通的数组:

    使用数组构建哈希表,最大的好处在于:可以直接将数组下标当作已存储元素的索引,不再需要为每个元素手动配置索引,极大得简化了构建哈希表的难度。

    我们知道,在数组中查找一个元素,除非提前知晓它存储位置处的下标,否则只能遍历整个数组。哈希表的解决方案是:各个元素并不从数组的起始位置依次存储,它们的存储位置由专门设计的函数计算得出,我们通常将这样的函数称为哈希函数

    哈希函数类似于数学中的一次函数,我们给它传递一个元素,它反馈给我们一个结果值,这个值就是该元素对应的索引,也就是存储到哈希表中的位置。

    举个例子,将 {20, 30, 50, 70, 80} 存储到哈希表中,我们设计的哈希函数为 y=x/10,最终各个元素的存储位置如下图所示:
    在这里插入图片描述
    在图 2 的基础上,假设我们想查找元素 50,只需将它带入 y=x/10 这个哈希函数中,计算出它对应的索引值为 5,直接可以在数组中找到它。借助哈希函数,我们提高了数组中数据的查找效率,这就是哈希表存储结构。

    构建哈希表时,哈希函数的设计至关重要。假设将 {5, 20, 30, 50, 55} 存储到哈希表中,哈希函数是 y=x%10,各个元素在数组中的存储位置如下图所示:
    在这里插入图片描述

    可以看到,5 和 55 以及 20、30 和 50 对应的索引值是相同的,它们的存储位置发生了冲突,我们习惯称为哈希冲突或者哈希碰撞。设计一个好的哈希函数,可以降低哈希冲突的出现次数。哈希表提供了很多解决哈希冲突的方案,比如线性探测法、再哈希法、链地址法等。

    本节我们使用线性探测法解决哈希冲突,解决方法是:当元素的索引值(存储位置)发生冲突时,从当前位置向后查找,直至找到一个空闲位置,作为冲突元素的存储位置。仍以图 3 中的哈希表为例,使用线性探测法解决哈希冲突的过程是:

    • 元素 5 最先存储到数组中下标为 5 的位置;
    • 元素 20 最先存储到数组中下标为 0 的位置;
    • 元素 30 的存储位置为 0,和 20 冲突,根据线性探测法,从下标为 0 的位置向后查找,下标为 1 的存储位置空闲,用来存储 30;
    • 元素 50 的存储位置为 0,和 20 冲突,根据线性探测法,从下标为 0 的位置向后查找,下标为 2 的存储位置空闲,用来存储 50;
    • 元素 55 的存储位置为 5,和 5 冲突,根据线性探测法,从下标为 5 的位置向后查找,下标为 6 的存储位置空闲,用来存储 55。

    借助线性探测法,最终 {5, 20, 30, 50, 55} 存储到哈希表中的状态为:
    在这里插入图片描述
    假设我们从图 4 所示的哈希表中查找元素 50,查找过程需要经过以下几步:

    • 根据哈希函数 y=x%10,目标元素的存储位置为 0,但经过和下标为 0 处的元素 20 比较,该位置存储的并非目标元素;
    • 根据线性探测法,比较下标位置为 1 处的元素 30,也不是目标元素;
    • 继续比较下标位置为 2 的元素 50,成功找到目标元素。
      对于发生哈希冲突的哈希表,尽管查找效率会下降,但仍比一些普通存储结构(比如数组)的查找效率高。

    对于发生哈希冲突的哈希表,尽管查找效率会下降,但仍比一些普通存储结构(比如数组)的查找效率高。

    哈希查找算法

    哈希查找算法就是利用哈希表查找目标元素的算法。对于给定的序列,该算法会先将整个序列存储到哈希表中,然后再查找目标元素。

    例如,哈希查找算法查找 {5, 20, 30, 50, 55} 序列中是否有 50 这个元素,实现的c语言代码如下:

    #include <stdio.h>
    #define N 10   //指定哈希表的长度
    //自定义哈希函数
    int hash(int value) {
        return value % 10;
    }
    //创建哈希表
    void creatHash(int arr[5], int hashArr[N]) {
        int i,index;
        //将序列中每个元素存储到哈希表
        for (i = 0; i < 5; i++) {
            index = hash(arr[i]);
            while(hashArr[index % N] != 0) {
                index++;
            }
            hashArr[index] = arr[i];
        }
    }
    
    //实现哈希查找算法,hashArr 表示哈希表,value 为要查找的目标元素
    int hash_search(int* hashArr, int value) {
        int hashAdd = hash(value);             //查找目标元素所在的索引
        while (hashArr[hashAdd] != value) {    // 如果索引位置不是目标元素,则发生了碰撞
            hashAdd = (hashAdd + 1) % N;       // 根据线性探测法,从索引位置依次向后探测
            //如果探测位置为空,或者重新回到了探测开始的位置(即探测了一圈),则查找失败
            if (hashArr[hashAdd] == 0 || hashAdd == hash(value)) {
                return -1;
            }
        }
        //返回目标元素所在的数组下标
        return  hashAdd;
    }
    
    int main()
    {  
        int hashAdd;
        int hashArr[N] = { 0 };
        int arr[5] = {  };
        creatHash(arr, hashArr);
    
        hashAdd = hash_search(hashArr, 50);
        //如果返回值为 -1,表明查找失败,反之则返回目标元素所在的位置
        if (hashAdd == -1) {
            printf("查找失败\n");
        }
        else {
            printf("查找成功,目标元素所在哈希表中的下标为:%d", hashAdd);
        }
        return 0;
    }
    

    如下是使用哈希查找算法在 {5, 20, 30, 50, 55} 序列中查找 50 的 Java 程序:

    public class Demo {
        //哈希函数
        public static int hash(int value) {
            return value % 10;
        }
        //创建哈希表
        public static void creatHash(int [] arr,int [] hashArr) {
         int i,index;
            //将序列中每个元素存储到哈希表
            for (i = 0; i < 5; i++) {
                index = hash(arr[i]);
                while(hashArr[index % 10] != 0) {
                    index++;
                }
                hashArr[index] = arr[i];
            }
        }
        //实现哈希查找算法
        public static int hash_serach(int [] hashArr,int value) {
            //查找目标元素对应的索引值
            int hashAdd = hash(value);
            while (hashArr[hashAdd] != value) {    // 如果索引位置不是目标元素,则发生了碰撞
                hashAdd = (hashAdd + 1) % 10;       // 根据线性探测法,从索引位置依次向后探测
                //如果探测位置为空,或者重新回到了探测开始的位置(即探测了一圈),则查找失败
                if (hashArr[hashAdd] == 0 || hashAdd == hash(value)) {
                    return -1;
                }
            }
            //返回目标元素所在的数组下标
            return  hashAdd;
        }
        public static void main(String[] args) {
            int [] arr = new int[] {5, 20, 30, 50, 55};
            int[] hashArr = new int[10];
            //创建哈希表
            creatHash(arr,hashArr);
            // 查找目标元素 50 位于哈希表中的位置
            int hashAdd = hash_serach(hashArr,50);
            if(hashAdd == -1) {
                System.out.print("查找失败");
            }else {
                System.out.print("查找成功,目标元素所在哈希表中的下标为:" + hashAdd);
            }
        }
    }
    

    如下是使用哈希查找算法在 {5, 20, 30, 50, 55} 序列中查找 50 的 Python 程序:

    # 自定义哈希函数
    def hash(hashArr,value):
        return value % len(hashArr)
    
    #创建哈希表
    def createHash(arr,hashArr):
        for ele in arr:
            index = hash(hashArr,ele)
            while hashArr[index % len(hashArr)] != 0:
                index = index + 1
            hashArr[index] = ele
       
    # 实现哈希查找算法,hashArr 表示哈希表,value 为要查找的目标元素
    def hash_search(hashArr,value):
        hashAdd = hash(hashArr,value)            # 查找目标元素所在的索引
        while hashArr[hashAdd] != value: # 如果索引位置不是目标元素,则发生了碰撞
            hashAdd = (hashAdd + 1) % len(hashArr) # 根据线性探测法,从索引位置依次向后探测
            #如果探测位置为空,或者重新回到了探测开始的位置(即探测了一圈),则查找失败
            if (hashArr[hashAdd] == 0) or (hashAdd == hash(hashArr,value)):
                return -1
        return hashAdd   # 返回目标元素所在的数组下标
    
    #待查找序列
    arr = [5, 20, 30, 50, 55]
    #构建哈希表
    hashArr = [0]*10
    createHash(arr,hashArr)
    # 查找元素 50 的位置
    hashAdd = hash_search(hashArr,50)
    if hashAdd == -1:
        print("查找失败\n")
    else:
        print("查找成功,目标元素所在哈希表中的下标为 %d" % (hashAdd))
    

    以上程序的输出结果均为:

    找成功,目标元素所在哈希表中的下标为 2
    

    C哈希表

    原文链接a hash table for C structures

    任何 C 结构都可以使用 uthash 存储在哈希表中。只需在结构中添加一个UT_hash_handle,并选择结构中的一个或多个字段作为密钥。然后使用这些宏来存储、检索或删除哈希表中的项目。
    Example 1. Adding an item to a hash.

    #include "uthash.h"
    
    struct my_struct {
        int id;            /* we'll use this field as the key */
        char name[10];
        UT_hash_handle hh; /* makes this structure hashable */
    };
    
    struct my_struct *users = NULL;
    
    void add_user(struct my_struct *s) {
        HASH_ADD_INT( users, id, s );
    }
    
    

    Example 2. Looking up an item in a hash.

     struct my_struct *find_user(int user_id) {
        struct my_struct *s;
    
        HASH_FIND_INT( users, &user_id, s );
        return s;
    }
    
    

    Example 3. Deleting an item from a hash.

    void delete_user(struct my_struct *user) {
        HASH_DEL( users, user);
    }
    
    
    展开全文
  • 哈希算法(哈希函数)基本

    千次阅读 2021-09-19 16:33:42
    一、什么是哈希(Hash) 哈希也称“散列”函数或“杂凑”函数。它是一个不可逆的单向映射,将任意长度的输入消息M(或文件F)映射成为一个较短的定长哈希值H(M),也叫散列值(HashValue)、杂凑值或消息摘要。...

    目录

    一、什么是哈希(Hash)

    二、哈希的原理和特点

    三、哈希的实际用途

    四、典型的哈希函数

    (一)MD5

    (二)SHA

    五、Hash构造函数的方法


    一、什么是哈希(Hash)

    哈希也称“散列”函数或“杂凑”函数。它是一个不可逆的单向映射,将任意长度的输入消息M(或文件F)映射成为一个较短的定长哈希值H(M),也叫散列值(HashValue)、杂凑值或消息摘要。可见,这是一种单向密码体制,只有加密过程,没有解密过程(因此Hash求逆很困难)。

    二、哈希的原理和特点

    1. 单向性:从哈希值不能反向推导原始数据(计算不可行),即从哈希输出无法倒推输入的原始数值。这是哈希函数安全性的基础。
    2. 灵敏性:对输入数据敏感,哪怕只改了一个Bit,得到的哈希值也大不相同。换言之,消息M的任何改变都会导致哈希值H(M)发生改变。
    3. 易压易算:Hash本质上是把一个大范围集合映射到另一个小范围集合。故输入值的个数必须与小范围相当或者更小,不然冲突就会很多。所以,哈希算法执行效率要高,散列结果要尽量均衡。
    4. 抗碰撞性:理想Hash函数是无碰撞的,但实际上很难做到这一点。有两种抗碰撞性:一种是弱抗碰撞性,即对于给定的消息,要发现另一个消息,满足在计算上是不可行的;另一种是强抗碰撞性,即对于任意一对不同的消息,使得在计算上也是不可行的。

    也可以这么理解正向快速、逆向困难、输入敏感、冲突避免

    三、哈希的实际用途

    Hash能把一个大范围映射到一个小范围,能对输入数据或文件进行校验,还可用于查找等。具体的:

    1. 唯一标识或数据检验:能够对输入数据或文件进行校验,判断是否相同或是否被修改。如图片识别,可针对图像二进制流进行摘要后MD5,得到的哈希值作为图片唯一标识;如文件识别,服务器在接受文件上传时,对比两次传送文件的哈希值,若相同则无须再次上传(传统的奇偶校验和CRC校验一定程度上能检测并纠正数据传输中的信道误码,但没有抗数据篡改的能力)。
    2. 安全加密:对于敏感数据比如密码字段进行MD5或SHA加密传输。哈希算法还可以检验信息的拥有者是否真实。如,用保存密码的哈希值代替保存密码,基本可以杜绝泄密风险。
    3. 数字签名。由于非对称算法的运算速度较慢,所以在数字签名协议中,单向散列函数扮演了一个重要的角色。对Hash值,又称“数字摘要”进行数字签名,在统计上可以认为与对文件本身进行数字签名是等效的。
    4. 散列函数:是构造散列表的关键。它直接决定了散列冲突的概率和散列表的性质。不过相对哈希算法的其他方面应用,散列函数对散列冲突要求较低,出现冲突时可以通过开放寻址法或链表法解决冲突。对散列值是否能够反向解密要求也不高。反而更加关注的是散列的均匀性,即是否散列值均匀落入槽中以及散列函数执行的快慢也会影响散列表性能。所以散列函数一般比较简单,追求均匀和高效。
    5. *负载均衡:常用的负载均衡算法有很多,比如轮询、随机、加权轮询。如何实现一个会话粘滞的负载均衡算法呢?可以通过哈希算法,对客户端IP地址或会话SessionID计算哈希值,将取得的哈希值与服务器列表大小进行取模运算,最终得到应该被路由到的服务器编号。这样就可以把同一IP的客户端请求发到同一个后端服务器上。
    6. *数据分片:比如统计1T的日志文件中“搜索关键词”出现次数该如何解决?我们可以先对日志进行分片,然后采用多机处理,来提高处理速度。从搜索的日志中依次读取搜索关键词,并通过哈希函数计算哈希值,然后再跟n(机器数)取模,最终得到的值就是应该被分到的机器编号。这样相同哈希值的关键词就被分到同一台机器进行处理。每台机器分别计算关键词出现的次数,再进行合并就是最终结果。这也是MapReduce的基本思想。再比如图片识别应用中给每个图片的摘要信息取唯一标识然后构建散列表,如果图库中有大量图片,单机的hash表会过大,超过单机内存容量。这时也可以使用分片思想,准备n台机器,每台机器负责散列表的一部分数据。每次从图库取一个图片,计算唯一标识,然后与机器个数n求余取模,得到的值就是被分配到的机器编号,然后将这个唯一标识和图片路径发往对应机器构建散列表。当进行图片查找时,使用相同的哈希函数对图片摘要信息取唯一标识并对n求余取模操作后,得到的值k,就是当前图片所存储的机器编号,在该机器的散列表中查找该图片即可。实际上海量数据的处理问题,都可以借助这种数据分片思想,突破单机内存、CPU等资源限制。
    7. *分布式存储:一致性哈希算法解决缓存等分布式系统的扩容、缩容导致大量数据搬移难题。

    四、典型的哈希函数

    常见Hash算法有MD5和SHA系列,目前MD5和SHA1已经被破解,一般推荐至少使用SHA2-256算法。

    (一)MD5

    MD5属于Hash算法中的一种,它输入任意长度的信息,在处理过程中以512位输入数据块为单位,输出为128位的信息(数字指纹)。常用场景:

    1、防篡改,保障文件传输可靠性:如SVN中对文件的控制;文件下载过程中,网站提供MD5值供下载后判断文件是否被篡改;BT中对文件块进行校验的功能。

    2、增强密码保存的安全性:例如网站将用户密码的MD5值保存,而不是存储明文用户密码,当然,还会加SALT,进一步增强安全性。

    3、数字签名:在部分网上赌场中,使用MD5算法来保证过程的公平性,并使用随机串进行防碰撞,增加解码难度。

    算法实现过程:

    第一步:消息填充,补长到512的倍数。最后64位为消息长度(填充前的长度)的低64位,一定要补长(64+1~512),内容为100…0(如若消息长448,则填充512+64)。

    第二步:分割,把结果分割为512位的块:Y0,Y1,…(每一个有16个32比特长字)。

    第三步:计算,初始化MD buffer,128位常量(4个32bit字),进入循环迭代,共L次。每次一个输入128位,另一个输入512位,结果输出128位,用于下一轮输入。

    第四步:输出,最后一步的输出即为散列结果128位。

    (二)SHA-1  Secure Hash Algorithm

    安全哈希算法(Secure Hash Algorithm)主要适用于数字签名标准(Digital Signature Standard DSS)里面定义的数字签名算法(Digital Signature Algorithm DSA)。对于长度小于2^64b的消息,SHA-1将输入流按照每块512b(64B)进行分块,并产生20B或160b的信息摘要。

    https://images2015.cnblogs.com/blog/929265/201607/929265-20160701092331874-1851324775.png

    1.补位

    消息补位使其长度在对512取模以后的余数是448。也就是说,(补位后的消息长度)% 512 = 448。即使长度已经满足对512取模后余数是448,补位也必须要进行。

    补位是这样进行的:先补一个1,然后再补0,直到长度满足对512取模后余数是448。总而言之,补位是至少补一位,最多补512位。还是以前面的“abc”为例显示补位的过程。

    原始信息:  011000010110001001100011

    补位第一步:0110000101100010011000111,首先补一个“1”

    补位第二步:01100001011000100110001110…..0,然后补423个“0”

    我们可以把最后补位完成后的数据用16进制写成下面的样子,确保是448b:

    61626380000000000000000000000000

    00000000000000000000000000000000

    00000000000000000000000000000000

    0000000000000000

    2.补长度

    补长度是将原始数据的长度补到已经进行了补位操作的消息后面。通常用一个64位的数据来表示原始消息的长度。如果消息长度不大于2^64,那么第一个字就是0。

    在进行了补长度的操作以后,整个消息就变成下面这样了(16进制格式):

    61626380000000000000000000000000

    00000000000000000000000000000000

    00000000000000000000000000000000

    00000000000000000000000000000018

    如果原始的消息长度超过了512,我们需要将它补成512的倍数。然后我们把整个消息分成一个一个512位的数据块。分别处理每一个数据块,从而得到消息摘要。

    3.使用的常量

    一系列的常量字K(0),K(1),...,K(79),如果以16进制给出。它们如下:

    Kt=0x5A827999(0<=t<=19)

    Kt=0x6ED9EBA1(20<=t<=39)

    Kt=0x8F1BBCDC(40<=t<=59)

    Kt=0xCA62C1D6(60<=t<=79).

    4.需要使用的函数

    在SHA1中我们需要一系列的函数。每个函数ft(0<=t<=79)都操作32位字B,C,D并且产生32位字作为输出。

    ft(B,C,D)可以如下定义:

    ft(B,C,D)=(BANDC)or((NOTB)ANDD)(0<=t<=19)

    ft(B,C,D)=BXORCXORD(20<=t<=39)

    ft(B,C,D)=(BANDC)or(BANDD)or(CANDD)(40<=t<=59)

    ft(B,C,D)=BXORCXORD(60<=t<=79).

    5.计算消息摘要

    必须使用进行了补位和补长度后的消息来计算消息摘要。计算需要两个缓冲区,每个都由5个32位的字组成,还需要一个80个32位字的缓冲区。第一个5个字的缓冲区被标识为A,B,C,D,E。第一个5个字的缓冲区被标识为H0,H1,H2,H3,H4。80个字的缓冲区被标识为W0,W1,...,W79。

    另外还需要一个一个字的TEMP缓冲区。

    为了产生消息摘要,在第4部分中定义的16个字的数据块M1,M2,...,Mn会依次进行处理,处理每个数据块Mi包含80个步骤。


    在处理每个数据块之前,缓冲区{Hi}被初始化为下面的值(16进制)

    H0=0x67452301

    H1=0xEFCDAB89

    H2=0x98BADCFE

    H3=0x10325476

    H4=0xC3D2E1F0.


    现在开始处理M1,M2,...,Mn。为了处理Mi,需要进行下面的步骤

    (1)将Mi分成16个字W0,W1,...,W15,W0是最左边的字

    (2)对于t=16到79令Wt=S1(Wt-3XORWt-8XORWt-14XORWt-16).

    (3)令A=H0,B=H1,C=H2,D=H3,E=H4.

    (4)对于t=0到79,执行下面的循环

    TEMP=S5(A)+ft(B,C,D)+E+Wt+Kt;

    E=D;D=C;C=S30(B);B=A;A=TEMP;

    (5)令H0=H0+A,H1=H1+B,H2=H2+C,H3=H3+D,H4=H4+E.

    在处理完所有的Mn,后,消息摘要是一个160位的字符串,以下面的顺序标识H0H1H2H3H4。

    (三)SHA-2系列

    SHA-2是六个不同算法的合称,包括:SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。除了生成摘要的长度、循环运行的次数等一些微小差异外,这些算法的基本结构是一致的。对于任意长度的消息,SHA256都会产生一个256bit长的消息摘要。

    详细参见:sha256算法原理 - Practical - 博客园

    至今尚未出现对SHA-2有效的攻击,SHA-2和SHA-1并没有接受公众密码社区的详细检验,所以它们的密码安全性还不被广泛信任。

    总体上,HAS-256与MD4、MD5以及HSA-1等哈希函数的操作流程类似,在哈希计算之前首先要进行以下两个步骤:

    • 对消息进行补位处理,最终的长度是512位的倍数;
    • 以512位为单位对消息进行分块为M1,M2,…,Mn
    • 处理消息块:从一个初始哈希H0开始,迭代计算:Hi = Hi-1 + CMi(Hi-1)

    其中C是SHA256的压缩函数,+是mod 2^32加法,Hn是消息区块的哈希值。

    五、Hash构造函数的方法

    1.直接定址法(极少用)

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

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

    2.数字分析法

    假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us),分析关键字集中的全体,并从中提取分布均匀的若干位或它们的组合作为地址。数字分析法是取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法。即当关键字的位数很多时,可以通过对关键字的各位进行分析,丢掉分布不均匀的位,作为哈希值。它只适合于所有关键字值已知的情况。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间。

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

    3.折叠法

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

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

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

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

    4.平方取中法

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

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

    5.减去法



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

    6.基数转换法

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

    7.除留余数法

    假设哈希表长为m,p为小于等于m的最大素数,则哈希函数为h(k)=k%p,其中%为模p取余运算。除留余数法的模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」

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

    10.字符串数值哈希法

    把字符串的前10个字符的ASCⅡ值之和对N取摸作为Hash地址,只要N较小,Hash地址将较均匀分布[0,N]区间内。对于N很大的情形,可使用ELFHash(ExecutableandLinkingFormat,ELF,可执行链接格式)函数,它把一个字符串的绝对长度作为输入,并通过一种方式把字符的十进制值结合起来,对长字符串和短字符串都有效,这种方式产生的位置可能不均匀分布。

    11.旋转法

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

    展开全文
  • 哈希表的长度最好是素数表中的数,哈希表扩容的时候也是从哈希表中取得,扩容后需要把原来表中的数据重新哈希,存入新的哈希表 装载因子:当表的使用量 超过 总容量 * 装载因子 时,需要进行扩容,使用哈希表的 均摊...

    一、哈希表

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    二、线性探测哈希表

    哈希表的长度最好是素数表中的数,哈希表扩容的时候也是从哈希表中取得,扩容后需要把原来表中的数据重新哈希,存入新的哈希表

    装载因子:当表的使用量 超过 总容量 * 装载因子 时,需要进行扩容,使用哈希表的 均摊时间复杂度是O(1)

    在这里插入图片描述

    enum State {
    	UNUSE,    // 从未被使用
    	USING,    // 正在使用
    	DELETE    // 使用后被删除
    };
    
    struct Node {
    	Node(int val = 0, State state = UNUSE) 
    		:val_(val)
    		, state_(state)
    	{}
    	int val_;
    	State state_; // 节点的状态
    };
    
    class HashTable {
    public:
    	HashTable(int cap = primes_[0], double load_factor = 0.75)
    		: load_factor_(load_factor)
    		, prime_idx(0)
    		, size_(0)
    	{
    		// 如果用户传入的cap不符合素数表,需要重新指定cap_
    		if (cap != primes_[0]) {
    			for (; prime_idx < PRIMES_SIZE; prime_idx++) {
    				if (primes_[prime_idx] >= cap) {
    					break;
    				}
    			}
    			// 用户传入的cap过大,不合法,重新指定cap_
    			if (prime_idx == PRIMES_SIZE) {
    				prime_idx--;
    			}
    		}
    		cap_ = primes_[prime_idx];
    		table_ = new Node[cap_];
    	}
    	
    	~HashTable() {
    		delete[] table_;
    		table_ = nullptr;
    	}
    
    public:
    	// 可以插入重复的val
    	bool insert(int val) {
    		cout << "哈希表使用因子:" << size_ * 1.0 / cap_ << endl;
    		if (size_ >= load_factor_ * cap_) {
    			cout << "当前使用:" << size_ << " 哈希表总容量:" << cap_ << " 需要扩容" << endl;
    			expand();
    			cout << "扩容完成,当前容量:"<<cap_ << endl;
    		}
    
    		int start = val % cap_;
    		int idx = start;
    		do {
    			if (table_[idx].state_ != USING) {
    				table_[idx].state_ = USING;
    				table_[idx].val_ = val;
    				size_++;
    				return true;
    			}
    			idx = (idx + 1) % cap_;
    		} while (idx != start);
    
    		return false;
    	}
    
    	// 删除所有val
    	bool erase(int val) {
    		int start = val % cap_;
    		int idx = start;
    		do {
    			// 在用 && 找到
    			if (table_[idx].state_ == USING && table_[idx].val_ == val) {
    				table_[idx].state_ = DELETE;
    				size_--;
    			}
    			idx = (idx + 1) % cap_;
    		} while (table_[idx].state_ != UNUSE && idx != start);  // 若碰到了UNUSE,则说明后面肯定没有自己要找的val了
    		return true;
    	}
    	
    	// 找到val返回对应的key,找不到返回-1
    	int find(int val) {
    		int start = val % cap_;
    		int idx = start;
    		do {
    			// 在用 && 找到
    			if (table_[idx].state_ == USING && table_[idx].val_ == val) {
    				return idx;
    			}
    			idx = (idx + 1) % cap_;
    		} while (table_[idx].state_ != UNUSE && idx != start);  // 若碰到了UNUSE,则说明后面肯定没有自己要找的val了
    		return -1;
    	}
    
    private:
    	void expand() {
    		prime_idx++;
    		if (prime_idx == PRIMES_SIZE) {
    			throw "current hashtable is too large, can't expand anymore!";
    		}
    		Node* tmp = new Node[primes_[prime_idx]];
    		for (int i = 0; i < cap_; i++) {
    			if (table_[i].state_ == USING) {
    				// 取出旧表中的元素,在新表中重新哈希
    				int start = table_[i].val_ % primes_[prime_idx];
    				int idx = start;
    				do {
    					if (tmp[idx].state_ != USING) {
    						tmp[idx].state_ = USING;
    						tmp[idx].val_ = table_[i].val_;
    						break;       // 新表中插入一个元素后,就可以跳出查找位置的while循环
    					}
    					idx = (idx + 1) % primes_[prime_idx];
    				} while (idx != start);
    			}
    		}
    		cap_ = primes_[prime_idx];
    		delete[] table_;
    		table_ = tmp;
    	}
    
    private:
    	Node* table_;
    	int cap_;                      // 哈希表的容量
    	int size_;                     // 已经使用的空间
    	double load_factor_;           // 装载因子
    	
    	static const int PRIMES_SIZE = 10;
    	static const int primes_[PRIMES_SIZE];
    	int prime_idx;                 // 当前哈希表使用的素数
    };
    
    const int HashTable::primes_[PRIMES_SIZE] = { 3,7,23,47,251,443,911,1471,42773 };
    
    int main() {
    	HashTable h_table;
    	h_table.insert(21);
    	h_table.insert(32);
    	h_table.insert(14);
    	h_table.insert(15);
    	h_table.insert(22);
    	cout << h_table.find(21) << endl;
    	h_table.erase(21);
    	cout << h_table.find(21) << endl;
    	
    	return 0;
    }
    

    缺点:

    1. 发生冲突时,线性探测的过程会逐渐逼近O(n),存储会比较慢
    2. C++ STL中的所有容器都不是线性安全的,需要额外进行同步互斥操作,并且锁的粒度很大,需要锁住整个数组。

    三、链式哈希表

    若使用线性探测哈希表,要锁住整个数组。使用链式哈希表,则可以只使用分段的锁(锁住一个桶即可),既保证了线程安全,又有一定的并发量,提高了效率

    优化空间:

    1. 当数组里每个链表过长时,可以把链表转成红黑树O(n)
    2. 链式哈希表都可以创建自己的锁(分段锁),不同的桶中的操作是可以并发的

    在这里插入图片描述

    class HashTable {
    public:
    	// size用于初始化vector的大小
    	HashTable(int size = primes_[0], double load_factor=0.75)
    		: load_factor_(load_factor)
    		, prime_idx(0)
    		, use_num(0)
    	{
    		if (size != primes_[0]) {
    			for (; prime_idx < PRIMES_SIZE; prime_idx++) {
    				if (primes_[prime_idx] >= size) {
    					break;
    				}
    			}
    			if (prime_idx == PRIMES_SIZE) {
    				prime_idx--;
    			}
    		}
    		// 开辟空间,并且创建元素:table_.size() == primes_[prime_idx] && table_.capacity == primes_[prime_idx]
    		table_.resize(primes_[prime_idx]);  
    	}
    
    	// 实现为不可重复插入
    	bool insert(int val) {
    		bool inserted = false;
    		double factor = use_num * 1.0 / table_.size();
    		cout << "当前装载因子:" << factor << endl;
    		if (factor >= load_factor_) {
    			cout <<" 需要扩容" << endl;
    			expand();
    			cout << "扩容完成,当前容量:"<<table_.size() << endl;
    		}
    		int idx = val % table_.size();
    		if (table_[idx].empty()) {
    			use_num++;
    			table_[idx].emplace_front(val);     // 链表头插
    			inserted = true;
    		}
    		else {
    			auto iter = ::find(table_[idx].begin(), table_[idx].end(), val);
    			if (iter == table_[idx].end()) {
    				// 当前插入的值不存在,则插入链表
    				table_[idx].emplace_front(val); // 链表头插
    				inserted = true;
    			}
    		}
    		return inserted;
    	}
    
    	// 删除元素
    	bool erase(int val) {
    		int idx = val % table_.size();
    		// 如果链表节点过长,说明散列函数有问题,如果散列结果很离散,链表不会很长
    		auto iter = ::find(table_[idx].begin(), table_[idx].end(), val);
    		if (iter != table_[idx].end()) {
    			table_[idx].erase(iter);
    			if (table_[idx].empty()) {
    				use_num--;        // 删完后当前链表为空,则调整vector已经使用的个数
    			}
    			return true;
    		}
    		return false;
    	}
    
    	bool find(int val) {
    		int idx = val % table_.size();
    		auto iter = ::find(table_[idx].begin(), table_[idx].end(), val);
    		return iter != table_[idx].end();
    	}
    
    private:
    	void expand() {
    		if (prime_idx + 1 == PRIMES_SIZE) {
    			throw "hash table can't expand anymore!";
    		}
    		vector<list<int>> tmp;     // 资源交换过来后,局部变量出作用域自动析构
    		table_.swap(tmp);          // 若使用相同的容器适配器,只是交换成员变量
    		table_.resize(primes_[++prime_idx]);
    
    		// 遍历旧表中的元素,然后重新哈希
    		for (list<int> l : tmp) {
    			for (int val : l) {
    				int idx = val % table_.size();
    				if (table_[idx].empty()) {
    					use_num++;
    				}
    				table_[idx].emplace_front(val); // 链表头插
    			}
    		}
    	}
    
    private:
    	vector<list<int>> table_;
    	double load_factor_;           // 装载因子
    	int use_num;
    
    	static const int PRIMES_SIZE = 10;
    	static const int primes_[PRIMES_SIZE];
    	int prime_idx;                 // 当前哈希表使用的素数
    };
    
    const int HashTable::primes_[PRIMES_SIZE] = { 3,7,23,47,251,443,911,1471,42773 };
    

    四、哈希表相关面试题

    1. 有两个文件,分别存放了一些ip地址,找出同时在两个文件中都出现的ip地址

    把一个文件的ip放在一个哈希表,然后遍历另一个文件的同时在哈希表中查找,找到则输出

    1. 有两个文件,分别存放了1亿个数,每条数字4B,限制内存100MB,找出同时在两个文件中都出现的数

    1亿 约等于 100M
    100M * 4B = 400MB数据 ==> 放入链式哈希表后,还需要增加400MB的地址域,一共800MB

    在这里插入图片描述
    将两个大文件分成足够多的小文件,使得哈希过后将数字存入每个小文件的数据不至于超过100MB,这样相同的数必然会被哈希到下标相同的小文件中。

    把某个a小文件全部读入内存中的哈希表,然后从下标相同的b文件中挨个读取数据,然后在哈希表中查找,找到则在两个文件中重复出现

    五、位图大数据查重

    在这里插入图片描述

    现在有1亿个数据,最大值为1亿,每个数字4B,限制内存100MB

    若使用哈希表,需要使用100M * 4B * 2 = 800MB

    使用位图,则只需要使用100000000bit,(100000000/8+1)B = 12500000 = 12.5MB

    位操作: | 是赋值的,&是求值的

    template<typename T>
    void show_repeat(const vector<int>& vec, T bit_map_type = char()) {
    	int max_val = *max_element(vec.begin(), vec.end());
    	char* bitmap = new char[max_val / (sizeof(char) * 8) + 1]();
    	unique_ptr<char> ptr(bitmap);
    
    	for (int v : vec) {
    		int index = v / (sizeof(T) * 8);
    		int offset = v % (sizeof(T) * 8);
    		// &用于取出某个bit,|用于对某个bit赋值
    		if ((bitmap[index] & (1 << offset)) == 0) {
    			bitmap[index] |= (1 << offset);
    		}
    		else {
    			cout << v << "重复" << endl;
    		}
    	}
    }
    
    int main() {
    	vector<int> vec = {42,3,45,423,15,1,23,1,3412,45,12,45,2,65,412,5,4};
    	show_repeat(vec, int());
    	return 0;
    }
    

    位图适用场景: 数据数量和数据的最大值相当的时候适用,不适用于数据很少,但是最大值很大的情况,因为要按照最大值开辟内存空间

    六、布隆过滤器Bloom Filter

    在这里插入图片描述

    增加元素: 把key用k个哈希函数计算后,得到一组下标,将Bloom Filter中对应的bit置为1

    搜索元素: 把key用k个哈希函数计算后,得到一组下标,若Bloom Filter中对应的bit全为1,那这个key有可能存在,若对应的bit不全为1,则key肯定不在。Bloom Filter存在一定的误判率,但随着其长度和哈希函数的增加,误判率会大大降低

    删除元素: Bloom Filter不提供删除操作,若key1和key2有公用的bit,删除key1对应的bit后,那也改变了key2对应的bit,再查找key2的时候,也就查不到key2了

    一些应用场景
    在这里插入图片描述
    在这里插入图片描述
    优点: 结合了哈希表的效率高位图的省内存的优点,但是会存在一定的误判率,但随着其长度和哈希函数的增加,误判率会大大降低

    #include<iostream>
    #include<vector>
    #include<string>
    #include"stringhash.h"
    
    using namespace std;
    
    class BloomFilter {
    public:
    	BloomFilter(int bit_cap = 1471)
    		: bit_cap_(bit_cap)
    		, type_size_(sizeof(char))
    	{
    		bit_map_.resize(bit_cap_ / (type_size_ * 8) + 1);
    	}
    	
    	// 往Bloom Filter中插入key
    	void set_bit(const char* key) {
    		int idx1 = BKDRHash(key) % bit_cap_;
    		int idx2 = RSHash(key) % bit_cap_;
    		int idx3 = APHash(key) % bit_cap_;
    
    		int index = 0;
    		int offset = 0;
    		
    		index = idx1 / (type_size_ * 8);
    		offset = idx1 % (type_size_ * 8);
    		bit_map_[index] |= (1 << offset);
    
    		index = idx2 / (type_size_ * 8);
    		offset = idx2 % (type_size_ * 8);
    		bit_map_[index] |= (1 << offset);
    
    		index = idx3 / (type_size_ * 8);
    		offset = idx3 % (type_size_ * 8);
    		bit_map_[index] |= (1 << offset);
    	}
    
    	// 查询key是否存在于Bloom Filter
    	bool get_bit(const char* key) {
    		int idx1 = BKDRHash(key) % bit_cap_;
    		int idx2 = RSHash(key) % bit_cap_;
    		int idx3 = APHash(key) % bit_cap_;
    
    		int index = 0;
    		int offset = 0;
    
    		index = idx1 / (type_size_ * 8);
    		offset = idx1 % (type_size_ * 8);
    		if ((bit_map_[index] & (1 << offset)) == 0) {
    			return false;
    		}
    
    		index = idx2 / (type_size_ * 8);
    		offset = idx2 % (type_size_ * 8);
    		if ((bit_map_[index] & (1 << offset)) == 0) {
    			return false;
    		}
    
    		index = idx3 / (type_size_ * 8);
    		offset = idx3 % (type_size_ * 8);
    		if ((bit_map_[index] & (1 << offset)) == 0) {
    			return false;
    		}
    
    		return true;
    	}
    	
    private:
    	int bit_cap_;
    	int type_size_;
    	vector<char> bit_map_; 
    };
    
    class BlackList {
    public:
    	void add(string url) {
    		bloom_filter_.set_bit(url.c_str());
    	}
    
    	bool query(string url) {
    		return bloom_filter_.get_bit(url.c_str());
    	}
    private:
    	BloomFilter bloom_filter_;
    };
    
    int main() {
    	BlackList b_list;
    	b_list.add("www.baidu.com");
    	b_list.add("www.alibaba.com");
    	b_list.add("www.tencent.com");
    	cout << b_list.query("www.baidu.com") << endl;
    	cout << b_list.query("www.alibaba.com") << endl;
    	cout << b_list.query("www.tencent.com") << endl;
    	cout << b_list.query("www.bytedance.com") << endl;
    	return 0;
    }
    

    七、topK问题

    (1)堆排序求topk

    求最小的K个元素,用大根堆:堆中加入小的,淘汰大的
    在这里插入图片描述

    求最大的K个元素,用小根堆:堆中加入大的,淘汰小的在这里插入图片描述
    时间复杂度: O(logK)*O(n) = O(n)

    手写堆,实现求最大的k个数

    求出最大的K个元素,使用小根堆
    把数组前K个元素建立一个小根堆,从前K个元素第一个内部节点(K-1)/2开始建堆

    建堆完成后,开始遍历数组的其他元素

    1. 若当前元素大于堆顶元素,则淘汰堆顶元素,将当前元素放在堆顶,然后对堆顶元素调堆

    2. 若当前元素小于堆顶元素,则直接遍历下一个元素

    // 在[0,size-1]的范围内调堆,使下标为cur的元素满足堆性质
    void sift_down(int arr[], int cur, int size) {
    	int val = arr[cur];
    	int n = size - 1;
    	while (cur <= (size - 2) / 2) {
    		int min_child = 2 * cur + 1;   // 若满足while循环条件,则必然存在左孩子
    		if (2 * cur + 2 <= n) {
    			min_child = arr[min_child] < arr[2 * cur + 2] ? min_child : 2 * cur + 2;
    		}
    		if (arr[min_child] < val) {
    			arr[cur] = arr[min_child];
    			cur = min_child;
    		}
    		else {
    			break;
    		}
    	}
    	arr[cur] = val;
    }
    
    int main() {
    	int arr[10] = { 11,54,62,45,27,98,7,625,37,59 };
    	int k = 5;
    	for (int i = (k - 1 - 1) / 2; i >= 0; i--) {
    		sift_down(arr, i, k);
    	}
    
    	int n = sizeof(arr) / sizeof(arr[0]);
    	for (int i = k; i < n; i++) {
    		if (arr[i] > arr[0]) {
    			arr[0] = arr[i];
    			sift_down(arr, 0, k);
    		}
    		else {
    			continue;
    		}
    	}
    	for (int i = 0; i < k; i++) {
    		cout << arr[i] << " ";
    	}
    	return 0;
    }
    

    使用内置的优先级队列和哈希表实现统计出现次数最少的k个数字

    int main() {
    	int k = 5;
    	vector<int> vec;
    	srand(time(nullptr));
    	for (int i = 0; i < 1000; i++) {
    		vec.push_back(rand() % 100);
    	}
    
    	// 统计元素出现的个数
    	unordered_map<int, int> mp;
    	for (int key : vec) {
    		mp[key]++;
    	}
    
    	using Type = pair<int, int>;
    	using Comp = function<bool(Type&, Type&)>;
    	priority_queue<Type, vector<Type>, Comp> max_heap(
    		[](Type& a, Type& b)->bool {
    			return a.second < b.second;  // 大根堆
    		}
    	);
    
    	auto iter = mp.begin();
    	for (int i = 0; i < k; i++, iter++) {
    		max_heap.push(*iter);
    	}
    	for (; iter != mp.end(); iter++) {
    		if (iter->second < max_heap.top().second) {
    			max_heap.pop();
    			max_heap.push(*iter);
    		}
    	}
    
    	while (!max_heap.empty()) {
    		cout <<"value:"<< max_heap.top().first << " times:" << max_heap.top().second << endl;
    		max_heap.pop();
    	}
    	return 0;
    }
    

    (2)快排分割求topk

    int partition(int arr[], int begin, int end, int k) {
    	int l = begin;
    	int r = end;
    	int val = arr[l];
    	
    	while (l < r) {
    		while (l < r && arr[r] > val) {
    			r--;
    		}
    		if (l < r) {
    			arr[l] = arr[r];
    			l++;
    		}
    
    		while (l < r && arr[l] < val) {
    			l++;
    		}
    		if (l < r) {
    			arr[r] = arr[l];
    			r--;
    		}
    		
    	}
    	arr[l] = val;
    	return l;
    }
    
    // 递归函数作用:能把[begin, end]区间内,前topk的元素放在[0, k]
    void select_topk(int arr[], int begin, int end, int k) {
    	int pos = partition(arr, begin, end, k);
    	if (pos == k - 1) {
    		return;
    	}
    	else if (pos < k - 1) {
    		select_topk(arr, pos + 1, end, k);
    	}
    	else {
    		select_topk(arr, begin, pos - 1, k);
    	}
    }
    

    最好时间复杂度: 每次基准数都在中间,二叉树很平衡,n+n/2+…+1 = O(n)
    最坏时间复杂度: 数据本就有序,基准数每次都在最边上,二叉树退化为链表,O(n^2)

    八、一致性哈希算法

    (1)负载场景

    在这里插入图片描述
    经过哈希算法hash(ip:port)%N,同一客户的请求都会被映射到相同的服务器上,这有效解决了会话共享 的问题,这时候就不需要加入redis缓存服务器去记录客户的登录状态,避免引用外部模块过多导致系统不稳定的问题。

    但这种方法也有问题,比如当某个服务器宕机了(或增加服务器),这时候N的值就发生改变,导致相同客户的请求就不一定还会转发到以前那台服务器上,这会发生身份认证的问题。

    我们想要的是 同一 ip:port 的请求,永远被映射到同一台server上处理

    (2)缓存场景

    客户通常发请求查询信息的时候,是现在缓存服务器上查找,查找不到再到DB查找,然后把数据从DB转移到缓存服务器。
    在这里插入图片描述

    1. 若此时有一台服务器宕机了,同理在0号缓存服务器中的信息再次被查询时,这个请求很有可能会被转发到1号服务器,此时无法在1号缓存服务器中找到信息,就会去DB中查找,此时大量的磁盘IO会严重影响server的响应速度。更严重来讲,一台服务器的负载太高,可能会影响整个系统的运转,甚至崩溃

    2. 若此时增加了一台服务器,N发生改变。举个极端的例子,此时所有的请求都被转发到新的服务器中,新的服务器无法查询到相应信息,同理会产生大量的磁盘IO,甚至服务器崩溃

    我们的理想情况是:

    1. 某个server挂了,不影响其他server的正常运转,不会请求急剧增加
    2. server增加了,不影响原来server的请求,只会把后续的请求映射到新的server上

    (3)解决方法:一致性哈希算法

    为解决普通哈希算法导致的以上问题,提出一致性哈希算法(分布式系统负载均衡的首选算法

    一个良好的分布式哈希方案应该具有良好的单调性,即服务节点数量的改变不会造成大量哈希的重新定位

    算法过程
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    容错性分析

    1. 假设server A 宕机了,那原来在server C的请求2、3依然在server C,原来在server B的请求4依然在server B,只是原来在server A的请求会被转发到server C
    2. 假设多了一台server D放在如下位置,这只会影响新增server D与逆时针碰到的第一个server C之间的请求4,不会影响到其他的请求,这将影响降到了最低

    在这里插入图片描述

    为了达到良好的负载均衡,经过一致性哈希算法后的 server最好在哈希环上分散开,所以一般我们要在哈希环上加入物理节点的虚拟节点。加入物理节点的虚拟节点可防止由于物理节点过少,导致哈希处理后几台服务器挤在一起,从而导致某一台主机的负载过多,而其他空闲的情况
    在这里插入图片描述
    类设计如下:
    在这里插入图片描述

    #include<iostream>
    #include<set>
    #include<list>
    #include<map>
    #include<string>
    #include"md5.h"
    
    using namespace std;
    using uint = unsigned int;
    
    class PhysicalHost;
    
    class VirtualHost {
    public:
    	VirtualHost(string ip, PhysicalHost* phy_host_ptr) 
    	: ip_(ip)
    	, phy_host_ptr_(phy_host_ptr)
    	{
    		md5_ = getMD5(ip_.c_str());
    	}
    
    	// 虚拟节点存放到set的时候,需要排序,默认less,需要提供operator<
    	bool operator<(const VirtualHost& vir_host) const {
    		// 根据md5值排序
    		return md5_ < vir_host.md5_;
    	}
    
    	// 删除哈希环上的虚拟节点时,需要查找,重载operator==
    	bool operator==(const VirtualHost& vir_host) const {
    		return ip_ == vir_host.ip_;
    	}
    
    	const uint get_md5() const {
    		return md5_;
    	}
    
    	const PhysicalHost* get_phy_host() const {
    		return phy_host_ptr_;
    	}
    private:
    	string ip_;                   // 虚拟节点记录的ip信息
    	uint md5_;                    // 根据物理节点的ip计算的ip值得到的MD5,这是32位加密串运算得到的uint
    	PhysicalHost* phy_host_ptr_;  // 指向实际的物理节点
    };
    
    class PhysicalHost {
    public:
    	// 物理节点的ip,创建虚拟节点的个数
    	PhysicalHost(string ip, int v_number)
    	: ip_(ip)
    	{
    		for (int i = 0; i < v_number; i++) {
    			// 虚拟节点需要记录ip以及对应的物理节点
    			virtual_hosts_.push_back(VirtualHost(ip_ + "#" + ::to_string(i), this));
    		}
    	}
    
    	const string get_ip() const{
    		return ip_;
    	}
    
    	const list<VirtualHost>& get_virtual_hosts() const {
    		return virtual_hosts_;
    	}
    
    private:
    	string ip_;
    	list<VirtualHost> virtual_hosts_;  // 双向循环链表
    };
    
    class ConsistentHash {
    public:
    	// 添加物理主机的虚拟节点到一致性哈希环
    	void add_host(PhysicalHost& phy_host) {
    		auto vir_list = phy_host.get_virtual_hosts();
    		for (auto vir_host : vir_list) {
    			hash_circle_.insert(vir_host);
    		}
    	}
    
    	// 删除哈希环物理节点所有的虚拟节点
    	void del_host(PhysicalHost& phy_host) {
    		auto vir_list = phy_host.get_virtual_hosts();
    		for (auto vir_host : vir_list) {
    			// 红黑树查找,O(log2n)
    			auto iter = hash_circle_.find(vir_host);
    			if (iter != hash_circle_.end()) {
    				hash_circle_.erase(iter);
    			}
    		}
    	}
    
    	// 根据客户的ip,计算其对应的虚拟主机,然后根据虚拟主机返回真是的物理主机的ip
    	string get_client_host(string client_ip) const{
    		uint client_md5 = getMD5(client_ip.c_str());
    		// 找第一个比客户ip的md5大的虚拟主机
    		for (VirtualHost vir_host : hash_circle_) {
    			if (vir_host.get_md5() > client_md5) {
    				return vir_host.get_phy_host()->get_ip();
    			}
    		}
    		// 客户的ip得到的md5过大,无法找到更大的md5,那直接分配第一个虚拟节点
    		return hash_circle_.begin()->get_phy_host()->get_ip();
    	}
    
    private:
        // 由于需要顺时针查找,需要排序,所以一致性哈希算法底层用到红黑树
    	set<VirtualHost> hash_circle_;
    };
    
    void show_consistent_hash(const ConsistentHash& hash_circle) {
    	list<string> client_ip_list{
    		"192.168.1.100",
    		"192.168.1.101",
    		"192.168.1.102",
    		"192.168.1.103",
    		"192.168.1.104",
    		"192.168.1.105",
    		"192.168.1.106",
    		"192.168.1.107",
    		"192.168.1.108",
    		"192.168.1.109",
    		"192.168.1.110",
    		"192.168.1.111",
    		"192.168.1.112",
    		"192.168.1.113",
    	};
    
    	// 物理服务器ip  所服务的客户端ip
    	map<string, list<string>> ip_map;
    	for (string client_ip : client_ip_list) {
    		// 根据客户端的ip,计算哈希环上的虚拟主机,从而拿到对应物理主机的ip
    		string phy_host_ip = hash_circle.get_client_host(client_ip);  
    		ip_map[phy_host_ip].push_back(client_ip);
    	}
    	for (auto pair : ip_map) {
    		cout << "server ip :" << pair.first << endl;
    		cout << "该服务器服务的客户端有" << pair.second.size() << "个" << endl;
    		cout << "client ip :" << endl;
    		for (string client_ip : pair.second) {
    			cout << client_ip << endl;
    		}
    		cout << "-----------------------------" << endl;
    	}
    }
    
    int main() {
    	PhysicalHost phy_host1("10.117.121.66", 200);
    	PhysicalHost phy_host2("10.117.121.67", 200);
    	PhysicalHost phy_host3("10.117.121.68", 200);
    	
    	ConsistentHash hash_circle;
    	hash_circle.add_host(phy_host1);
    	hash_circle.add_host(phy_host2);
    	hash_circle.add_host(phy_host3);
    	
    	show_consistent_hash(hash_circle);
    	hash_circle.del_host(phy_host2);
    	cout << "*********主机2宕机*********" << endl;
    	show_consistent_hash(hash_circle);
    
    	return 0;
    }
    
    server ip :10.117.121.66
    该服务器服务的客户端有3个
    client ip :
    192.168.1.105
    192.168.1.109
    192.168.1.112
    -----------------------------
    server ip :10.117.121.67
    该服务器服务的客户端有5个
    client ip :
    192.168.1.100
    192.168.1.102
    192.168.1.103
    192.168.1.107
    192.168.1.110
    -----------------------------
    server ip :10.117.121.68
    该服务器服务的客户端有6个
    client ip :
    192.168.1.101
    192.168.1.104
    192.168.1.106
    192.168.1.108
    192.168.1.111
    192.168.1.113
    -----------------------------
    *********主机2宕机*********
    server ip :10.117.121.66
    该服务器服务的客户端有4个
    client ip :
    192.168.1.105
    192.168.1.109
    192.168.1.110
    192.168.1.112
    -----------------------------
    server ip :10.117.121.68
    该服务器服务的客户端有10个
    client ip :
    192.168.1.100
    192.168.1.101
    192.168.1.102
    192.168.1.103
    192.168.1.104
    192.168.1.106
    192.168.1.107
    192.168.1.108
    192.168.1.111
    192.168.1.113
    -----------------------------
    

    该代码需要md5源码才可运行,需要可以私信

    展开全文
  • 什么是哈希 数据结构中我们学习过哈希表也称为散列表,我们来回顾下散列表的定义。 散列表,是根据键直接访问在指定储存位置数据的数据结构。通过计算一个关于键的...常见的哈希算法 MD5算法 MD5消息摘要算法(MD5 M

    什么是哈希

    数据结构中我们学习过哈希表也称为散列表,我们来回顾下散列表的定义。

    散列表,是根据键直接访问在指定储存位置数据的数据结构。通过计算一个关于键的函数也称为哈希函数,将所需查询的数据映射到表中一个位置来访问记录,加快查找速度。这个映射函数称做「散列函数」,存放记录的数组称做散列表。

    散列函数能使对一个数据序列的访问过程更加迅速有效,是一种空间换时间的算法,通过散列函数数据元素将被更快定位。

    下图示意了字符串经过哈希函数映射到哈希表的过程。
    在这里插入图片描述

    常见的哈希算法

    MD5算法

    MD5消息摘要算法(MD5 Message-Digest Algorithm),一种被广泛使用的密码散列函数,可以产生出一个128位(16字节)的散列值(hash value),MD5算法将数据(如一段文字)运算变为另一固定长度值,是散列算法的基础原理。由美国密码学家 Ronald Linn Rivest设计,于1992年公开并在 RFC 1321 中被加以规范。

    CRC算法

    循环冗余校验(Cyclic Redundancy Check)是一种根据网络数据包或电脑文件等数据,产生简短固定位数校验码的一种散列函数,由 W. Wesley Peterson 于1961年发表。生成的数字在传输或者存储之前计算出来并且附加到数据后面,然后接收方进行检验确定数据是否发生变化。由于本函数易于用二进制的电脑硬件使用、容易进行数学分析并且尤其善于检测传输通道干扰引起的错误,因此获得广泛应用。

    MurmurHash

    MurmurHash 是一种非加密型哈希函数,适用于一般的哈希检索操作。由 Austin Appleby 在2008年发明,并出现了多个变种,与其它流行的哈希函数相比,对于规律性较强的键,MurmurHash的随机分布特征表现更良好。

    这个算法已经被很多开源项目使用,比如libstdc++ (4.6版)、Perl、nginx (不早于1.0.1版)、Rubinius、 libmemcached、maatkit、Hadoop等。

    常见散列方法

    直接定址法

    取关键字或关键字的某个线性函数值为散列地址,这个线性函数的定义多种多样,没有标准。

    数字分析法

    假设关键字是以r为基的数,并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址。

    平方取中法

    取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况,取其中的哪几位也不一定合适,而一个数平方后的中间几位数和数的每一位都相关,由此使随机分布的关键字得到的哈希地址也是随机的,取的位数由表长决定。

    折叠法

    将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。

    取模法

    取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址。即 hash(key) = key % p(p<= M),不仅可以对关键字直接取模,也可在折叠法、平方取中法等运算之后取模。对 p 的选择很重要,一般取素数或 m,若 p 选择不好,容易产生冲突。

    缓存系统负载均衡

    在分布式集群缓存的负载均衡实现中,比如 memcached 缓存集群,需要把缓存数据的 key 利用哈希函数散列,这样缓存数据能够均匀分布到各个分布式存储节点上,要实现这样的负载均衡一般可以用哈希算法来实现。下图演示了这一分布式存储过程:
    在这里插入图片描述

    普通哈希算法负载均衡

    前面我们介绍过各种散列方法,不管是选择上述哪种散列方法,在这个应用场景下,都是要把缓存数据利用哈希函数均匀的映射到服务器集群上,我们就选择简单的「取模法」来说明这个过程。

    假设有 3 个服务器节点编号 [0 - 2],6 个缓存键值对编号 [1 - 6],则完成哈希映射之后,三个缓存数据映射情况如下:

    哈希计算公式:key % 节点总数 = Hash节点下标
    1 % 3 = 1
    2 % 3 = 2
    3 % 3 = 0
    4 % 3 = 1
    5 % 3 = 2
    6 % 3 = 0
    

    在这里插入图片描述
    每个连接都均匀的分散到了三个不同的服务器节点上,看起来很完美!

    但是,在分布式集群系统的负载均衡实现上,这种模型有两个问题:

    扩展能力差

    为了动态调节服务能力,服务节点经常需要扩容缩容。打个比方,如果是电商服务,双十一期间的服务机器数量肯定要比平常大很多,新加进来的机器会使原来计算的哈希值不准确,为了达到负载均衡的效果,要重新计算并更新哈希值,对于更新后哈希值不一致的缓存数据,要迁移到更新后的节点上去。

    假设新增了 1 个服务器节点,由原来的 3 个服务节点变成 4 个节点编号 [0 - 3],哈希映射情况如下:

    哈希计算公式:key % 节点总数 = Hash节点下标
    1 % 4 = 1
    2 % 4 = 2
    3 % 4 = 3
    4 % 4 = 0
    5 % 4 = 1
    6 % 4 = 2
    

    可以看到后面三个缓存 key :4、5、6 对应的存储节点全部失效了,这就需要把这几个节点的缓存数据迁移到更新后的节点上 (费时费力) ,也就是由原来的节点 [1, 2, 0] 迁移到节点 [0, 1, 2],迁移后存储示意图如下:
    在这里插入图片描述

    容错能力不佳

    线上环境服务节点虽然有各种高可用性保证,但还是是有宕机的可能,即使没有宕机也有缩容的需求。不管是宕机和缩容都可以归结为服务节点删除的情况,下面分析下服务节点删除对负载均衡哈希值的影响。

    假设删除 1 个服务器节点,由最初的 3 个服务节点变成 2 个,节点编号 [0 - 1],哈希映射情况如下:

    哈希计算公式:key % 节点总数 = Hash节点下标
    1 % 2 = 1
    2 % 2 = 0
    3 % 2 = 1
    4 % 2 = 0
    5 % 2 = 1
    6 % 2 = 0
    

    下图展示普通哈希负载均衡算法在一个节点宕机时候,导致的的缓存数据迁移分布情况:

    在这里插入图片描述
    如图所见,在这个例子中,仅仅删除了一个服务节点,也导致了哈希值的大面积更新,哈希值的更新也是意味着节点缓存数据的迁移(缓存数据表示心好累)

    一致性哈希算法负载均衡

    正是由于普通哈希算法实现的缓存负载均衡存在扩展能力和容错能力差问题,所以我们引入一致性哈希算法,那么什么是一致性哈希呢?先来看下wiki上对一致性Hash的定义

    一致哈希由 MIT 的 David Karger 及其合作者提出,现在这一思想已经扩展到其它领域。在这篇1997年发表的学术论文中介绍了一致哈希如何应用于用户易变的分布式Web服务中。一致哈希也可用于实现健壮缓存来减少大型Web应用中系统部分失效带来的负面影响。
    
    下载地址:http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.147.1879
    

    一句话概括一致性哈希:就是普通取模哈希算法的改良版,哈希函数计算方法不变,只不过是通过构建环状的 Hash 空间代替普通的线性 Hash 空间。具体做法如下:

    首先,选择一个足够大的Hash空间(一般是 0 ~ 2^32)构成一个哈希环。

    在这里插入图片描述
    然后,对于缓存集群内的每个存储服务器节点计算 Hash 值,可以用服务器的 IP 或 主机名计算得到哈希值,计算得到的哈希值就是服务节点在 Hash 环上的位置。

    在这里插入图片描述
    最后,对每个需要存储的数据 key 同样也计算一次哈希值,计算之后的哈希也映射到环上,数据存储的位置是沿顺时针的方向找到的环上的第一个节点。下图举例展示了节点存储的数据情况,我们下面的说明也是基于目前的存储情况来展开。

    在这里插入图片描述

    原理讲完了,来看看为什么这样的设计能解决上面普通哈希的两个问题。

    扩展能力提升

    前面我们分析过,普通哈希算法当需要扩容增加服务节点的时候,会导致原油哈希映射大面积失效。现在,我们来看下一致性哈希是如何解决这个问题的。

    如下图所示,当缓存服务集群要新增一个节点node3时,受影响的只有 key3 对应的数据 value3,此时只需把 value3 由原来的节点 node0 迁移到新增节点 node3 即可,其余节点存储的数据保持不动。

    在这里插入图片描述

    容错能力提升

    普通哈希算法当某一服务节点宕机下线,也会导致原来哈希映射的大面积失效,失效的映射触发数据迁移影响缓存服务性能,容错能力不足。一起来看下一致性哈希是如何提升容错能力的。

    如下图所示,假设 node2 节点宕机下线,则原来存储于 node2 的数据 value2 和 value5 ,只需按顺时针方向选择新的存储节点 node0 存放即可,不会对其他节点数据产生影响。一致性哈希能把节点宕机造成的影响控制在顺时针相邻节点之间,避免对整个集群造成影响。

    在这里插入图片描述

    一致性哈希优化

    存在的问题

    上面展示了一致性哈希如何解决普通哈希的扩展和容错问题,原理比较简单,在理想情况下可以良好运行,但在实际使用中还有一些实际问题需要考虑,下面具体分析。

    数据倾斜

    试想一下若缓存集群内的服务节点比较少,就像我们例子中的三个节点,而哈希环的空间又有很大(一般是 0 ~ 2^32),这会导致什么问题呢?

    可能的一种情况是,较少的服务节点哈希值聚集在一起,比如下图所示这种情况 node0 、node1、node2 聚集在一起,缓存数据的 key 哈希都映射到 node2 的顺时针方向,数据按顺时针寻找存储节点就导致全都存储到 node0 上去,给单个节点很大的压力!这种情况称为数据倾斜。
    在这里插入图片描述

    节点雪崩

    数据倾斜和节点宕机都可能会导致缓存雪崩。

    拿前面数据倾斜的示例来说,数据倾斜导致所有缓存数据都打到 node0 上面,有可能会导致 node0 不堪重负被压垮了,node0 宕机,数据又都打到 node1 上面把 node1 也打垮了,node1 也被打趴传递给 node2,这时候故障就像像雪崩时滚雪球一样越滚越大。

    还有一种情况是节点由于各种原因宕机下线。比如下图所示的节点 node2 下线导致原本在node2 的数据压到 node0 , 在数据量特别大的情况下也可能导致节点雪崩,具体过程就像刚才的分析一样。

    总之,连锁反应导致的整个缓存集群不可用,就称为节点雪崩。
    在这里插入图片描述

    虚拟节点

    那该如何解决上述两个棘手的问题呢?可以通过「虚拟节点」的方式解决。

    所谓虚拟节点,就是对原来单一的物理节点在哈希环上虚拟出几个它的分身节点,这些分身节点称为「虚拟节点」。打到分身节点上的数据实际上也是映射到分身对应的物理节点上,这样一个物理节点可以通过虚拟节点的方式均匀分散在哈希环的各个部分,解决了数据倾斜问题。

    由于虚拟节点分散在哈希环各个部分,当某个节点宕机下线,他所存储的数据会被均匀分配给其他各个节点,避免对单一节点突发压力导致的节点雪崩问题。

    下图展示了虚拟节点的哈希环分布,其中左边是没做虚拟节点情况下的节点分布,右边背景色绿色两个的 node0 节点是 node0 节点的虚拟节点;背景色红色的 node1 节点是 node1 的虚拟节点。

    在这里插入图片描述

    总结一下

    本文首先介绍了什么是哈希算法和常见的哈希算法,以及常见散列方式,接着说明基于普通哈希算法的缓存负载均衡实现,并举例说明普通算法的扩展性和容错性方便存在的问题。

    为了解决普通算法的扩展性和容错性问题引入一致性哈希算法,图解和举例分析了一致性哈希是如何提高扩展性和容错性。最后粗糙的一致性哈希算法也存在数据倾斜和节点雪崩的问题,讲解了如何利用虚拟节点优化一致性哈希算法,解决数据倾斜和雪崩问题。至此,一致性哈希你学会了吗?

    一致性哈希这个知识点不难,但是经常会考察到,就像布隆过滤器算法一样,没听过的人觉得很高端,研究一下也就那么一回事,所以知识面要宽才能吊打面试官啊同学们!

    展开全文
  • 哈希算法

    2021-01-15 14:36:07
    哈希 1.什么是哈希? 2.哈希函数? 1.哈希函数的定义: ... 按照某种方式,将元素与其所在的表格中的存储位置建立一一映射的关系,那么就在查找时,通过改函数可以快速的找到。时间复杂度为O(1)。...
  • 联合索引的创建方法与单个索引创建的方法一样,不同之处仅在于有多个索引列。 创建了联合索引 index_a_b 那么何时需要使用联合索引呢?在讨论这个问题之前,先来看一下联合索引内部的结果。从本质上来说,联合索引也...
  • 哈希MurmurHash算法详解

    2021-09-24 08:30:06
    文章目录一、哈希函数定义特点应用常见哈希算法二、murmurhash定义特点应用介绍三、MurmurHash使用四、性能测试 MurmurHash:(multiply and rotate) and (multiply and rotate) Hash,乘法和旋转的hash 算法。 一、...
  • 1,对于待存储的海量数据,如何将它们分配到各个机器中去?---数据分片与路由当数据量很大时,通过改善单机硬件资源的纵向扩充方式来存储数据变得越来越不适用,而通过增加机器数目...2,衡量一致性哈希算法好处的四...
  • 一致性哈希算法详解

    2021-10-06 10:38:51
    散列表,是根据键直接访问在指定储存位置数据的数据结构。通过计算一个关于键的函数也称为哈希函数,将所需查询的数据映射到表中一个位置来访问记录,加快查找速度。这个映射函数称做「散列函数」,存放记录的数组...
  • 哈希算法如果我们用(用户id)%服务器机器数这样的方法来分配服务器。虽然我们能保证数据的均匀性,但稳定性差,比如我们增加一个节点,会导致大量的映射失效。1%3 == 1%42%3 == 2%43%3 != 3%44%3 != 4%4 这就难搞了,...
  • 一致性哈希算法

    2021-02-21 18:49:28
    哈希算法就是按键值对的存储,给定一个键,可以做到O(1)的时间复杂度内的数据查找。例如根据学生的学号查找学生的相关的信息。一种简单的存储形式就是以哈希表的形式来存储<code,studentinfo>。 假如某个学校...
  • 算法--前缀和+哈希

    2021-07-04 11:17:16
    今天学习一下前缀和和哈希算法思想。主要用于解决连续子数组问题。 前缀和: 给定一个数组a[0,..n-1] 定义Sn=a0+a1+...+an-1。则连续子数组和Suma[i, j] 可以表示为ai+...+aj=Sj-Si-1。即连续子数组和问题可以...
  • 哈希表与哈希查找

    2021-08-28 14:07:36
    在这种查找方式中,“比较”是必不可免的,那么是否有一种方法可以避免比较,即通过关键字的某种形式来存储该数据的地址,这样在查找时,将待查询的关键字通过一定计算就可以得到目的数据的地址。 文章目录哈希表...
  • 目 录布隆过滤器(BloomFilter)SimhashMinhashing局部敏感哈希(Local Sensitive Hashing)前言:接上文,本篇所讲的两种哈希算法:minhashing和局部敏感哈希(LSH)是一类哈希的思路,可以用来在海量数据中查找相似的...
  • 顺序查找也叫线性查找,是按照序列原有顺序对数组进行遍历比较查询的基本查找算法,顺序查找是最简单的搜索算法,其实现如下: def seq_search(li,val): for ind,v in enumerate(li): if v == val: return ind # ...
  • 顺序查找 二分查找 索引查找 哈希查找【数据结构与算法
  • 这里面计算映射方法叫做散列函数也叫做哈希(hash函数),存放记录的数组叫做散列表。是一种典型的空间换时间的策略。 这样当有一个数据来需要查询的时候,先通过散列函数计算出对应位置,在通过计算出位置的去查找...
  • 哈希函数(哈希表) 1.概念 2.用法注意点 四.运用哈希表来编写实现一个<学生信息管理系统> 笔记: 一.排序 1.插入排序: 先构建一个有序的序列,遍历无序的序列,将无序的序列中的每一个元素和有序序列中的...
  • 这里的对应关系f 称为散列函数,又称为哈希(Hash函数),采用散列技术将记录存储在一块连续的存储空间中,这块连续存储空间称为散列表或哈希表(Hash table)。 当使用哈希表进行查询的时候,就是再次使用哈希函数...
  • JAVA算法哈希查找

    2021-05-12 17:02:43
    首先在元素的关键字k和元素的存储位置p之间建立一个对应关系H,使得p=H(k),H称为哈希函数。 除留余数法: 假设哈希表长为m, p为小于等于m的最大素数, 则哈希函数为 H(k)=k%p,其中%为模p取余运算。 处理冲
  • 哈希哈希

    2021-10-31 23:54:34
    数据结构中有一类常用于搜索,给定一个元素集合,常见的可用于搜索的算法有 遍历,遍历是十分粗暴简单的手段,对于元素的集合没有特殊要求,时间复杂度是O(N)。效率通常较低。 二分查找,二分查找要求元素集合有序,...
  • 对此希望找到一种理想的搜索方法:可以不经过任何比较,一次直接从表中得到要搜索的元素。 如果构造一种存储结构,通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时...
  • 假设我们要破解的摘要值(哈希链表的 H(x) 不一定是 MD5 算法,这里用更准确的说法代替 MD5 码)是 7E9F216C,经过 R(x) 运算得到 rapper,说明我们要寻找的原文就在以 rapper 为末端的哈希链表中。从首端开始经过...
  • 查找算法06-哈希查找

    2021-07-31 09:57:19
    查找算法06-哈希查找6、哈希查找6-1实现代码6-2测试6-3方法解析 6、哈希查找 (1)概述 在哈希表中,若出现key1≠key2,而f(key1)=f(key2),则这种现象称为地址冲突key1和key2对哈希函数f来说是同义词。根据设定的哈希...
  • 几种常见的哈希函数(散列函数)构造方法 直接定址法 取关键字或关键字的某个线性函数值为散列地址。 即 H(key) = key 或 H(key) = a*key + b,其中a和b为常数。 比如 除留余数法 取关键字被某个不大于散...
  • 加密算法优缺点及适用场景整理

    千次阅读 2021-01-26 09:46:48
    加密算法优缺点及适用场景整理 对称加密算法(DES和AES) DES 算法:一种典型的块加密方法,将固定长度的明文通过一系列复杂的操作变成同样长度的密文,块的长度为64位。同时,DES 使用的密钥来自定义变换过程,因此...
  • 探查序列:冲突解决策略的闭哈希方法中,如果基位置冲突,需要根据探查函数查找下一个空槽,这个过程产生的序列加上基位置组成了某个关键码的探查序列 基本聚集:在探查函数的设计中,如果不同基位置关键码产生的...
  • 然后通过哈希算法(如取余法等)获得的值比方0,就是哈希值(位置信息),存储“0对应老铁双击666“这些关系的就是哈希表。 什么是哈希冲突? 图1 上面的30比方就是老铁双击666,但为什么后面还有值呢,因为其他值...
  • 哈希函数介绍

    2021-11-01 18:37:25
    通常,包含哈希函数的算法算法复杂度都假设为 O(1),这就是为什么在哈希表中搜索数据的时间复杂度会被认为是"平均为 O(1) 的复杂度". 基本概念 在讲解具体内容前,首先我们要清楚以下几个概念: 1. 冲突(碰撞)...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 45,064
精华内容 18,025
关键字:

哈希算法适用的存储方法