什么是哈希算法？

2024-02-23 01:03:18 阅读 0

下面分享一下鹅厂WXG开发工程师对Hash的一些理解。本文梳理了完美Hash的概念，通过Hash的构造步骤了解了它是如何解决Hash冲突的，并对哈希表和完美Hash表进行了比较。下面介绍常见的Hash和Hash函数以及它们在不同场景下的应用。

哈希函数（英语：Hash），也称为散列算法、杂凑函数，是一种从任何种类的数据中创建小型数字“指纹”的方法。哈希函数将消息或数据压缩成摘要，使数据量更小，并固定数据的格式。该函数对数据进行打乱，以重新创建称为哈希值（哈希、哈希码、哈希和或）的指纹。哈希值通常由随机字母和数字组成的短字符串表示。

哈希函数是一个单射函数，它将集合S转换为定长、不可逆的集合U。它的值一般是数字和字母的组合。 Hash函数的输入空间无限，但输出空间有限。这意味着Hash函数肯定会产生碰撞，而一个好的Hash函数可以显着降低碰撞的概率。哈希函数一般具有以下特点：

一致性。 Hash函数可以接受任意大小的数据并输出固定长度的哈希值，并且输出不同值的概率应尽可能一致。例如，无论原始数据有多大，计算出的哈希值始终是128位。雪崩效应。即使原始数据中只修改了一个字节，得到的哈希值也会发生巨大的变化。单向。只能从原始数据计算出哈希值，但不能从哈希值计算出原始数据。所以哈希算法不是加解密算法。加密和解密是可逆的，但哈希算法是不可逆的。避免冲突。几乎不可能找到与当前计算的数据具有相同哈希值的数据，因此哈希函数可以保证数据的唯一性。当Hash函数保证不同值出现的概率一致时，碰撞的概率只有2^-128。因为不同Key的碰撞概率很小，所以在某些情况下我们可以直接使用较短的Hash值来代替较长的原始数据存储。

一致性hash算法应用_一致性hash代码_一致性哈希代码

哈希函数

常见的哈希函数有：

、常用Hash函数的性能统计：

一致性哈希代码_一致性hash代码_一致性hash算法应用

常见用法：

哈希表：哈希算法用于将键均匀地映射到不同的位置。访问单个key时，平均时间复杂度可以达到O(1)，加快访问速度。

安全哈希函数

安全哈希函数（或加密哈希函数）是一种优秀的哈希函数。通过Hash值猜出Key是不可能（或很难）的。更准确的说，安全的Hash必须满足防碰撞和不可逆两个条件：不能通过统计方法对哈希值进行逆向，不能通过算法层进行逆向。常见的安全哈希算法包括：

SHA0、SHA1 和 MD5 算法被认为是不安全的并且存在已知的漏洞。不要使用这些不安全的哈希函数进行签名。

常见用法：

安全哈希函数广泛应用于数字签名技术：对原文进行哈希处理后，用私钥对哈希结果进行签名，以防止原文泄露或被修改；工作量证明：例如，加密货币的挖矿是使用给定值计算的。合格的哈希输入；文件ID：网站下载地址旁边往往会提供文件的MD5或SHA-1，以确保下载的文件完整且未被删减。

具有全局哈希（hash）

全局哈希解决了确定性哈希算法无法应对特殊输入的问题。在链中，假设 m = size，考虑我们有一个输入集 S 和一个哈希函数 H，其中 H = H' % m。如果攻击者知道哈希函数，就很容易构造集合S，使得集合中每个元素的大小和哈希值相同，就会退化为链表。最坏的情况下，搜索的时间复杂度变成O(n)，插入n个元素需要的时间复杂度为O(n2)，所以也称为攻击。

全局哈希解决的问题是，对于精心构造的输入，碰撞率仍然是 1/m。一个简单的想法就是随机选择一个Hash函数，而不是每次操作都选择一个，而是在输入之前选择一个Hash函数，之后的所有操作都是基于这个Hash函数。

当然，H不是随便定义的。具体地，从|H|中随机选择一个Hash函数。哈希函数 H 作为所有键的哈希函数。 H中的所有哈希函数H'对于不等关键字x和y，使H'(x)和H'(y)值相等的函数H'的数量等于|H| /m，此时冲突概率为1/m。

