算法第三章

布隆过滤器

• 海量数据管理，在哈希表上再压缩数据，但会存在较低的失误率
  • 失误类型：宁可错杀三千不可错放一个，非存储数据小概率判断为存储数据

• bit位数组存储：eg. int数组每位存储0~31位bit数组

• 思想：准备k个哈希函数，哈希值取模bit数组大小m，每个键经过记录得到k个哈希值范围[0,m-1]，将bit数组k个哈希值的对应位置1。查表时，若是查询键中非全部哈希置位为1，则未被记录。

  • 若是k个值有重复，则仍然置1，多余的不变

  • 所有键共用一个bit数组

  • 在bit数组映射整型数组的值：n_bit/32(int范围)%32

• 布隆过滤器大小与失误率(要求)、样本数有关 - 小数向上取整
  • \(m = - \frac{n * ln^{p}}{({ln^{2})}^2}\)
• 哈希函数多少与布隆过滤器大小，样本数有关 - 小数向上取整
  • \(k={ln}^{2} * \frac{m}{n}\)
• 真实失误率
  • \(p_{real}={(1-{e}^{-\frac{n * k}{m}})}^k\)

一致性哈希

• 负载均衡结构：哈希key返回value，取哈希域模线性映射，均匀分布各个站点
  • 问题：范围改变时需要重新映射，迁移代价过高
• 一致性哈希结构：哈希key返回value， 不取模哈希域为环，根据哈希值分布在环上往后最近站点（二分查找往后最近站点）

  • 添加站点时，只需要在后站点往新站点进行数据迁移（删除站点时同理）

  • 问题①：当数据少量的时候无法保证负载均衡

  • 问题②：当添加 / 删除站点的时候可能无法保证负载均衡

    • 解决：使用虚拟节点技术

    • 将虚拟节点均匀分配给实际站点，数据哈希值分布在虚拟节点上

题目一：随时找到数据流的中位数

• 题目：有一个不断吐整数的数据流，假设有足够的空间来存储。设计一个MedianHolder结构，它可以随时取得之前吐出所有数的中位数。

• 要求：结构加入新数的复杂度为O(logⁿ)；取中位数的时间复杂度O(1)

• 思想：

  • 根据要求可以想到使用大小根堆来实现，中位数是在有序序列正中间，将数据流吐数分成两部分，元素个数相差不超过1，左边大根堆，右边小根堆

  • 进来的第一个数默认放在大根堆。之后进来的数先跟大根堆堆顶进行比较 - 若是比之小，则加入大根堆；若是比之大，则加入小根堆

  • 当大根堆与小根堆元素个数相差超过1时，多的堆弹出堆顶元素加入另一个堆

未完待续

初级> - 第三章 布隆过滤器、一致性哈希等相关问题' ref='nofollow'>算法<初级> - 第三章 布隆过滤器、一致性哈希等相关问题

原文：https://www.cnblogs.com/ymjun/p/12202547.html