0%

哈希

发表于 更新于 分类于

哈希问题

哈希函数

  • 定义: 给定一个对象, 返回一个值(一个对象只对应一个哈希值)
  • 性质:
    1. 哈希函数的输入域是无限大的
    2. 哈希函数的输出域是有穷的
    3. 当输入是固定的参数时, 输出也是固定的
    4. 当输入不一样, 输出可能一样(哈希冲突)
    5. 如果输入是很多不同的值, 输出将会在输出域上均匀的分布

哈希表

  • 操作:

    1. put(key, value)
    2. get(key)
    3. remove(key)

  • 原理:

    • put: 通过哈希函数得到哈希码, 然后哈希码对储存空间容量取余, 得到多少, 就把kv挂在那个空间上, 当哈希表的某个节点的元素数量超过一个定值, 我们就可以认为哈希表已满, 可以进行扩容(可以是成两倍扩容, 可以成N倍扩容), 然后重新计算所有元素的位置.
    • get: 通过key计算位置, 然后找到指定的元素, 返回.
    • remove: 通过key计算位置, 然后找到指定元素, 删除.

设计RandomPool结构

  • 题目: 设计一种结构, 在该结构中有如下三个功能:
    1. insert(key): 将某个key加入到该结构中, 做到不重复加入
    2. delete(key): 将原本在结构中的某个key移除
    3. getRandom(): 等概率随机返回结构中的任何一个key
  • 要求:
    • insert delete getRandom的时间复杂度都是O(1)
  • 代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    class RandomPool<T>
    {
        public RandomPool()
        {
            this.dic1 = new Dictionary<T, int>();
            this.dic2 = new Dictionary<int, T>();
            this.size = 0;
            this.random = new Random();
        }

        public void Insert(T key)
        {
            if (!this.dic1.ContainsKey(key))
            {
                this.dic1[key] = this.size;
                this.dic2[this.size] = key;
                this.size++;
            }
        }

        public T GetRandom()
        {
            if (this.size == 0)
            {
                return default(T);
            }
            int next = this.random.Next(this.size);
            return this.dic2[next];
        }

        public void Remove(T key)
        {
            if (this.dic1.ContainsKey(key))
            {
                this.size--;
                int val = this.dic1[key];
                this.dic1.Remove(key);
                this.dic1[this.dic2[this.size]] = val;
                this.dic2[val] = this.dic2[this.size];
                this.dic2.Remove(this.size);
            }
        }

        private Dictionary<T, int> dic1;
        private Dictionary<int, T> dic2;
        private int size;
        private Random random;
    }

布隆过滤器

  • 用途: 爬虫去重, 黑名单
  • 例: 黑名单
    1. 准备一个足够长的bit数组, 并初始化为0
    2. 准备K个哈希函数
    3. 对指定url计算K次哈希
    4. 将K个哈希值对bit数组长度取模, 得到的位置改为1
    5. 将所有的url重复上面的操作
    6. 当有新的url来到, 判断K个位置是否为1
    7. 只要有一个位不是1, 这个url就不在黑名单里
  • 说明:
    1. 失误率与哈希函数个数与数组长度有关
    2. 空间越大, 失误率越低
    3. 数组长度与原始数据量和要求失误率有关
  • 公式
    • 确定数组大小的公式(上取整): m = - (n * lnP )/((ln2)^2)
      • m: 数组要申请的空间
      • n: 样本量
      • P: 预期失误率
    • 确定哈希函数数量的公式(上取整): K = ln2 * (m / n)
      • K: 哈希函数的个数
      • m: 数组空间
      • n: 样本量
    • 真实失误率: P = (1 - e^(-(n*k)/m))^k
      • P: 真实失误率
      • n: 样本量
      • m: 数组空间
      • k: 哈希函数个数

一致性哈希

  • 假设有个服务器群, 这个服务器群已经运行了一段时间(产生了很多数据), 这个服务器处理请求是通过哈希函数来进行均衡负载的. 如果要扩容服务器数量, 那么已有的数据就需要全部重新计算哈希, 这样的代价会很大.
  • 解决上面的问题:
    1. 将机器的信息收集起来计算哈希
    2. 让请求的哈希值由小到大排序(最大值后面跟着最小值)形成一个环
    3. 让机器根据哈希值插入到环中, 每台机器只负责哈希值小于等于机器哈希值的请求
    4. 这样无论增加或是减少机器, 都只需要迁移一部分数据即可(即带操作服务器的位置到上一个节点位置的数据在增加和删除的服务器和下一个节点服务器直接交换即可)
  • 新问题:
    • 这样做以后, 服务器的请求会分布不均匀, 导致无法负载均衡
  • 解决方法: 虚拟节点技术 (一致性哈希技术)
    • 使用虚拟节点来分割请求形成的环(虚拟节点个数可以远大于服务器数量)
    • 建立真实服务器和虚拟节点的路由(服务器对应虚拟节点的个数必须相同)
    • 当增加或删除服务器的时候, 在环上增加或删除每台服务器对应节点个数的虚拟节点, 然后迁移数据
    • 此时增加服务器成本很小, 迁移数据也很小, 并且依然负载均衡