哈希(Hash)
文章目录
- 一、哈希是什么？
- 二、哈希冲突
- 三、开放定址法
- 1.线性探测
- 2.二次探测
- 四、拉链法/哈希桶
- 五、哈希的应用
- 1.位图
- 1.1 面试题
- 1.2 位图概念
- 1.3 位图的应用
- 2.布隆过滤器
- 2.1概念
- 2.2布隆过滤器的查找
- 2.3布隆过滤器的删除
一、哈希是什么？
Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的 输入 （又叫做预映射pre-image）通过散列算法变换成固定长度的 输出 ，该输出就是散列值。 这种转换是一种 压缩映射 ，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。
举个例子，我们现在有一组数据"香香"、“螃蟹”，通过哈希运算后，可以获得一个数列，无论这组数据有多长"锟斤拷锟斤拷锟斤拷……"，经过运算后也是固定长度的数列，而且这个过程 不 可 逆。
二、哈希冲突
现有数组{3，7，19，300，700}；
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。
由于300%10 -> 0
700 % 10 -> 0,
可以发现，300和700映射了相同的位置，这就发生了哈希冲突
怎么解决哈希冲突？
- 闭散列–开放定址法
- 开散列–拉链法/哈希桶
三、开放定址法
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把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亿个数中。
- 遍历，时间复杂度O(N)
- 排序(O(NlogN))，利用二分查找: logN
- 位图解决，数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：
1.2 位图概念
所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的
1.3 位图的应用
- 快速查找某个数据是否在一个集合中
- 排序 + 去重
- 求两个集合的交集、并集等
- 操作系统中磁盘块标记
2.布隆过滤器
2.1概念
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
2.2布隆过滤器的查找
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。
注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。
比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。
2.3布隆过滤器的删除
布隆过滤器不支持删除。