散列表 Hash Table

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。
当按照键值查询元素时，用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。

散列函数和哈希算法

1. 散列函数 散列函数，顾名思义，它是一个函数。我们可以把它定义成 hash(key)，其中 key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。

该如何构造散列函数呢？主要有三大要求：

• 散列函数计算得到的散列值是一个非负整数；(数组下标是一个非负整数)
• 如果 key1 = key2，那 hash(key1) == hash(key2)；
• 如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)，换言之，不存在hash冲突。
  • 要想找到一个不同的 key 对应的散列值都不一样的散列函数，几乎是不可能的

2. 哈希算法 将任意长度的二进制值串映射为 固定长度 的二进制值串，这个映射的规则就是 哈希算法，而通过原始数据映射之后得到的二进制值串就是 哈希值。

一个优秀的哈希算法，必须同时满足如下条件：

• 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）；
• 对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同；
• 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小；
• 希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。

哈希算法的应用：

• 散列函数：散列函数的要求并没有哈希算法那么苛刻：
  • 并不关心是否能反向解密
  • 并不要求哈希值的长度固定
  • 更加关注散列后的值是否能平均分布
• 安全加密：例如，不存储明文密码，只存储经过hash处理后的密码
  • 为了防范字典攻击，我们可以引入一个盐（salt），跟用户的密码组合在一起，增加密码的复杂度。
  • 使用SHA算法，因为MD5算法已经被破解了。
• 唯一标识：使用hash值来唯一标识一张图片。从图片的二进制码串开头取 100 个字节，从中间取 100 个字节，从最后再取 100 个字节，然后将这 300 个字节放到一块，通过哈希算法（比如 MD5），得到一个哈希字符串，用它作为图片的唯一标识。
• 数据校验：给下载的文件，指定一个hash值，以校验是否完整。
• 负载均衡：
  • 通过哈希算法，对客户端 IP 地址或者会话 ID 计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。
  • 这样，我们就可以把同一个 IP 过来的所有请求，都路由到同一个后端服务器上。
• 数据分片
  • 我们可以先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度。
  • 分片的过程：
    • 假设有n台机器，我们先计算关键词的hash值，然后再跟 n 取模，最终得到的值，就是应该被分配到的机器编号。
  • 这就是 MapReduce 的基本设计思想。
• 分布式存储
  • 现在互联网面对的都是海量的数据、海量的用户。我们为了提高数据的读取、写入能力，一般都采用分布式的方式来存储数据
  • 该如何决定将哪个数据放到哪个机器上呢？我们可以借用前面数据分片的思想，即通过哈希算法对数据取哈希值，然后对机器个数取模，这个最终值就是应该存储的缓存机器编号。
  • 但是，如果数据增多，原来的 10 个机器已经无法承受了，我们就需要扩容了，比如扩到 11 个机器，这时候麻烦就来了。
    • 所有的数据都要重新计算哈希值，然后重新搬移到正确的机器上。
  • 我们需要一种方法，使得在新加入一个机器后，并不需要做大量的数据搬移。这时候，一致性哈希算法 就要登场了。

散列冲突

0. 装载因子

• 为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子（load factor）来表示空位的多少。
• 计算公式： 散列表的装载因子=填入表中的元素个数/散列表的长度
• 装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

1. 开放寻址法 如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。那如何重新探测新的位置呢？

• 线性探测
  • 插入数据: 如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。
  • 查找元素: 我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。
    • 如果相等，则说明就是我们要找的元素；
    • 否则就顺序往后依次查找
    • 如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中。
  • 删除元素:
    • 将删除的元素，特殊标记为 deleted。当线性探测查找的时候，遇到标记为 deleted 的空间，并不是停下来，而是继续往下探测。
• 二次探测
  • 所谓二次探测，跟线性探测很像，
    • 线性探测每次探测的步长是 1，那它探测的下标序列就是 hash(key)+0，hash(key)+1，hash(key)+2……
    • 而二次探测探测的步长就变成了原来的“二次方”，也就是说，它探测的下标序列就是 hash(key)+0，hash(key)+1^2，hash(key)+2^2……
• 双重散列
  • 使用一组散列函数 hash1(key)，hash2(key)，hash3(key)……
    • 我们先用第一个散列函数，如果计算得到的存储位置已经被占用，再用第二个散列函数，依次类推，直到找到空闲的存储位置。
• 当数据量比较小、装载因子小的时候，适合采用开放寻址法，因为开放寻址法比链表法更浪费内存。但是开放寻址法更有利于序列化。

2. 链表法 在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

• 插入的时间复杂度：当插入的时候，我们只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，所以插入的时间复杂度是 O(1)
• 查找、删除的时间复杂度：跟链表的长度 k 成正比，也就是 O(k)。
  • 对于散列比较均匀的散列函数来说，理论上讲，k=n/m，其中 n 表示散列中数据的个数，m 表示散列表中“槽”的个数。

动态扩容

对于没有频繁插入和删除的静态数据集合来说，我们很容易根据数据的特点、分布等，设计出完美的、极少冲突的散列函数，因为毕竟之前数据都是已知的。

对于动态散列表来说，数据集合是频繁变动的，我们事先无法预估将要加入的数据个数，所以我们也无法事先申请一个足够大的散列表。随着数据慢慢加入，装载因子就会慢慢变大。当装载因子大到一定程度之后，散列冲突就会变得不可接受。

这个时候就要使用“动态扩容”技术了。

• 数据搬运：相对于数组的扩容，散列表扩容时的数据搬移操作要复杂很多。因为散列表的大小变了，数据的存储位置也变了，需要通过散列函数重新计算每个数据的存储位置。
• 一次性扩容：当装载因子已经到达阈值，需要先进行扩容，再插入数据。这个时候，插入数据就会变得很慢，甚至会无法接受。
• 分批扩容：
  • 当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表中。
  • 当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。
  • 每次插入一个数据到散列表，我们都重复上面的过程。
  • 经过多次插入操作之后，老的散列表中的数据就一点一点全部搬移到新散列表中了。
• 分批扩容时，如何查找
  • 先从新散列表中查找，如果没有找到，再去老的散列表中查找。

对于动态散列表，随着数据的删除，散列表中的数据会越来越少，空闲空间会越来越多。如果我们对空间消耗非常敏感，我们可以在装载因子小于某个值之后，启动“动态缩容”。

上一篇 « B树 下一篇 » 位图