完善的哈希函数

传统的分支预测开销总是与内存进行比较。最坏的时间复杂度是O(n)。有这样一个Hash函数：完美的Hash函数（Hash，PHF），在最坏的情况下可以达到O(1)。）时间复杂度。当然，鱼与熊掌不可兼得。 Hash需要静态输入集合，而要查找的key必须存在于静态输入集合中，导致使用场景有限。它有几个特点：

大多数完美的哈希要求输入键的集合是已知的，并用于提前构建数据结构；构造算法比较复杂，大多数情况下需要较大的内存。特别是时间复杂度高，建立索引需要很长时间。，为海量密钥构建完美的哈希可能会失败；完美Hash的实现不仅仅是一个Hash函数，而是多个普通Hash函数和数据结构算法的组合，这意味着需要额外的空间来存储Hash冲突信息。

虽然它有一些缺点，但在一些场景如汉语拼音映射、词典、程序中预定义的映射关系等都有其应用。

Hash 对于给定的集合 S，S 中的所有 Key 都可以映射到整数 [0, m)，其中 m >= |S|。当m=|S|时，称为最小完美哈希函数（Hash，MPHF）。也就是说，作为一种特例，如果完美Hash可以将N个键映射到0到N-1的整数，那么它就可以称为最小完美Hash函数。

此外，如果哈希后给出的键的顺序不变，则称为完美的保序哈希函数。如果一个哈希函数在给定区域内冲突次数不超过t次，则该哈希函数称为t完美哈希函数。

一致性hash代码_一致性hash算法应用_一致性哈希代码

目前开源的Hash库包括：

下面将讨论FCH和CHD如何巧妙地解决Hash冲突并达到最差的O(1)时间复杂度。

Hash首先需要离线构建，获取Hash冲突信息并离线保存。当需要查询时，利用之前生成的信息计算出唯一的整数Hash值。

在描述算法之前，我们假设：

对于已知大小 n = |S| 的输入集 S，已知负载因子 alpha 和参数 c，表数 = n * alpha，桶数 m = cn / (log2 n + 1)。一般来说，c在2-8左右，保证每个有适当数量的key，而不会让太多空着。最终所有键都将映射到 [0, ) 中的整数。当α=1，=n时，就是MPHF。

FCH

A for Hash 是 Fox、Chen 和 Heath 发明的一种算法，用于生成完美的 Hash。 FCH是Hash的一个相当经典的实现。后续的很多算法都是受到FCH算法的启发。

FCH是一个基于两级哈希表的完美哈希函数：

通过一级哈希将数据映射到T空间，然后随机选择一个新的哈希函数将冲突数据映射到S空间，S空间的大小m为冲突数据的平方（例如， T2中有3个数字冲突，则映射到m=9的S2空间，m是避免桶内Hash冲突的参数）。这时候就很容易找到哈希函数来避免冲突（这个避免冲突的过程称为or）。最坏情况下所需的存储空间为O(n2)，但只要适当选择哈希函数以减少一级哈希时的冲突，就可以使预期的存储空间为O(n)。

构建FCH需要三个步骤：

为了将 60% 的密钥分配到 30% 的桶中，将 n 个密钥分为两组，S1 和 S2。 S1称为稠密集，键的数量保持在大约0.6 * n。 S2 是集合和密钥。数量大概约为 0.4 * n。同时，所有桶被分为两部分B1和B2。 B1的数量为p2=0.3*m，称为密度，B2的数量为0.7*m，称为密度。使用普通的Hash函数如/将S1通过H1映射到B1，同样的方式将S2通过H2映射到B2。

用数学语言描述一下：

一致性hash算法应用_一致性hash代码_一致性哈希代码

在这个阶段，所有桶按照桶内冲突的数量进行排序，冲突数量最多的桶被放置在最前面。

