精华内容
下载资源
问答
  • 2022-01-21 14:41:42

    哈希查找算法

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

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

    哈希表是什么

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

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

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

    在这里插入图片描述

    图 1 数组

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

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

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

    举个例子,将 {20, 30, 50, 70, 80} 存储到哈希表中,我们设计的哈希函数为 y=x/10,最终各个元素的存储位置如下图所示:

    在这里插入图片描述

    图 2 哈希表存储结构

    在图 2 的基础上,假设我们想查找元素 50,只需将它带入 y=x/10 这个哈希函数中,计算出它对应的索引值为 5,直接可以在数组中找到它。借助哈希函数,我们提高了数组中数据的查找效率,这就是哈希表存储结构。

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

    在这里插入图片描述

    图 3 哈希表发生哈希冲突

    可以看到,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 线性探测法解决哈希冲突

    假设我们从图 4 所示的哈希表中查找元素 50,查找过程需要经过以下几步:
    根据哈希函数 y=x%10,目标元素的存储位置为 0,但经过和下标为 0 处的元素 20 比较,该位置存储的并非目标元素;

    根据线性探测法,比较下标位置为 1 处的元素 30,也不是目标元素;
    继续比较下标位置为 2 的元素 50,成功找到目标元素。

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

    哈希查找算法

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

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

    N <- 10 // 指定哈希表的长度 输入 arr[] //存储 {5, 20, 30, 50, 55}
    待查找序列 //哈希函数 hash(value):
    return value%10 //创建哈希表,arr为原序列,hashArr为空的哈希表 createHash(arr, hashArr):
    for i <- 0 to 5:
    index <- hash(arr[i])
    while (hashArr[index % N] !=0):
    index <- index + 1
    hashArr[index] <- arr[i] // 实现哈希查找算法,value 为要查找的目标元素 hash_serch(hashArr[] , value):
    hashAdd = hash(value) // 根据哈希函数,找到对应的索引值
    while hashArr[hashAdd] != value: // 如果哈希表中对应位置不是要查找的目标元(即发生了碰撞)
    hashAdd = (hashAdd + 1) % N // 获取下一个索引值
    if hashArr[hashAdd] == 0 || hashAdd = hash(value): // 如果索引值对应的存储位置为空(这里用 -1 表示),或者已经查找了一圈,仍为找到目标元素
    return -1 // 查找失败(返回 -1 表示查找失败)
    return hashAdd // 返回目标元素所在的索引

    结合伪代码,如下是使用哈希查找算法在 {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

    更多相关内容
  • 算法:哈希

    2022-03-25 20:54:48
    哈希表简介 哈希表:也叫做散列表。是根据关键字和值(Key-Value)直接进行访问的数据结构。也就是说,它通过关键字 key 和一个映射函数 Hash(key) 计算出对应的值 value,然后把键值对映射到表中一个位置来访问记录...

    哈希表简介

    哈希表:也叫做散列表。是根据关键字和值(Key-Value)直接进行访问的数据结构。也就是说,它通过关键字 key 和一个映射函数 Hash(key) 计算出对应的值 value,然后把键值对映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做哈希函数(散列函数)用于存放记录的数组叫做 哈希表(散列表)
    哈希表的关键思想是使用哈希函数,将键 key值 value 映射到对应表的某个区块中。可以将算法思想分为两个部分:

    • 向哈希表中插入一个关键字:哈希函数决定该关键字的对应值应该存放到表中的哪个区块,并将对应值存放到该区块中
    • 在哈希表中搜索一个关键字:使用相同的哈希函数从哈希表中查找对应的区块,并在特定的区块搜索该关键字对应的值

    哈希表的原理示例图如下所示:

    在这里插入图片描述

    • 插入关键字:哈希函数对关键字进行哈希,得到哈希值后插入到哈希表对应的地方
    • 搜索关键字:哈希函数对关键字进行哈希,基于哈希值去哈希表中进行查询

    哈希表的应用举例:

    哈希表在生活中的应用也很广泛,其中一个常见例子就是「查字典」。
    比如为了查找这个字的具体意思,我们在字典中根据这个字的拼音索引 zan,查找到对应的页码为 599。然后我们就可以翻到字典的第 599 页查看字相关的解释了。

    在这里插入图片描述

    查找索引这一过程可以看作是哈希函数操作


    哈希函数

    哈希函数:将哈希表中元素的关键键值映射为元素存储位置的函数。
    哈希函数是哈希表中最重要的部分。一般来说,哈希函数会满足以下几个条件:

    • 哈希函数应该易于计算,并且尽量使计算出来的索引值均匀分布,这能减少哈希冲突
    • 哈希函数计算得到的哈希值是一个固定长度的输出值
    • 如果 Hash(key1) 不等于 Hash(key2),那么 key1、key2 一定不相等
    • 如果 Hash(key1) 等于 Hash(key2),那么 key1、key2 可能相等,也可能不相等(会发生哈希碰撞)

    在哈希表的实际应用中,关键字的类型除了数字类型,还有可能是字符串类型、浮点数类型、大整数类型,甚至还有可能是几种类型的组合。一般会将各种类型的关键字先转换为整数类型,再通过哈希函数,将其映射到哈希表中
    而关于整数类型的关键字,通常用到的哈希函数方法有:直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等

    下面介绍几个常用的哈希函数方法。

    直接定址法

    直接定址法取关键字或者关键字的某个线性函数值为哈希地址。即: H a s h ( k e y ) = k e y Hash(key) = key Hash(key)=key 或者 H a s h ( k e y ) = a ∗ k e y + b Hash(key) = a * key + b Hash(key)=akey+b,其中 a 和 b 为常数。

    这种方法计算最简单,且不会产生冲突适合于关键字分布基本连续的情况如果关键字分布不连续,空位较多,则会造成存储空间的浪费

    举一个例子,假设有一个记录了从 1 岁到 100 岁的人口数字统计表。其中年龄为关键字,哈希函数取关键字自身,如下表所示。

    在这里插入图片描述

    比如想要查询 25 岁的人有多少,则只要查询表中第 25 项即可。

    除留余数法

    除留余数法:假设哈希表的表长为 m,取一个不大于 m 但接近或等于 m 的质数 p,利用取模运算,将关键字转换为哈希地址。即: H a s h ( k e y ) = k e y Hash(key) = key % p Hash(key)=key,其中 p 为不大于 m 的质数。

    这也是一种简单且常用的哈希函数方法。其关键点在于p 的选择。根据经验而言,一般 p 取素数或者 m,这样可以尽可能的减少冲突。

    比如我们需要将 7 个数 [432, 5, 128, 193, 92, 111, 88] 存储在 11 个区块中(长度为 11 的数组),通过除留余数法将这 7 个数应分别位于如下地址:

    在这里插入图片描述

    比如432,对11取余数,余数为3,放在03位置

    平方取中法

    平方取中法:先通过求关键字平方值的方式扩大相近数之间的差别,然后根据表长度取关键字平方值的中间几位数为哈希地址。

    比如: H a s h ( k e y ) = ( k e y ∗ k e y ) / / 100 % 1000 Hash(key) = (key * key) // 100 \% 1000 Hash(key)=(keykey)//100%1000,先计算平方,去除末尾的2位数,再取中间 3 位数作为哈希地址。
    这种方法因为关键字平方值的中间几位数和原关键字的每一位数都相关,所以产生的哈希地址也比较均匀,有利于减少冲突的发生。

    比如关键字为1443, 进行哈希计算:

    1443 ∗ 1443 = 2082249 1443 * 1443 = 2082249 14431443=2082249

    2082249 / 100 = 20822 2082249/100=20822 2082249/100=20822

    20822 % 1000 = 822 20822\%1000=822 20822%1000=822

    因此最终的哈希值结果就是822

    基数转换法

    基数转换法:将关键字看成另一种进制的数再转换成原来进制的数,然后选其中几位作为哈希地址。

    比如,将关键字看作是13进制的数,再将其转变为10进制的数,然后将其作为哈希地址。

    以343246为例,计算方式如下:

    ( 343246 ) 13 = 3 ∗ 1 3 5 + 4 ∗ 1 3 4 + 3 ∗ 1 3 3 + 2 ∗ 1 3 2 + 4 ∗ 1 3 1 + 6 ∗ 1 3 0 = ( 1235110 ) 10 (343246)_{13} = 3 * 13^5 + 4 * 13^4 + 3 * 13^3 + 2 * 13^2 + 4 * 13^1 + 6 * 13^0 = (1235110)_{10} (343246)13=3135+4134+3133+2132+4131+6130=(1235110)10


    哈希冲突

    哈希冲突不同的关键字通过同一个哈希函数可能得到同一哈希地址,即 key1 ≠ key2,而 Hash(key1) = Hash(key2),这种现象称为哈希冲突。

    理想状态下,我们的哈希函数是完美的一对一映射,即一个关键字(key)对应一个值(value),不需要处理冲突。但是一般情况下,不同的关键字 key 可能对应了同一个值 value,这就发生了哈希冲突。

    设计再好的哈希函数也无法完全避免哈希冲突。所以就需要通过一定的方法来解决哈希冲突问题。常用的哈希冲突解决方法主要是两类:「开放地址法」和「链地址法」

    开放地址法

    开放地址法:指的是将哈希表中的「空地址」向处理冲突开放。当哈希表未满时,处理冲突时需要尝试另外的单元,直到找到空的单元为止。

    当发生冲突时,开放地址法按照下面的方法求得后继哈希地址 H ( i ) = ( H a s h ( k e y ) + F ( i ) ) % m , i = 1 , 2 , 3 , . . . , n ( n ≤ m − 1 ) H(i) = (Hash(key) + F(i)) \% m,i = 1, 2, 3, ..., n (n ≤ m - 1) H(i)=(Hash(key)+F(i))%mi=1,2,3,...,n(nm1)

    • H(i) 是在处理冲突中得到的地址序列。即在第 1 次冲突(i = 1)时经过处理得到一个新地址 H(1),如果在 H(1) 处仍然发生冲突(i = 2)时经过处理时得到另一个新地址 H(2) …… 如此下去,直到求得的 H(n) 不再发生冲突
    • Hash(key) 是哈希函数,m 是哈希表表长,取余目的是为了使得到的下一个地址一定落在哈希表中
    • F(i) 是冲突解决方法,取法可以有以下几种:
      • 线性探测法 F ( i ) = 1 , 2 , 3 , . . . , m − 1 F(i) = 1, 2, 3, ..., m - 1 F(i)=1,2,3,...,m1
      • 二次探测法 F ( i ) = 1 2 , − 1 2 , 2 2 , − 2 2 , . . . , n 2 ( n ≤ m / 2 ) F(i) = 1^2, -1^2, 2^2, -2^2, ..., n^2(n ≤ m / 2) F(i)=12,12,22,22,...,n2(nm/2)
      • 伪随机数序列F(i) = 伪随机数序列

    开放地址法举例

    举例说明一下如何用以上三种冲突解决方法处理冲突,并得到新地址 H(i)。例如,在长度为 11 的哈希表中已经填有关键字分别为 28、49、18 的记录(哈希函数为 Hash(key) = key % 11)。

    现在将插入关键字为 38 的新纪录,根据哈希函数得到的哈希地址为 5,产生冲突。接下来分别使用这三种冲突解决方法处理冲突。

    在这里插入图片描述

    • 使用线性探测法:得到下一个地址 H ( 1 ) = ( 5 + 1 ) % 11 = 6 H(1) = (5 + 1) \% 11 = 6 H(1)=(5+1)%11=6,仍然冲突;继续求
      H ( 2 ) = ( 5 + 2 ) % 11 = 7 H(2) = (5 + 2) \% 11 = 7 H(2)=(5+2)%11=7,仍然冲突;继续求出 H ( 3 ) = ( 5 + 3 ) % 11 = 8 H(3) = (5 + 3) \% 11 = 8 H(3)=(5+3)%11=8,8
      对应的地址为空,处理冲突过程结束,记录填入哈希表中序号为 8 的位置。

    在这里插入图片描述

    • 使用二次探测法:得到下一个地址 H ( 1 ) = ( 5 + 1 ∗ 1 )   H(1) = (5 + 1*1)\ % 11 = 6 H(1)=(5+11) ,仍然冲突;继续
      求出 H ( 2 ) = ( 5 − 1 ∗ 1 )   H(2) = (5 - 1*1)\ % 11 = 4 H(2)=(511) ,4 对应的地址为空,处理冲突过程结束,记录
      填入哈希表中序号为 4 的位置。

    在这里插入图片描述

    • 使用伪随机数序列:假设伪随机数为 9,则得到下一个地址$ H(1) = (9 + 5) % 11
      = 3$,3 对应的地址为空,处理冲突过程结束,记录填入哈希表中序号为 3 的位置。

    在这里插入图片描述

    3.2 链地址法

    链地址法:将具有相同哈希地址的元素(或记录)存储在同一个线性链表中。
    链地址法是一种更加常用的哈希冲突解决方法。相比于开放地址法,链地址法更加简单。
    假设哈希函数产生的哈希地址区间为[0, m - 1],哈希表的表长为 m。则可以将哈希表定义为一个有 m 个头节点组成的链表指针数组 T

    • 这样在插入关键字的时候,只需要通过哈希函数 Hash(key) 计算出对应的哈希地址 i,然后将其以链表节点的形式插入到以 T[i] 为头节点的单链表中。在链表中插入位置可以在表头或表尾,也可以在中间。如果每次插入位置为表头,则插入操作的时间复杂度为 O(1)。
    • 而在在查询关键字的时候,只需要通过哈希函数 Hash(key) 计算出对应的哈希地址 i,然后将对应位置上的链表整个扫描一遍,比较链表中每个链节点的键值与查询的键值是否一致。查询操作的时间复杂度跟链表的长度 k 成正比,也就是 O ( k ) O(k) O(k)。对于哈希地址比较均匀的哈希函数来说,理论上讲, k = n / / m k = n // m k=n//m,其中 n 为关键字的个数,m 为哈希表的表长。

    相对于开放地址法,采用链地址法处理冲突要多占用一些存储空间(主要是链节点占用空间)。但它可以减少在进行插入和查找具有相同哈希地址的关键字的操作过程中的平均查找长度。这是因为在链地址法中,待比较的关键字都是具有相同哈希地址的元素,而在开放地址法中,待比较的关键字不仅包含具有相同哈希地址的元素,而且还包含哈希地址不相同的元素。

    链地址法举例

    举例来说明如何使用链地址法处理冲突。

    假设现在要存入的关键字集合 keys = [88, 60, 65, 69, 90, 39, 07, 06, 14, 44, 52, 70, 21, 45, 19, 32]。再假定哈希函数为 H a s h ( k e y ) = k e y % 13 Hash(key) = key \% 13 Hash(key)=key%13,哈希表的表长 m = 13,哈希地址范围为[0, m - 1]

    将这些关键字使用链地址法处理冲突,并按顺序加入哈希表中(图示为插入链表表尾位置),最终得到的哈希表如下图所示。

    k e y s = [ 88 , 60 , 65 , 69 , 90 , 39 , 07 , 06 , 14 , 44 , 52 , 70 , 21 , 45 , 19 , 32 ] keys = [88, 60, 65, 69, 90, 39, 07, 06, 14, 44, 52, 70, 21, 45, 19, 32] keys=[88,60,65,69,90,39,07,06,14,44,52,70,21,45,19,32]

    在这里插入图片描述

    哈希表总结

    本节讲解了一些比较基础、偏理论的哈希表知识。包含哈希表的定义,哈希函数、哈希冲突以及哈希冲突的解决方法。

    • 哈希表通过键 key 和一个映射函数 Hash(key) 计算出对应的值 value,把关键码值映射到表中一个位置来访问记录,以加快查找的速度
    • 哈希函数将哈希表中元素的关键键值映射为元素存储位置的函数
    • 哈希冲突:不同的关键字通过同一个哈希函数可能得到同一哈希地址

    哈希表的两个核心问题是:「哈希函数的构建」和「哈希冲突的解决方法」。

    • 常用的哈希函数方法有:直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等
    • 常用的哈希冲突的解决方法有两种:开放地址法 和 链地址法。

    学习视频

    哈希表相较于列表查找而言,速度要快很多,宽泛来说时间复杂度是 O ( 1 ) O(1) O(1),应用比较多,比如redis就是基于哈希表构建的数据库


    例题

    160 存在重复元素

    给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ,返回 true ;如果数组中每个元素互不相同,返回 false

    示例 1:

    输入:nums = [1,2,3,1]
    输出:true
    

    示例 2:

    输入:nums = [1,2,3,4]
    输出:false
    

    示例 3:

    输入:nums = [1,1,1,3,3,4,3,2,4,2]
    输出:true
    

    提示:

    • 1 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105
    • − 1 0 9 < = n u m s [ i ] < = 1 0 9 -10^9 <= nums[i] <= 10^9 109<=nums[i]<=109

    解题思路:

    • 先对数组进行排序。排序之后,判断相邻元素之间是否出现重复元素。
    • 使用哈希表,具体步骤如下:
      • 遍历数组中元素
      • 如果哈希表中出现了该元素,则说明出现了重复元素,直接返回 True
      • 如果没有出现,则在哈希表中添加该元素
      • 如果遍历完也没发现重复元素,则说明没有出现重复元素,返回 False

    第二种需要占用新的空间,但是时间会快一些。这里以第二种哈希表实现

    代码实现:

    • python实现
    class Solution:
        def containsDuplicate(self, nums: List[int]) -> bool:
            count = dict()
            for num in nums:
                if num not in count:
                    count[num] = 1
                else:
                    return True
            return False
    
    • c++实现
    class Solution {
    public:
        bool containsDuplicate(vector<int>& nums) {
            unordered_map<int, int> d;
            for(int x: nums)
            {
                if(d.find(x) != d.end())
                {
                    return true;
                }
                d.insert({x, 1});
            }
            return false;
        }
    };
    

    33 有效的数独

    请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。

    1. 数字 1-9 在每一行只能出现一次。
    2. 数字 1-9 在每一列只能出现一次。
    3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)

    注意:

    • 一个有效的数独(部分已被填充)不一定是可解的。
    • 只需要根据以上规则,验证已经填入的数字是否有效即可。
    • 空白格用 '.' 表示。

    示例 1:

    img

    输入:board = 
    [["5","3",".",".","7",".",".",".","."]
    ,["6",".",".","1","9","5",".",".","."]
    ,[".","9","8",".",".",".",".","6","."]
    ,["8",".",".",".","6",".",".",".","3"]
    ,["4",".",".","8",".","3",".",".","1"]
    ,["7",".",".",".","2",".",".",".","6"]
    ,[".","6",".",".",".",".","2","8","."]
    ,[".",".",".","4","1","9",".",".","5"]
    ,[".",".",".",".","8",".",".","7","9"]]
    输出:true
    

    示例 2:

    输入:board = 
    [["8","3",".",".","7",".",".",".","."]
    ,["6",".",".","1","9","5",".",".","."]
    ,[".","9","8",".",".",".",".","6","."]
    ,["8",".",".",".","6",".",".",".","3"]
    ,["4",".",".","8",".","3",".",".","1"]
    ,["7",".",".",".","2",".",".",".","6"]
    ,[".","6",".",".",".",".","2","8","."]
    ,[".",".",".","4","1","9",".",".","5"]
    ,[".",".",".",".","8",".",".","7","9"]]
    输出:false
    解释:除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
    

    提示:

    • board.length == 9
    • board[i].length == 9
    • board[i][j] 是一位数字(1-9)或者 '.'

    解题思路

    有效的数独满足以下三个条件:

    • 同一个数字在每一行只能出现一次;
    • 同一个数字在每一列只能出现一次;
    • 同一个数字在每一个小九宫格只能出现一次。

    可以使用哈希表记录每一行、每一列和每一个小九宫格中,每个数字出现的次数。只需要遍历数独一次,在遍历的过程中更新哈希表中的计数,并判断是否满足有效的数独的条件即可。因此考虑使用3个长度为9的哈希表数组,来表示该数字是否在所在的行,所在的列,所在的方格中出现过。整个方法具体步骤如下:

    • 遍历代表数独的二维数组board
    • 如果board[i][j].字符,继续判断下一个数独位置
    • 判断该位置所在行,所在列,所在方格的哈希表中是否出现了该数字
    • 如果出现了该数字,返回False
    • 如果遍历完整个数独都没有出现重复数字,返回True

    代码实现:

    • python实现
    class Solution:
        def isValidSudoku(self, board: List[List[str]]) -> bool:
            row_map = [dict() for _ in range(9)]
            cols_map = [dict() for _ in range(9)]
            boxs_map = [dict() for _ in range(9)]
            
            for i in range(9):
                for j in range(9):
                    if board[i][j] == '.':
                        continue
                    
                    num = int(board[i][j])
                    box_index = (i//3) * 3 + j // 3
                    row_num = row_map[i].get(num, 0)
                    col_num = cols_map[j].get(num, 0)
                    box_num = boxs_map[box_index].get(num, 0)
                    
                    if row_num > 0 or col_num > 0 or box_num > 0:
                        return False
                    
                    row_map[i][num] = 1
                    cols_map[j][num] = 1
                    boxs_map[box_index][num] = 1
            return True
    
    • c++实现
    class Solution {
    public:
        bool isValidSudoku(vector<vector<char>>& board) {
        
            int rows[9][9];
            int columns[9][9];
            int subboxes[3][3][9];
            
            memset(rows,0,sizeof(rows));
            memset(columns,0,sizeof(columns));
            memset(subboxes,0,sizeof(subboxes));
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    char c = board[i][j];
                    if (c != '.') {
                        int index = c - '0' - 1;
                        rows[i][index]++;
                        columns[j][index]++;
                        subboxes[i / 3][j / 3][index]++;
                        if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) {
                            return false;
                        }
                    }
                }
            }
            return true;
        }
    };
    

    161 存在重复元素 II

    给你一个整数数组 nums 和一个整数 k ,判断数组中是否存在两个 不同的索引 ij,满足 nums[i] == nums[j]abs(i - j) <= k 。如果存在,返回 true ;否则,返回 false

    示例 1:

    输入:nums = [1,2,3,1], k = 3
    输出:true
    

    示例 2:

    输入:nums = [1,0,1,1], k = 1
    输出:true
    

    示例 3:

    输入:nums = [1,2,3,1,2,3], k = 2
    输出:false
    

    提示:

    • 1 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105
    • − 1 0 9 < = n u m s [ i ] < = 1 0 9 -10^9 <= nums[i] <= 10^9 109<=nums[i]<=109
    • 0 < = k < = 1 0 5 0 <= k <= 10^5 0<=k<=105

    解题思路:

    • 哈希表,可以使用一个哈希表记录元素,key为元素,value为下标。如果遍历的时候发现哈希表中已经存在该元素了,那么比较哈希表中的下标与遍历的下标的关系是否满足<=k,如果满足,则返回True;如果不满足,则更新哈希表中的该元素对应的value为最新的下标,这样才能使得i-j的值尽可能的小

    代码实现:

    • python实现
    class Solution:
        def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
            d = dict()
            for i, val in enumerate(nums):
                if val not in d:
                    d[val] = i
                else:
                    index = d[val]
                    if i - index <= k:
                        return True
                    else:
                        d[val] = i
            return False
    
    • c++实现
    class Solution {
    public:
        bool containsNearbyDuplicate(vector<int>& nums, int k) {
            unordered_map<int, int> d;
            int length = nums.size();
            for(int i=0; i<length; i++)
            {
                int num = nums[i];
                auto it = d.find(num);
                if(it != d.end())
                {
                    int index = d[num];
                    if(i-index <= k)
                    {
                        return true;
                    }
                    else
                    {
                        it->second = i;
                    }
                }
                else
                {
                    d[num] = i;
                }
            }
            return false;
        }
    };
    

    355 宝石与石头

    给你一个字符串 jewels 代表石头中宝石的类型,另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。

    字母区分大小写,因此 "a""A" 是不同类型的石头。

    示例 1:

    输入:jewels = "aA", stones = "aAAbbbb"
    输出:3
    

    示例 2:

    输入:jewels = "z", stones = "ZZ"
    输出:0
    

    提示:

    • 1 <= jewels.length, stones.length <= 50
    • jewelsstones 仅由英文字母组成
    • jewels 中的所有字符都是 唯一的

    解题思路:

    • 哈希表:首先遍历jewels,并使用哈希表进行存储;其次遍历stones,然后判断元素是否在哈希表中,如果在的话,宝石个数+1

    代码实现:

    • python实现
    class Solution:
        def numJewelsInStones(self, jewels: str, stones: str) -> int:
            d = dict()
            count = 0
            for s in jewels:
                d[s] = ''
            
            for s in stones:
                if s in d:
                    count += 1
            return count
    
    • c++实现
    class Solution {
    public:
        int numJewelsInStones(string jewels, string stones) {
            int count = 0;
            
            unordered_map <char, int> d;
            for(auto s: jewels)
            {
                d[s] = 1;
            }
            
            for(auto s: stones)
            {
                auto it = d.find(s);
                if(it != d.end())
                {
                    count++;
                }
            }
            return count;
        }
    };
    

    374 子域名访问计数

    网站域名 "discuss.leetcode.com" 由多个子域名组成。顶级域名为 "com" ,二级域名为 "leetcode.com" ,最低一级为 "discuss.leetcode.com" 。当访问域名 "discuss.leetcode.com" 时,同时也会隐式访问其父域名 "leetcode.com"以及 "com"

    计数配对域名 是遵循 "rep d1.d2.d3""rep d1.d2" 格式的一个域名表示,其中 rep 表示访问域名的次数,d1.d2.d3 为域名本身。

    • 例如,"9001 discuss.leetcode.com" 就是一个 计数配对域名 ,表示 discuss.leetcode.com 被访问了 9001 次。

    给你一个 计数配对域名 组成的数组 cpdomains ,解析得到输入中每个子域名对应的 计数配对域名 ,并以数组形式返回。可以按 任意顺序 返回答案。

    示例 1:

    输入:cpdomains = ["9001 discuss.leetcode.com"]
    输出:["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]
    解释:例子中仅包含一个网站域名:"discuss.leetcode.com"。
    按照前文描述,子域名 "leetcode.com" 和 "com" 都会被访问,所以它们都被访问了 9001 次。
    

    示例 2:

    输入:cpdomains = ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
    输出:["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
    解释:按照前文描述,会访问 "google.mail.com" 900 次,"yahoo.com" 50 次,"intel.mail.com" 1 次,"wiki.org" 5 次。
    而对于父域名,会访问 "mail.com" 900 + 1 = 901 次,"com" 900 + 50 + 1 = 951 次,和 "org" 5 次。
    

    提示:

    • 1 <= cpdomain.length <= 100
    • 1 <= cpdomain[i].length <= 100
    • cpdomain[i] 会遵循 "repi d1i.d2i.d3i""repi d1i.d2i" 格式
    • repi 是范围 [1, 104] 内的一个整数
    • d1id2id3i 由小写英文字母组成

    解题思路:

    • 哈希表:每次先把前面的数字取出,然后从后向前遍历,遇到.就将后面的字符串放进哈希表,数量加上之前的,然后拼接成字符串即可

    代码实现:

    • python实现
    class Solution:
        def subdomainVisits(self, cpdomains: List[str]) -> List[str]:
            hashmap = {}
            res = []
            def deal(string):
                nums, half_last = string.split(' ')
                nums = int(nums)  # 类型转换
                # 处理half_last
                str_ = ''
                for i in range(len(half_last)-1, -1, -1):
                    if half_last[i] == '.':
                        if str_ in hashmap:
                            hashmap[str_] += nums
                        else:
                            hashmap[str_] = nums
                    str_ = half_last[i] + str_
                # 将最长域名加入其中
                if half_last in hashmap:
                    hashmap[half_last] += nums
                else:
                    hashmap[half_last] = nums
            for ch in cpdomains:
                deal(ch)
            for k, v in hashmap.items():
                res.append(' '.join([str(v), k]))
            return res
    
    • c++实现
    class Solution {
    private:
        vector<string> Split(const string& s, char c)
        {
            vector<string> res;
            stringstream ss(s);
            string curr;
            while(std::getline(ss, curr, c))
            {
                // cout << "[" <<  curr << "]" << endl;
                res.push_back(curr);
            }
            return res;
        }
    
    public:
        vector<string> subdomainVisits(vector<string>& cpdomains) {
            // 保存数量映射的哈希表
            unordered_map<string, int> str2cnt;
    
            // 遍历去拆分字符串
            for (const string& cp : cpdomains)
            {
                vector<string> cc = Split(cp, ' ');
                vector<string> s = Split(cc[1], '.');
                int cnt = stoi(cc[0]);
                // 从后往前去构建字符串数组
                string curr = "";
                for (int i = s.size()-1; i >= 0; --i)
                {
                    curr = s[i] + (curr.empty() ? "" : ".") + curr;
                    str2cnt[curr] += cnt;
                }
            }
    
            vector<string> res;
            for (auto iter = str2cnt.begin(); iter != str2cnt.end(); ++iter)
            {
                res.push_back(to_string(iter->second) + " " + iter->first);
            }
    
            return res;
        }
    };
    
    展开全文
  • 哈希函数和哈希

    2021-09-06 21:35:28
    哈希表 主要作用:加快查找速度。可以近似看成O(1). 哈希函数特点: 1.其输入无限,输出有限。 2.每次相同的输入一定得到相同的输出。不同的输入也可能产生相同的输出。(哈希碰撞) 3.输出分布是绝对离散的,不会...

    哈希函数特点:

    哈希函数特点:

    1. 其输入无限,输出有限。
    2. 每次相同的输入一定得到相同的输出。
    3. 不同的输入也可能产生相同的输出。(哈希碰撞)
    4. 输出分布是绝对离散的,不会受输入的影响,即同样的面积在任何地方框点都是差不多的。(最重要,哈希函数主要利用这个性质)
      在这里插入图片描述

    ==4.==任何值模上一个数,最后一定得到0-该数的一个范围值。比如任何数模(或者说取余)上100,最后得到的值一定在0-99范围内。并且是绝对均匀分布。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    哈希函数不害怕多个重复数字,因为他可以把多个数字都压缩在同一个值上。

    哈希函数的目的是用于哈希表的第一步数组查询,直接通过取模(哈希函数)就得到哈希表对应的位置。这一步的时间复杂度是O(1)。(big)

    哈希表

    主要作用:加快查找速度。可以近似看成O(1).

    时间复杂度:
    哈希表每次增删改查的代价可以说是O(1),虽然每次扩容的代价是O(logn)。
    在这里插入图片描述
    一个原因是现实使用的工程数据量都是非常低的,另一个原因是离线技术,不占用用户使用的时候的时间。

    总结:

    • 哈希函数特征:

      1.与输入规律无关;2.哈希函数生成16位的码每一位都是相互独立的(因此利用一个哈希函数可造出很多哈希函数)
      
    • 哈希表的增删改查复杂度O(1)(哈希表的扩容复杂度log以n为底N,n为扩容的倍数,或者可以用离线扩容,因此哈希表的增删改查复杂度认为是O(1))

    • 利用哈希函数做分流,处理大数据问题

    哈希函数的缺点:

    1.**当更多的数插入时,哈希表冲突的可能性就更大。**对于冲突,哈希表通常有两种解决方案:第一种是线性探索,相当于在冲突的槽后建立一个单链表,这种情况下,插入和查找以及删除操作消耗的时间会达到O(n),且该哈希表需要更多的空间进行储存。
    第二种方法是开放寻址,他不需要更多的空间,但是在最坏的情况下(例如所有输入数据都被map到了一个index上)的时间复杂度也会达到O(n)。

    2.在决定建立哈希表之前,最好可以估计输入的数据的size。否则,resize哈希表的过程将会是一个非常消耗时间的过程。
    例如,如果现在你的哈希表的长度是100,但是现在有第101个数要插入。这时,不仅哈希表的长度可能要扩展到150,且扩展之后所有的数都需要重新rehash。

    3.哈希表中的元素是没有被排序的。然而,有些情况下,我们希望储存的数据是有序的。

    哈希表的应用场景:

    C++中如unordered_map和unordered_set都是用红黑树实现的。
    哈希表适用于那种查找性能要求高,数据元素之间无逻辑关系要求的情况。
    例如做文件校验或数字签名。当然还有快速查询功能的实现。

    红黑树:

    主要目的:主要是用它来存储有序的数据,它增删改查的时间复杂度都是O(logn)。
    采用迭代器遍历一棵红黑树的时间复杂度是多少呢? 是O(N)。
    红黑树首先是平衡二叉树(AVL)的一种,所以他一定满足根节点小于左子树大于右子树。再然后才是它特有的属性。

    二分查找法———二分查找树———AVL树———红黑树
    二分查找法不能处理大数据和非数字情况,有了二分查找树;
    二分查找树会出现单链表情况,所以有了AVL树通过旋转实现绝对平衡;
    但是AVL树为了维护绝对平衡,几乎每次插入删除都要进行旋转操作;
    删除节点的时候,需要要维护从被删除节点到根节点这几个节点的平衡,旋转的时间复杂度是O(logn),
    所以有了红黑树,在牺牲一定的查找效率的情况下,提升了删除效率

    RB-Tree是功能、性能、空间开销的折中结果
    总结:实际应用中,若搜索的次数远远大于插入和删除,那么选择AVL,
    如果搜索,插入删除次数几乎差不多,应该选择RB。

    应用场景:C++中如map和set都是用红黑树实现的

    红黑树和哈希表的比较

    map的底层是红黑树,unordered_map底层是哈希表,明明哈希表的查询效率更高,为什么还需要红黑树?
    hashmap有unordered_map,map其实就是很明确的红黑树。map比起unordered_map的优势主要有:
    1.map始终保证遍历的时候是按key的大小顺序的,这是一个主要的功能上的差异。(有序无序)

    2.时间复杂度上,红黑树的插入删除查找性能都是O(logN)
    而哈希表的插入删除查找性能理论上都是O(1),他是相对于稳定的,最差情况下都是高效的。
    哈希表的插入删除操作的理论上时间复杂度是常数时间的,这有个前提就是哈希表不发生数据碰撞。在发生碰撞的最坏的情况下,哈希表的插入和删除时间复杂度最坏能达到O(n)。

    3.map可以做范围查找,而unordered_map不可以。
    4. 扩容导致迭代器失效。 map的iterator除非指向元素被删除,否则永远不会失效。unordered_map的iterator在对unordered_map修改时有时会失效。

    5.因为3,所以对map的遍历可以和修改map在一定程度上并行(一定程度上的不一致通常可以接受),而对unordered_map的遍历必须防止修改map的iterator可以双向遍历,这样可以很容易查找到当前map中刚好大于这个key的值,或者刚好小于这个key的值这些都是map特有而unordered_map不具备的功能。(这个不太明白,先放一放)

    对第二点的参考
    时间复杂度
    红黑树的插入删除查找性能都是O(logN)
    而哈希表的插入删除查找性能理论上都是O(1),在这个对比上来看,红黑树性能远没有哈希表优秀。
    但是值得一提的是红黑树从上面介绍的资料来看,他是相对于稳定的,最差情况下都是高效的。
    而相对于哈希表这个数据结构来讲,哈希表的插入删除操作的理论上时间复杂度是常数时间的,这有个前提就是哈希表不发生数据碰撞。
    在发生碰撞的最坏的情况下,哈希表的插入和删除时间复杂度最坏能达到O(n)。
    而在一般情况下,如果在实际应用中,当然一个相对稳定且快速的数据结构是比较理想的选择。

    HashMap是有序的还是无序的?

     HashMap的数据结构:数组+单链表,当存在hashCode相同的不同对象时,会将value以单链表的形式,往后增加。数组加快访问速度,单链表解决hash值冲突。
     调用put方法时,发生了什么:根据key的hashCode,计算出将key放入数组的index下标,index=(数组长度-1)&hashCode
     HashMap循环遍历的顺序:根据数组顺序+单链表顺序进行输出。
    虽然遍历时,用的EntrySet,但是可以简单理解为,两层循环输出数据,外层循环为遍历数组,内层循环为遍历单链表。
     HashMap在初始化时,默认初始变量为16,以及默认的扩容因子为0.75

    结论

    若两个Map的初始化容量不一致,就算同时插入相同的key,最后输出的顺序,不一定一直

    再结论

    代码规范性挺重要的,想要依赖Map保持有序性,请使用LinkedHashMap
    HashMap是通过key的hashCode来计算索引的,与元素放入的先后顺序没有什么关系,所以我们在使用HashMap的时候,千万不要寄希望于HashMap中的数据与我们压入的数据的先后顺序一致。如果要保证压入的顺序一致,可以使用LinkedHashMap对象。

    HashMap 为啥线程不安全?

    (1)HashMap 不是一个线程安全的容器,不安全性体现在多线程并发对 HashMap 进行 put 操作上。
    如果有两个线程 A 和 B ,首先 A 希望插入一个键值对到 HashMap 中,在决定好插入的位置(桶)的位置进行 put 时,此时 A 的时间片正好用完了,
    轮到 B 运行,B 运行后执行和 A 一样的操作,只不过 B 成功把键值对插入进去了。
    如果 A 和 B 插入的位置(桶)是一样的,那么线程 A 继续执行后就会覆盖 B 的记录,造成了数据不一致问题。
    (2)还有一点在于 HashMap 在扩容时,因 resize 方法会形成环,造成死循环,导致 CPU 飙高

    展开全文
  • 为什么要构建哈希表? 现在有一组数据,我们想...哈希就是根据设定好的哈希函数和处理发生哈希冲突的解决方法,哈希是一种存储方法,也是一种查找方法,算法中只要用到这种哈希思想,就可以叫做哈希算法(hash) 哈希

    为什么要构建哈希表?

    现在有一组数据,我们想查找一个值(x)是否在这组数据中,通常来说,我们需要把这组数据遍历一遍,来看看有没有x这个值。

    这时,我们发现这样查找数据要花费的时间复杂度为O(n),链表、顺序表都是如此。

    为了降低查找数据的时间复杂度,那我们就不能去遍历所有的数据来查找,我们需要找到新的方法来查找数据,这时我们就引入了哈希表。

    哈希

    哈希就是根据设定好的哈希函数和处理发生哈希冲突的解决方法,哈希是一种存储方法,也是一种查找方法,算法中只要用到这种哈希思想,就可以叫做哈希算法(hash)

    哈希函数

    1.定义

    将一组数据的关键字映射到连续且有限的地址集(区间)可以将映射到地址集上的像记录在表中,这个表就是我们说的哈希表,这个映射的过程一般叫做哈希造表 或者叫散列,这个映射关系叫做哈希函数或者散列

    2.构造方法

    1)直接定址法

    取其关键字或者关键字的某个线性函数值为哈希地址。即:
    f ( k e y ) = a × k e y + b ( a 、 b  为常数  ) f(k e y)=a \times k e y+b \quad(a 、 b \text { 为常数 }) f(key)=a×key+b(ab 为常数 )
    例如:现在有一个0~100岁的人口统计表,其中年龄作为关键字哈希函数取关键字:
    f ( k e y ) = k e y f(k e y)= k e y f(key)=key
    直接定址
    如果我们要统计1980年后出现的人口数,那么我们就可以对出生年份这个关键字减去1980来作为地址,即:
    f ( k e y ) = k e y − 1980 f(k e y)= k e y-1980 f(key)=key1980
    在这里插入图片描述

    2)数字分析法

    假设关键字是以r为基的数(如:以10为基的十进制数),并且哈希表可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址。
    例如:我们的11位手机号“130xxxx1234”,前三位表示不同运营商公司的子品牌,中间四位是HLR识别号,表示用户的归属地,后面四位才是真正的用户号,如下图所示

    手机号

    那么如果我们要存储某家公司员工登记表,如果用手机号作为关键字,那么很有可能前7位是相同的,那么选取后四位作为哈希地址就是不错的选择。

    3)平方取中法

    这个方法计算比较简单,假设关键字是1234,那么它的平方就是1522756,再抽取中间的3位就是227,用做哈希地址。这种方法比较适合不知道关键字的分布,而位数又不是很大的情况。

    4)折叠法

    折叠法是将关键字从左到右分割成位数相等的几部分,然后将这几部分叠加求和,并按照哈希表表长,取后几位作为哈希地址。
    比如我们的关键字是9876543210,哈希表表长为3位,我们将其分为四组987|654|321|0,然后将它们叠加求和987+654+321+0=1962,在求后三位得到哈希地址为962.
    折叠法事先不需要知道关键字的分布,适合关键字位数比较多的情况。

    5)除留余数法

    此方法是最常用的构造哈希函数的方法。对于哈希表长为m的哈希函数公式为:
    f (  key  ) =  key    m o d   p ( p ⩽ m ) f(\text { key })=\text { key } \bmod p(p \leqslant m) f( key )= key modp(pm)
    mod是取模(求余数)的意思,并且此方法不仅可以直接对关键字取模,也可以在折叠、平方取中后再取模。此方法的关键在于选取合适的p,如果选的不好很容易造成哈希冲突。
    如对下表,我们对于有12个记录的关键字构造哈希表时,就用了 f (  key  ) =  key  .   m o d   12 f(\text { key })=\text { key } .\bmod 12 f( key )= key .mod12的方法,比如 29 m o d 12 = 5 29mod12=5 29mod12=5,所以它存储在下表为5的位置。

    6)随机数法

    选取一个随机数,取关键字的随机函数值作为它的哈希地址,也就是 f ( k e y ) = r a n d o m ( k e y ) f(key)=random(key) f(key)=random(key).这里 r a n d o m random random是随机函数。当关键字的长度不等时,采用这个方法比较合适。

    哈希冲突

    1.定义

    不同数据的关键字通过哈希函数得到一个相同的地址,这时就发生冲突,这种冲突一般叫做哈希冲突(存放位置有值)。

    2.构造方法

    1)开放定址法

    此方法就是一旦发生了冲突,就去寻找下一个空的哈希地址,只要哈希列表足够大,空的哈希地址总能找到,并将记录存入。
    公式为: f i (  key  ) = ( f (  key  ) + d i ) MOD ⁡ m ( d i = 1 , 2 , 3 , ⋯ ⋯   , m − 1 ) f_{i}(\text { key })=\left(f(\text { key })+d_{i}\right) \quad \operatorname{MOD} m\left(d_{i}=1,2,3, \cdots \cdots, m-1\right) fi( key )=(f( key )+di)MODm(di=1,2,3,,m1)

    2)再哈希函数法

    对于我们的哈希函数来说,我们可以事先准备多个哈希函数
    f i (  key  ) = R H i (  key  ) ( i = 1 , 2 , ⋯   , k ) f_{i}(\text { key })=R H_{i}(\text { key }) \quad(i=1,2, \cdots, k) fi( key )=RHi( key )(i=1,2,,k)
    这里 R H i R H_{i} RHi就是不同的哈希函数,可以把我们之前说的除留余数、折叠、平方取中等方法全部用上。每当哈希地址冲突时,就换一个哈希函数计算,相信总会有一个可以把冲突解决掉,当然这种方法会相应的增加计算的时间。

    3)链地址法

    我们将所有关键字为同义词的记录存储在一个单链表中,称这种表为同义词子表,在散列表中只存储所有同义词子表的头指针。对于关键字集合{12,67,56,16,25,37,22,29,15,47,48,34},我们用前面同样的12为除数,进行除留余数法,可得到如下图结构,此时,已经不存在冲突换址的问题,无论有多少个冲突,都只是在当前位置给单链表增加结点的问题。
    在这里插入图片描述
    链地址法对于可能会造成很多冲突的哈希函数来说,提供了绝不会出现找不到地址的保障。当然,这也就带来了查找时需要遍历单链表的性能损耗。

    4)公共区溢出法

    这个方法就是建立一个溢出表,把所有冲突的数据都存进去,我们给所有冲突的关键字建立了一个公共溢出区来存放。

    展开全文
  • 哈希表与哈希查找

    2021-08-28 14:07:36
    在这种查找方式中,“比较”是必不可免的,那么是否有一种方法可以避免比较,即通过关键字的某种形式来存储该数据的地址,这样在查找时,将待查询的关键字通过一定计算就可以得到目的数据的地址。 文章目录哈希表...
  • 哈希表总结

    2021-11-28 16:20:00
    二,哈希冲突(哈希碰撞) 1.概念 2.分析 初步分析: 避免冲突时的哈希函数设计: 常见的哈希函数: 3.解决 1.闭散列 2.开散列 三,模拟实现哈希桶(开散列) 模拟实现的准备工作 1.定义哈希表中的结点 ...
  • 本文暂且不表这些基础知识,更多的重点在于哈希的一些应用和题目,对于哈希表、哈希函数从来没有学习过或者已经遗忘大部分的同学,建议先去阅读相关内容,否则本文不会成为一篇值得阅读的内容。 1.哈希的函数的定义...
  • 3.1 哈希算法

    2018-08-25 18:07:36
    哈希算法在区块链系统中的应用很广泛:比特币使用哈希算法通过公钥计算出了钱包地址、区块头以及交易事务的哈希值,梅克尔树结构本身就是一棵哈希树,就连 挖矿算法都是使用的哈希值难度匹配;以太坊中的挖矿计算也...
  • 哈希-基础数据结构

    2022-03-11 19:18:00
    目的:可以在第一时间内确定这个x值到底在不在这个数组? 数据和存储位置没有任何关系 例:我想在一组数中寻找数33 只能从前向后全部遍历一遍这个数组,确定33是不是在这个数组中,时间复杂度..
  • 哈希函数相关的比较分析

    千次阅读 2022-03-03 08:30:28
    哈希函数的几个临近的概念,和应用实例的一些简单调查。主要比较了密码学哈希,非密码学哈希,以及应用实例的哈希密码、密钥派生函数。
  • 哈希表大总结

    2020-11-26 18:32:09
    哈希表总结 哈希表 记录的存储位置和它的关键字之间建立一确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。 因而查找时,只需根据这个对应关系f找到给定值K的像f(K)。 若结构中存在关键字和K相等...
  • 1. 哈希表知识 1.1 哈希表简介 哈希表(Hash Table):也叫做散列表。是根据键(key)、值(value)直接进行访问的数据结构。也就是说,它通过键key和一个映射函数Hash(key)计算出对应的值value,把key和value映射到...
  • 哈希表支持一种最有效的检索方法:散列。 从根来上说,一个哈希表包含一个数组,通过特殊的索引值(键)来访问数组中...计算哈希值和在数组中进行索引都只消耗固定的时间,因此哈希表的最大亮点在于它是一种运行时...
  • 基于哈希函数的签名

    千次阅读 2019-05-13 18:28:28
    (这里当然存在许多例外,但最棒的部分在于,不论 X 属于什么分布,找到 X 的时间成本和暴力搜寻相同。) 抗-次原像攻击 :这和前者有些微的差别。给定输入 X,对于攻击者来说,要找到另一个 X' 使得 H(X)=H(X') ...
  • 关于哈希表,在内核里设计两个很重要的数据结构:哈希链表节点:点击(此处)折叠或打开/*...可以看到哈希节点和内核普通双向链表的节点唯一的区别就在于,前向节点pprev是个两级指针,至于为什么这样设计而不采用st...
  • 哈希算法

    2020-08-17 15:01:34
    哈希算法的目的就是为了验证原始数据是否被篡改。 Java字符串的hashCode()就是一个哈希算法,它的输入是任意字符串,输出是固定的4字节int整数: "hello".hashCode(); //0x5e918d2 "hello, java".hashCode(); //...
  • 哈希索引

    千次阅读 2019-05-22 17:09:45
    哈希索引(hash index)基于哈希表实现,只有精确匹配索引所有列的查询才有效。对于每一行数据,存储引擎都会对所有的索引列计算一个哈希码(hash code),哈希码是一个较小的值,并且不同键值的行计算出来的哈希码...
  • 哈希算法(Hash)又称摘要算法(Digest),它的作用是:对任意一...哈希算法的目的就是为了验证原始数据是否被篡改。 Java字符串的hashCode()就是一个哈希算法,它的输入是任意字符串,输出是固定的4字节int整数: ...
  • 区块链技术之哈希指针

    千次阅读 2021-09-17 22:25:54
    先给出答案,这与区块链的数据结构哈希指针和默克尔树有关。那么我们今天先分享哈希指针相关的内容。 1. 那些年学过的链表 区块链,顾名思义也是链,学过计算机数据结构的朋友都知道,数据结构里面有一种就是...
  • 哈希

    千次阅读 2016-12-07 17:26:42
    0、引入 哈希表支持一种最有效的检索方法:散列。从根本上来说,一个哈希表包含一个数组,通过特殊的索引值(键)来访问数组中的...由于计算哈希值和在数组中进行索引都只消耗固定的时间,因此哈希表的最大亮点在于它是
  • 数据结构与算法(七)-哈希表(HashTable)

    千次阅读 2022-01-11 17:04:47
    哈希表的结构就是数组,但它神奇之处在于对下标值的一种变换,这种变换我们可以称之为哈希函数,通过哈希函数可以获取HashCode。哈希表通常是基于数组实现的,但是相对于数组,它存在更多优势 1. 哈希表的优点 哈希...
  • 使用哈希表的好处

    千次阅读 2020-07-19 19:31:53
    (这个函数不用纠结,我们现在的目的是了解为什么要有这么一个函数)。 对于第一个元素 h(13) = 13%5 = 3; 也就是说13的下标为3;即Hash[3] = 13; 对于第二个元素 h(7) = 7 % 5 = 2; 也就是说7的下标为2; 即Hash...
  • 哈希猫很牛吗

    2021-06-16 16:52:14
    哈希猫(Hashcat)是一款在渗透人员、系统管理员,甚至是网络罪犯和网络...它的优点在于瞬间加密,但如果想暴力破解将函数逆向出来,以目前的计算机算力而言,在我们有生之年几乎是不可能的。(数世咨询:王小云教授的破
  • 点击上方蓝字关注我们基于特征选择的局部敏感哈希位选择算法周文桦, 刘华文, 李恩慧浙江师范大学数学与计算机科学学院,浙江 金华 321001摘要:作为主流的信息检索方法,局部敏感哈希往往...
  • 目 录 Redis列表(list)常用命令数据结构Redis 集合(set)常用命令数据结构Redis哈希(Hash)常用命令数据结构Redis有序集合Zset(sorted set)常用命令数据结构跳跃表 Redis列表(list) 单键多值 Redis列表是简单...
  • 哈希表概述

    千次阅读 2018-05-22 21:46:50
    一、什么是哈希表? &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键...
  •   在顺序表查找时,如果要查找某个关键字的记录,就是从表头开始,挨个的比较记录a[i]...最终的目的都是为了查找那个i,其实也就是相对应的下标,再通过顺序存储位置计算的方法,LOC(ai)=LOC(a1)+(i-1) * c,得到最终...
  • 原标题:解析区块链中的核心技术哈希(Hash)算法作者:崔利民区块链是分布式数据存储、点对点传输、共识机制、加密算法等计算机技术的新型应用模式。区块链的关键技术组成主要为:P2P网络协议、共识机制、密码学技术...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 38,355
精华内容 15,342
关键字:

哈希的目的在于