🍕 哈希
哈希函数需要有的功能:
- 输入范围: 无穷
- 输出范围: 有穷
- 比如 MD5, 输出范围就是 [0,
], 即 128 位的比特数, 或 32 位的 16 进制数。
- 比如 MD5, 输出范围就是 [0,
- 一致性: 相同输入, 相同输出。 当然, 不同输入也可能有相同输出(碰撞)
- 不可逆性: 也叫坑碰撞性。
- 输入敏感性: 微小的输入变化, 会导致巨大的输出变化。
- 离散性, 分布均匀性
- 将输出看做一个"域", 因为任意输入值的输出, 在这个域上足够离散, 所以域中的输出, 才足够均匀。 这也是衡量哈希好坏的一个标准。
- 比如 "域" 是一个圆圈, 每输入一个字符串, 就在域中点上一个点, 即使字符串很相似, 由于哈希的离散型, 他也能把这个点的位置变得很不相同。
- 所以, 即使你输入的足够多, 这个圆圈上的点也是非常均匀的, 这样才能保证不会"碰撞"
- 对输出结果进行模运算后, 仍然具备离散性。
- 因为哈希的输出域太大了, 所以可以通过模运算, 将输出域缩小, 比如与 m 进行模运算, 就能够保证输出范围变成 [0, m-1]。
- 高效性: 运算的时间复杂度是
O(1)的, 当然, 这个常数比较大, 不像计算 1+1 等于 2 那么快。
哈希的实现方式有很多, 但都需要实现有上面的功能。 简单提一嘴哈希函数的一种实现。 任何数据都是二进制, 以一种编造好的规律, 对每一位都执行操作, 比如这一位执行 &, 另一位执行 |, 又有一个执行 !。
经典哈希表原理
【基本原理】:
- 利用哈希函数的离散性, 并且对输出值求模, 然后各自放到一个"桶"里面。
- 一个 "桶" 中的结构是链表结构, 当一个桶中放的元素超过指定的数字 k 时, 就会对哈希表进行扩容。
- 当检测到一个桶的元素超过 k 时, 说明全部通的元素都基本要超过 k 了(均匀性)
- 扩容就是增加哈希表的桶的数量, 同时将原有哈希表中的元素全部重新执行一遍哈希函数, 然后放到新的哈希表中。
【时间复杂度】:
- 哈希函数是 O(1), 计算出哈希值后求模, 同时定位到对应的桶也是 O(1) 级别的, 但是一个桶中最多有 k 个元素, k 是一个常数, 比如设置为 6, 所以在桶中查找元素是也是 O(1)
- 增删改查的时间复杂度都可以认为是 O(1)。重点在于扩容的时间复杂度。 和之前计算堆的扩容类似, 每次都是成倍扩容, 成倍扩容时会重新计算就哈希表中的元素值, 然后放到新哈希表中, 同时桶中的元素会减半。
- 扩容代价, 假设增加到了 N 个字符串, 那么意味扩容了 logN 次, 扩容是每个元素都会重新计算哈希值并求模放到新的哈希表中, 所以拷贝的代价是 O(N), 扩容的总代价就是 O(N logN), 将代价平摊到每一个元素上, 那么每一个元素的扩容代价就是 O(logN)
- 所以, 算上扩容代价时, 增删改查的时间复杂度是 O(logN) 的, 那为什么又认为哈希表的增删改查是 O(1) 呢?
- 原因时, 只有在需要扩容的时候, 才需要耗费扩容的代价。 如果不是即时性的东西, 完全可以在用户不操作时进行扩容操作, 这样用户 使用 哈希表时增删改查就是 O(1)
- 此外, 哈希表不会真的从 2 开始扩容, 初始时可以将哈希表定的大一点, 这样小数据时基本不会出发扩容机制。
经典哈希表的原理都是这样的, 但实际使用时的哈希表, 不同语言会有不同的优化, 比如桶中不是链表, 而且数组, 这些优化。
案例1 找出现次数最多的数
假设文件中有 40 亿个数字(无符号int), 要求找出出现次数最多的数字。 但内存限制为 1G。
如果直接使用哈希表实现, 假设一条记录占 8 字节, 最差的情况是每个数字都不相同, 此时如何实现哈希表存储, 内存会爆掉。
这个时候就可以利用哈希函数的离散性解决问题。 依次读取每一个数字, 计算他们的哈希值然后对哈希值求模。 比如对 100 求模, 在硬盘创建 100 个文件夹, 硬盘没有空间限制。 每个数字求哈希值再求模, 相同值的放入对应的文件夹中。 这样一来, 当遍历完 40 亿个数字后, 由于哈希函数的离散性, 将能保证 40 亿个数字是近乎均匀的分布在 100 个文件夹中的。 并且因为相同输入一定有相同输出, 所以相同的数字肯定在相同的文件夹中。 此时就可以在每个文件夹中, 利用哈希表求出出现次数最多的数字, 最终比较 100 个文件夹中各自产生的次数最多的数。 从而得出 40 亿个数字中, 哪个数字出现次数最大。
简单的说, 就是分而治之的思维, 但利用哈希函数能够保证这个 "分", "分" 的均匀。
案例2 设计 RandomPool 结构
【题目】: 设计一种结构, 在该结构中有如下三个功能
- insert(key): 将某个 key 加入到该结构, 做到不重复加入
- delete(key): 将原本在结构中的某个 key 移除
- getRandom(): 等概率随机返回结构中的任何一个 key
【要求】: Insert、delete和getRandom方法的时间复杂度都是 O(1)
【注意】: 看到题意时, 不要想着是让你自己实现哈希表的结构, 实际上这是一道使用哈希表的题。
单独的插入和删除并不难, 主要是有等概率随机返回一个 key。 key 的值是任意的, 所以我们需要使用一个数字标识它。 比如利用一个 index 来表示每一个 key, index 是连续的, 可以以加入时间次序作为他们的 index。 这样随机时, 只需要在 size 范围上获取一个随机数就可以了。 但又因为会删除 key, 删除 key 时会导致中间镂空, 所以删除的机制是将最后一个数填补到要删除的位置上。 这样就能保证 size 范围内都是有值的。
class Pool<K> {
HashMap<K, Integer> keyIndexMap; // key 到 index 的 map
HashMap<Integer, K> indexKeyMap; // index 到 key 的 map
int size; // index 就是插入的顺序, size 是池中剩余的 key 值, 同时也是 index 值
// 这一切都是为了 随机 服务的。
Pool(){}
void insert(K key) {
// 不插入重复值, 插入时给的是 key
if (!this.keyIndexMap.containsKey(key)) {
this.keyIndexMap.put(key, this.size);
this.indexKeyMap.put(this.size++, key);
}
}
void delete(K key) {
if (this.keyIndexMap.containsKey(key)) {
// 删除方式是, 将最后一个 key 填补到要删除的位置上》
int deleteIndex = this.keyIndexMap.get(key); // 或者要删除的位置 / 要填补的位置
int lastIndex = --this.size; // size 从 0 开始, 所以获取最后一个元素时, 下标要 -1
K lastKey = this.indexKeyMap.get(lastIndex);
// 将最后位置的值填补到要删除的位置上
this.keyIndexMap.put(lastKey, deleteIndex);
this.indexKeyMap.put(deleteIndex, lastKey);
// 添加完后删除两张表最后的 key 和 index
this.keyIndexMap.remove(key);
this.indexKeyMap.remove(lastIndex);
}
}
K getRandom() {
if (this.size == 0) {
return null;
}
// 创建两张表, 创建 size, 删除时将最后一个元素填补到删除元素为止上, 一切都是为了此刻随机时, 可以直接从 0~size-1 随机出一个数。
int randomIndex = (int) (Math.random() * this.size);
return this.indexKeyMap.get(randomIndex);
}
}案例3 布隆过滤器
比如有 40 亿个网站 url 是黑名单, 每次用户访问网站时, 都要知道这个网站是否是黑名单中的。 并且一个网站加入黑名单后不会删除掉, 即我们的需求只有增加和查询两个功能, 不会删除。 这种情形就可以使用布隆过滤器。
布隆过滤器, 其实就是利用哈希函数求取每一个 url 的哈希值, 然后求模得到一个下标, 这个下标所在位置只会是 0/1, 而存储的方式使用的是位图。 即一位代表一个信息。 普通结构存储时, 至少都是一个字节(8位)。 所以使用位图能够节省空间。
布隆过滤器一定会有失误率, 这是由哈希函数决定的, 因为哈希函数会有碰撞, 而你使用布隆过滤器的情况正是因为数据量大。 数据量大, 要想要节省空间, 所以碰撞率就会提高。 失误有两种:
- 网站是黑名单, 但识别为白名单。 布隆过滤器不可能出现这种失误, 因为一个 url 经过哈希函数后, 对应的位图一定值为 true
- 网站是白名单, 误识别为黑名单。 布隆过滤器只会有这种失误。 因为数据量大, 位图空间小, 所以存在某个白名单的 url 计算出来的哈希值求模后, 对应位置的下标是 true。
位图
先看看位图的实现:
- 每一位都是一个信息, 但我们没有 "位" 数组, 我们有的只有普通类型的数组。 所以我们是利用普通类型数组实现位图
- 此时需要实现的就是, 给你一个位图的下标, 你如何在普通类型数组中找到该位的信息
- 同理, 给你一个位图的下标, 你如何修改它的值
int[] arr = new int[10]; // 32bit * 10 这个长度为10的int数组, 我们会将其当成长度为 320 的位图
int i = 178; // 现在有一个位图的下标 178
// 要如何查询和修改对应位上的数据?
// 需要两个值, 这个 "位" , 在 arr 数组中的第几个元素中
int numIndex = 178 / 32; // arr 数组一个元素里面有 32 位, 所以 numIndex 就是所在 arr 数组下标
// 找到在那个元素里面, 那么他是在 32 位中的第几位呢?
int bitIndex = 178 % 32; // 通过模运算就可以得出第几位
// 有了这两个信息后, 就可以查询对应位的值了
// 首先, 取出第 numIndex 个元素, 因为值在该元素中, 然后右移 bitIndex 位, 此时最右侧的值就是我们要的信息了, 将它与 1 & 一下, 就知道这个位上的值是 0 是 1 了
int val = ( (arr[numIndex] >> bitIndex) & 1 )
// 修改位上的值, 如果要改成 1, 也就是要让其他位保持不变, 只有对应位始终为 1, 此时可以使用 | 运算
// | 运算, 任意值 | 1 = 1, 任意值 | 0 = 原值。 所以我们要将对应位上的值改为 1, 其他位上的值改为 0
arr[numIndex] = arr[numIndex] | (1 << bitIndex); // 先将 1 移到对应位上, 此时然后 | 上对应元素, 这样就实现了只有对应值变成 1, 其他位的值都是原值
// 同理, 要将位上信息该位 1, 可以使用 & 运算, 然后只让该位的值为 0
arr[numIndex] = arr[numIndex] & (~ (1 << bitIndex))布隆过滤器
【失误率分析】:
- 布隆过滤器的失误率有两个因素: 样本量 n, 位图大小 m
- 位图大小 m。 求出哈希值后, 需要将哈希值映射到 m 上
- 样本量 n, 单个样本具体的长度是无所谓的, 因为哈希算法不限制输入范围。
- 假设 n 不变, 如果位图太小, 那么位图上的格子很容易全被描黑。 (格子表示某一位, 描黑表示该值为黑名单的值)
- 这样当非黑名单的 url 映射到位图上, 很容易掉入被描黑的格子中, 失误率就会高
- 假设 m 不变, n 太大, 同样失误率也容易高。
【步骤】:
- 利用 k 个哈希生成器, 对每一个 url 对计算出对应的哈希值, 然后对位图大小 m 求模, 得出多个位图下标
- 当查询时, 同样会利用 k 个哈希生成器处理 url, 然后求模, 最终得到多个下标, 查询位图上对应下标是否描黑
- 虽然使用了多个哈希生成器, 但如果 url 是黑名单, 那么对应的多个格子, 肯定都是被描黑的
- 但如果 url 是白名单时, 出现误判时, 大多数情况下会是一些被描黑, 一些没被描黑, 小概率出现全被描黑的情况
- 所以使用多个哈希生成器时, 可以控制失误率
【控制失误率】:
- 我们能改变的参数有两个, 一个是 k, 即选用多少个哈希生成器, 一个是 m, 即位图定义多大。
- 首先, 只有 m 变化时, 当 m 增大时, 失误率会是下降的, 并且曲线会是反过来的 log 函数曲线 ╰
- 然后, 只有 k 固定时, 对应的失误率曲线应该是先减后增的。 后面会增加是由于, 当你使用太多哈希生成器时, 每一个 url 会生成 k 个格子, k 变大时, 位图很容易被填满, 所以失误率后续会上升。
n 是样本量, p 是失误率, m 是位图大小, k 是哈希生成器数量。 他们关系如下:
一致性哈希原理
分布式存储时, 一个机器存储一部分内容, 比如现在有三台机器, 各自存储 1/3 的用户内容。 (这里考虑的是底层数据存储, 而不是逻辑层, 比如代码如何查询)
- 现在假设某位用户要查询它的年龄, 那么逻辑服务器查询时, 需要先确定这个用户的数据存储在哪一台机器上。
- 操作是这样的, 在存储用户时, 将用户的身份证作为 key, 然后经过哈希函数计算出哈希值, 然后对 3 求模, 这样就能确定这个用户的数据存储在哪台机器上
- 逻辑服务器需要查询数据时, 再次以该用户的身份证作为 key, 求哈希求模后得出它在那个机器上, 然后再在对应机器上进行查询操作。
- key 的选取要保证种类繁多, 这样哈希函数才能均匀的将数据平均划分到三台服务器上, 保证三台服务器各自的中高频中频低频用户都有, 这样才能保证负载均衡。
- 假如选取的 key 是民族, 那么存储用户时, 因为 9 成用户都是汉族, 所以这 9 成用户最后都会存储在一台机器上。 当用户查询时, 全部都会到这个机器上查询, 这样就不负载均衡了
- 极端点, 如果 key 是性别, 那么用户的数据只会存储在两台机器上, 另一台机器完全不会存储数据。
上面的场景看起来很好, 但有一个问题, 如果扩展业务, 需要增加分布式存储的机器时, 上面方式就需要全所有数据重新进行一次求哈希求模。 因为机器数量增多, 而我们计算哈希后又会对机器数求模, 所以一旦改变机器数, 所以数据都需要重新求取哈希值。 一次性哈希就是解决这个问题的, 一次性哈希不需要求模。
一致性哈希
- 对一个 key 计算哈希后得到的哈希值, 是一个非常大的范围。 把这个范围看成一个环(即最小值与最大值相连)。
- 首先, 我们选取用户的身份证作为 key, 对所有用户求取哈希值后, 我们能确保最终值是均匀的分别在这个环上的。
- 然后, 分布式存储, 其实就是每台机器各自存储环上的一部分数据, 想要负载均衡, 就是每台机器负责的环的范围一样大, 即一个环被所有机器均分。
- 假设现在有三台机器, 三台机器肯定有自己的唯一值, 比如 IP, 或者 MAC码, 根据这三个值求出对应的哈希值, 假设这三个哈希值落在环上的位置刚好均分整个环。
- 此时环被均分成了三份, 当查询一个用户的数据时, 首先计算出该用户的哈希值, 然后查看该哈希值在哪个范围, 从而确定这个用户存储在哪台机器上。
- 上面的实现有一个问题, 首先就是只有 3 台机器的话, 求取机器的哈希值时无法保证均分, 因为只求了三个哈希。 (哈希的特性得数据量多时, 看起来才是离散的)
- 也就是说, 无法保证每台机器负责的环的范围一样多, 这样的话就无法实现负载均衡
- 其次, 退一步讲, 就算三台机器负责的环的区域一样多, 当增加一台机器时, 对新机器求取的哈希值, 必定会落在某台机器负责的范围上
- 比如刚好落在机器1负责的范围上, 那么原本机器1的环范围, 就变分成了两部分, 此时只需要将其中属于新机器的数据拷贝到新机器上就实现了数据的移动。
- 这样的数据移动代价是很少的, 但问题还是负载均衡, 因为机器2和机器3负责的依旧是 1/3 的环, 但机器1和新机器一共才负责 1/3 的环。
总的来说, 不求模的解决方案是: 将哈希值的范围看成环, 然后求取机器的哈希值确定这台机器负责的环范围(抢点), 即这个机器存储哪些数据。 这种方式解决了数据迁移代价大的问题 —— 当你增加或减少机器时, 只需要移动一部分数据。 但它同时存储新的问题:
- 机器数量少时, 如何保证均分环?
- 增加或减少机器时, 如何保证负载均衡?
解决方法: 虚拟节点技术
现在有三台机器, 假设每台机器都分配 1000 个字符串, 这些字符串就是虚拟节点
之前我们是直接对机器的 IP 或者 MAC值求哈希, 即是机器自己去"枪环",
但现在我们用机器的虚拟节点求哈希, 这样一来, 因为有 3000 个虚拟节点, 所以可以保证求出后的哈希值是均匀分配在环上的
而每台机器都负责 1000 个虚拟节点, 所以能保证每个机器均分环。
对于虚拟节点, 改变数据位置时, 虚拟节点要如何正确找到位置?
这个其实很简单, 假设虚拟节点1(位于机器1)的数据要转移给虚拟节点2(位于机器2), 那么当机器1把对应的数据转移给机器2后,
对于虚拟节点, 只需要改变他们查找的地址就可以了。 因为数据在环上的位置是固定的, 一个数据计算出哈希值后, 发现这个哈希值是在虚拟节点1上面的
于是就去虚拟节点1上找数据, 但虚拟节点1上的数据已经转给了虚拟节点2, 所以只需要简单的让虚拟节点1指向虚拟节点2就可以了, 这样就会到虚拟节点2上面找到数据。
又要如何保证增加或减少机器时, 负载均衡呢?
增加机器时, 他也创建 1000 个虚拟节点, 这 1000 个节点计算出哈希值后, 对应到环上时同样是均分的。
当新的虚拟节点对应到环上后, 由于是均分的, 所以之前三个机器都会各自迁移一部分数据到新机器上。
这样一来, 每个机器控制相同数量的虚拟节点, 而虚拟节点足够多, 保证了他们能够均匀的分布在环上, 从而实现了每个机器负责的环面积是相同的(负载均衡)
使用了虚拟节点后, 不仅仅可以实现负载均衡, 还可以实现管理负载
比如机器1性能强, 机器3性能弱, 那就让机器1负责2000个虚拟节点, 机器3负责500个虚拟节点。
通过控制机器负责的虚拟节点数量, 从而实现负载的管理。
底层分布式数据库的底层原理, 全部都是“虚拟节点技术”, 这也是谷歌改变世界技术的三驾马车之一。 该技术出自论文 《一致性哈希和随机哈希函数：负载均衡的比较》