该阶段会依次处理每个中的冲突，并尝试为每个key分配唯一的Hash值。经过上一阶段的排序后，本阶段将优先考虑冲突最多的桶。对于每个桶，尝试参数di，bi，并将哈希值（x，di，bi）=（h（x，s2 + b1）+ di）mod分配给桶中的每个键。该值在[0, )时间之间，其中s2为全局随机种子，bi为单个比特，di为从0开始递增的整数。如果桶中的Hash值与之前计算的Hash值冲突，则更改bi或di直到Hash值不出现为止。冲突（为了加快查找di的速度，原论文中提出了辅助数据结构和压缩方法，有兴趣的可以参考论文）。

一致性hash算法应用_一致性哈希代码_一致性hash代码

处理完冲突后，我们最终可以得到m个参数bi，di存储在P数组中，大约只占用m * ((log2 n) + 1) = cn位（这只是理论结果，如何存储bi和di不在我们讨论的范围内），即每个key只占用c位。

查询时：对于给定的key，计算一级Hash，得到桶号。通过桶的bi、di和全局s2参数计算二级哈希。即完成一次搜索，任意key都可以找到查询步骤。一切都是相同的，没有循环，即所有步骤都是确定性的 O(1)。请注意，无法确定密钥是否存在。

一致性hash算法应用_一致性哈希代码_一致性hash代码

在FCH中，c越大，构建速度越快，但空间利用率越低。特别是，FCH搜索MPHF需要花费巨大的时间：当c = 3时，1亿条数据需要一个多小时才能生成，因此它并不是一个实用的算法。

冠心病

为了解决FCH构建速度太慢的问题，基于FCH思想的CHD应运而生，一种简单的Hash算法，支持MPHF，空间利用率较高，但速度较慢。

主要区别：使用一般的Hash函数计算每个key的三个Hash值：h、h0、h1，h用来表示桶号，h0和h1用来计算最终的，定义为 = (h0 + ( h1 * d1) + d0) mod 。

与 FCH 一样，CHD 也分为三个阶段：

Stage不需要像FCH那样分成两组，而是直接映射到一组。

用c++来描述：

buckets.resize(m);
for (auto key : keys) {
  auto [h, h0, h1] = hash(key);
  buckets[h].hash = h;
  buckets[h].keys.push_back(make_tuple(h0, h1));
}

与 FCH 相同。

sort(buckets.begin(), buckets.end(), [](auto &lhs, auto &rhs){
  return lhs.keys.size() > rhs.keys.size();
});

（也称为）

该阶段还处理每个桶中的冲突。不同的是，函数发生了变化：为每个桶初始化一个pilot，其中pilot = d0 * + d1，并使用公式计算key的Hash值。当发生冲突时，Pilot加1（相当于d1加1，此时的结果会发生明显变化）重新计算，直到桶中所有key都不冲突为止。

bool_vector position_used, position_used_in_bucket;
vector p; // 结果数组
position_used.resize(table_size);
position_used_in_bucket.resize(buckets[0].keys.size());
p.resize(m);
for (auto &bucket : buckets) {
  if (bucket.keys.size() == 0) continue;
  // 单个桶 pilot = d0 * table_size + d1
  int d0 = 0;
  int d1 = 0;
  while(true) {
    bool ok = true;
    position_used_in_bucket.clear();
    for (auto [h0, h1] : bucket.keys) {
      uint64 position = (h0 + (h1 * d1) + d0) % table_size;
      if (position_used[position]) {
        // hash 结果冲突，换一个 pilot
        ok = false;
        break;
      }
      if (position_used_in_bucket[position]) {
        // 桶内 hash 结果冲突，换一个 pilot
        ok = false;
        break;
      }
      position_used_in_bucket[position] = true;
    }
    if (ok) {
      // 单个桶处理完毕
      position_used.union(position_used_in_bucket);
      // pilot 存到 p 数组中
      p[bucket.h] = d0 * table_size + d1;
      break;
    }
    d1++;
    if (d1 >= table_size) {
      d1 = 0;
      d0++;
      if (d0 > table_size) {
        // 构建失败，找不到一个可用的 pilot
        throw ...
      }
    }
  }
}

最终得到的m个导频存储在P数组中。

