• 哈希(Hash)



    一、哈希是什么?

      Hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的 输入 (又叫做预映射pre-image)通过散列算法变换成固定长度的 输出 ,该输出就是散列值。 这种转换是一种 压缩映射 ,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。

      举个例子,我们现在有一组数据"香香"、“螃蟹”,通过哈希运算后,可以获得一个数列,无论这组数据有多长"锟斤拷锟斤拷锟斤拷……",经过运算后也是固定长度的数列,而且这个过程 不 可 逆

    二、哈希冲突

    现有数组{3,7,19,300,700};
    哈希函数设置为:hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
    由于300%10 -> 0
    700 % 10 -> 0,
    可以发现,300和700映射了相同的位置,这就发生了哈希冲突
    在这里插入图片描述
    怎么解决哈希冲突?

    1. 闭散列–开放定址法
    2. 开散列–拉链法/哈希桶

    三、开放定址法

    闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被装满,说明在哈希表中必然还有空位置,那么可以把key存放到冲突位置中的“下一个” 空位置中去。

    当发生地址冲突后,求解下一个地址:
    ND =( D+di)%m  i=1,2,…,k(k<= m-1)

    假如冲突很多,1占了1的位置,11只能占2的位置,21占3的位置……再放12的时候,就只能放在4的位置。

    1.线性探测

    D = H(key);
    ND = (D+di)%m; di取1,2,3,……,m-1
    线性探测再散列处理冲突的基本思想:若数据元素在存储地址D发生冲突,则放到存储地址(D+1)%m;若又发生冲突则放到存储地址(D+2)%m;……;直到碰到第一个为空的存储地址(D+i)%m,则将数据元素存放在该存储空间。

    2.二次探测

    D = H(key);
    ND = (D+di)%m; di取11,-11,22,-22,……,KK,-KK  (K≤m/2)

    四、拉链法/哈希桶

    开散列法又叫链地址法(开链法),首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子集合,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中。
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    瞧瞧!拉链法在每个元素下再拉一个数组(也可以是其他数据结构),有几个,挂几个,这样就不会相互影响、抢占别人的位置了。

    五、哈希的应用

    1.位图

    1.1 面试题

    给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。

    1. 遍历,时间复杂度O(N)
    2. 排序(O(NlogN)),利用二分查找: logN
    3. 位图解决,数据是否在给定的整形数据中,结果是在或者不在,刚好是两种状态,那么可以使用一个二进制比特位来代表数据是否存在的信息,如果二进制比特位为1,代表存在,为0代表不存在。比如:
      在这里插入图片描述

    1.2 位图概念

    所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的

    1.3 位图的应用

    1. 快速查找某个数据是否在一个集合中
    2. 排序 + 去重
    3. 求两个集合的交集、并集等
    4. 操作系统中磁盘块标记

    2.布隆过滤器

    2.1概念

    布隆过滤器是由布隆(Burton Howard Bloom)在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构,特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”,它是用多个哈希函数,将一个数据映射到位图结构中。此种方式不仅可以提升查询效率,也可以节省大量的内存空间。
    在这里插入图片描述

    2.2布隆过滤器的查找

    布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中,因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找:分别计算每个哈希值对应的比特位置存储的是否为零,只要有一个为零,代表该元素一定不在哈希表中,否则可能在哈希表中。
    注意:布隆过滤器如果说某个元素不存在时,该元素一定不存在,如果该元素存在时,该元素可能存在,因为有些哈希函数存在一定的误判。
    比如:在布隆过滤器中查找"alibaba"时,假设3个哈希函数计算的哈希值为:1、3、7,刚好和其他元素的比特位重叠,此时布隆过滤器告诉该元素存在,但实该元素是不存在的。

    2.3布隆过滤器的删除

    布隆过滤器不支持删除。

  • 相关阅读:
    2025快手校招面试真题汇总及其解答(二)
    商城小程序开发|二级分销裂变商城小程序怎么赚钱?
    Multiplexer and Demultiplexer(多路复用器和解复用器)
    【微众银行秋招】230903三、平均值 <前缀和>
    Go 存储系列:LSM存储引擎 LevelDB
    PTA 1064 朋友数(Python3)
    免费的在线白板协作工具有哪些?
    Celery基本语法
    CAPL 无法处理 xlsx 表格,Python老大哥曲线助攻
    93. 复原 IP 地址
  • 原文地址:https://blog.csdn.net/m0_63742310/article/details/128024733