散列表和哈希算法

散列表

• 概念: 散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

• 散列冲突的解决办法:

  • 开放寻址法, 如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入
    • 线性探测, 从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止; 插入查找同数组一致, 但删除不能直接删掉元素, 只能标记deleted, 不然会使后续的查找算法失效
    • 二次探测, 二次探测探测的步长就变成了原来的“二次方”，也就是说，它探测的下标序列就是 hash(key)+0，hash(key)+12，hash(key)+2
    • 双重散列, 先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置
  • 链表法

• 装载因子, 散列表的装载因子=填入表中的元素个数/散列表的长度

  • 装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降
  • 装载因子越小, 会导致内存浪费严重

• 避免低效的扩容

  • 为了解决一次性扩容耗时过多的情况，我们可以将扩容操作穿插在插入操作的过程中，分批完成。当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表中。
  • 当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表，我们都重复上面的过程。经过多次插入操作之后，老的散列表中的数据就一点一点全部搬移到新散列表中了。这样没有了集中的一次性数据搬移，插入操作就都变得很快了。

• 散列表与链表的结合, 是增加一个双向链表来达到高效的操作, 如下实现的LRU原理
  • 下图中的hnext, 是节点串在散列表的拉链中
  • 查找, 删除, 添加操作均可通过散列表在O(1)时间复杂度找到元素, 然后通过双向链表在O(1)复杂度删除节点或是在尾部新增节点

哈希算法

• 概念: 将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值
• 哈希算法的要求:
  • 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）；
  • 对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同；
  • 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；
  • 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。
• 哈希算法的应用:
  • 安全加密 , 常用的安全加密哈希算法, MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）和 SHA（Secure Hash Algorithm，安全散列算法）, 还有DES（Data Encryption Standard，数据加密标准）、AES（Advanced Encryption Standard，高级加密标准）
  • 唯一标识 , 如在海量图库中搜索一张图是否存在, 可以从图片的二进制码串开头取 100 个字节，从中间取 100 个字节，从最后再取 100 个字节，然后将这 300 个字节放到一块，通过哈希算法（比如 MD5），得到一个哈希字符串，用它作为图片的唯一标识
  • 数据校验 , 如BT种子下载, 可以对文件块取哈希值, 再与种子中的哈希值对比, 确保文件没有被篡改
  • 散列函数
  • 负载均衡 , 通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号, 以实现一个会话粘滞（session sticky）的负载均衡算法
  • 数据分片 , 如统计每个关键词在日志中被搜索的次数, 可以将搜索关键词计算得到哈希值, 再对机器个数取模, 将每个搜索关键词的计算分布到各个机器中处理, 就是MapReduce的思想
  • 分布式 存储 , 一致性哈希算法, 假设我们有 k 个机器，数据的哈希值的范围是[0, MAX]。我们将整个范围划分成 m 个小区间（m 远大于 k），每个机器负责 m/k 个小区间。当有新机器加入的时候，我们就将某几个小区间的数据，从原来的机器中搬移到新的机器中。这样，既不用全部重新哈希、搬移数据，也保持了各个机器上数据数量的均衡。