查询时：对于给定的key，使用固定的Hash函数计算h、h0、h1，根据P[h]得到pilot和d0、d1，使用Yi得到Hash值，即完成一次查找（至少 4 次除法或求余运算，h < m)

auto [h, h0, h1] = hash(key);
auto pilot = p[h];
auto d0 = pilot / table_size;
auto d1 = pilot % table_size;
return (h0 + (h1 * d1) + d0) % table_size;

在结果集P中，导频往往非常小，有压缩的空间。在作者的论文中，为了压缩P数组的大小，使用了FN，可以压缩到2.08 bit/key的开销。你自己的实现可以直接使用位（又名）压缩实现起来更简单。

压缩：给定一系列整数S，已知S中最大的整数x需要用y位表示。我们可以用固定的 y 位来表示所有整数，而不牺牲精度和访问时间。

CHD算法相对简单，并且有不同语言的实现，包括Rust语言。 Go语言实现。

CHD虽然实现简单，但是包含大量的除法和余数计算，效率不是很高，耗时也太长。最近有一篇文章提出了一种提高FCH上构建时间和空间利用率的方法，作者也提供了源码供参考。

设计思想与FCH类似，只不过定义变成(x, Pilot) = (h(x, s) xor h(pilot, s)) mod，其中h是普通Hash函数，x是key， s 是全局种子。。与FCH相比，所有key的Hash h(x, s)可以提前计算出来，节省了构建时间。该压缩方法效果非常好，耗时可以达到FCH级别。

与FCH相同

采用新的公式计算，得到n个导频。根据公式定义可以发现，大部分导频都是比较小的值。作者还引入了一种Front-Back，将结果集的前30%分割成前集，然后（1-30%）分割成后集，代价是运行时多了一次分支判断。

由于前组的桶最先处理冲突，因此冲突数量较少，大多数导频都比后组的小，压缩率较高。将Front和Back集中的导频编码后，称为-。

查询时根据ID确定是查询前集还是后集的试点。不考虑解压过程，只需要两次除法或求余运算。

当然，你也可以在这里牺牲一部分空间，不使用Front-Back来达到更快的查询速度。根据不同的方法，可以达到时间和空间的平衡：

一致性hash算法应用_一致性hash代码_一致性哈希代码

本质上，是根据给定的key获取value的地址。设计的核心主要在于：

空间开销：键和值是如何组织的？单个密钥需要多少额外空间来存储元信息？查询与插入：如何通过key计算value的地址？遇到冲突如何处理？区别在于如何处理冲突。除了常规读写外，还有只读，存储更小，性能更好。常规

每种语言都有内置的实现。除了使用不同的Hash函数之外，不同的实现对于Hash冲突的解决方案也不同：

F14&B16系列

F14&B16是使用SIMD技术的链式搜索。它为每个Key计算两个Hash值：H1和H2。 H1决定Key放在哪个桶中，H2用于处理桶内冲突。一般要求负载系数较高，以获得较高的空间利用率。同时通过SIMD指令对桶中的H2进行比较，一次比较14个key或者16个key。与H2相比，它可以支持动态插入，但搜索性能没有那么好。

有什么办法可以使用哈希吗？由于Hash已经映射到[0,)中的整数，所以不需要考虑key冲突处理，所以使用起来比较简单：

一致性hash代码_一致性hash算法应用_一致性哈希代码

Hash要求查询的key必须存在于输入集中。其他要求没那么严格。如果使用不在输入集中的密钥会发生什么情况？从CHD算法的流程分析，当输入未知的密钥时，可以认为返回的是一个随机的Index。如果我们需要确认key是否存在，我们需要保存原来的key，放到Index对应的Value中。查询完Index后，再次进行比较。确认key是否存在。

一般的用法是先离线生成map信息，然后读入其中，或者像rust-phf一样在编译时构建到二进制文件中，直接读取P数组。如果特别大，也可以通过mmap以只读方式加载到内存中。

测试设备：m1 Pro 32G，MacOS 12.4，clang 13.1.6。

比较对象：

测试场景：输入100万个随机不重复的变长字符串（平均长度8字节）作为key，value与key相同。随机化一切。

一致性hash算法应用_一致性哈希代码_一致性hash代码