时间戳

首页 > 解决方案 > 哈希表双重哈希

algorithm - 哈希表双重哈希

问题描述

我得到了两个散列函数，我应该使用它们来插入和删除表；

int hash1(int key)
{
    return (key % TABLESIZE);
}

int hash2(int key)
{
    return (key % PRIME) + 1;
}

我对如何使用它们感到困惑。

我是否：

  1. 先用hash1，如果槽位取返回值，用hash2？
  2. 我是否使用 hash1 然后将结果添加到 hash2 的输出中？
  3. 我是否使用 hash 的输出作为 hash2 的输入？

标签： algorithmdata-structureshashhashmaphashtable

解决方案

TLDR：bucket_selected = hash1(hash2(key))

hash1()是从键到桶的身份哈希（它将键折叠到表大小中）。如果表大小恰好是 2 的幂，它会有效地屏蔽掉一些低位，丢弃高位；例如，表大小为 256，有效返回键 & 255：最低有效 8 位。如果键不是，这将有点容易发生冲突：

  • 大部分是连续的数字——可能有一些小的间隙，这样它们大部分时间都干净地映射到连续的桶上，或者
  • 使用的低位非常随机，因此它们分散在桶中

如果表大小不是 2 的幂，理想情况下是素数，则高位有助于将密钥散布在桶中。冲突的可能性与随机数一样，但在计算机系统上，有时密钥中的不同位或多或少可能会发生变化（例如，double内存中的 s 由一个符号、许多尾数和许多指数位组成：如果你的数字具有相似的量级，它们之间的指数变化不大），或者存在基于二次幂边界的模式。例如，如果您将 4 个 ASCII 字符打包到一个uint32_t键中，则% table_sizetable_size 为 256 的哈希仅提取其中一个字符作为哈希值。如果表大小改为 257，则更改任何字符都会更改所选存储桶。

(key % PRIME) + 1如果表大小是素数，则接近于做hash1()，但为什么要加 1？有些语言确实从 1 开始索引它们的数组，这是我能想到的唯一充分理由，但是如果处理这样的语言，您可能也想hash1()添加 1。为了解释 的潜在用途hash2()，让我们先退后一步......

真正的通用哈希表实现需要能够创建不同大小的表 - 任何适合程序的 - 实际上，如果插入的元素多于它可以处理的数量，应用程序通常希望表“调整大小”或动态增长。因此，诸如散列函数之类的散列函数hash1将依赖于散列表实现或调用代码来告诉它当前表的大小。如果哈希函数可以独立于任何给定的哈希表实现来编写，通常会更方便，只需要密钥作为输入。许多散列函数所做的是将密钥散列为一定大小的数字，例如 auint32_t或uint64_t。显然，这意味着哈希值可能比哈希表中的桶数更多，所以一个%操作（或更快的按位-&如果 # buckets 是 2 的幂，则操作）然后用于将哈希值“折叠”回存储桶上。因此，一个好的哈希表实现通常接受一个哈希函数，生成例如uint32_toruint64_t输出，并在内部执行%or &。

在hash1- 的情况下可以使用：

  • 作为将密钥折叠到存储桶的身份哈希，或
  • 将散列值从另一个散列函数折叠到存储桶。

在第二种用法中，第二个哈希函数可以是hash2. hash2如果给定的密钥通常比使用的 PRIME 大得多，而 PRIME 又比存储桶的数量大得多，这可能是有意义的。为了解释为什么这是可取的，让我们再退一步......

假设您有 8 个桶和一个哈希函数，该函数以均匀的概率在 [0..10] 范围内生成一个数字：如果您%将哈希值放入表大小，哈希值 0..7 将映射到桶 0..7 , 并且哈希值 8..10 将映射到存储桶 0..2：存储桶 0..2 的碰撞键可能是其他存储桶的两倍。当哈希值的范围远大于桶的数量时，让一些桶%比其他桶多一次的意义相应地很小。或者，如果您说一个哈希函数输出 32 位数字（因此不同哈希值的数量是 2 的幂），那么%通过较小的 2 次幂将完全相同数量的哈希值映射到每个桶.

所以，让我们回到我之前的断言：hash2()的潜在用途实际上是这样使用它：

bucket_selected = hash1(hash2(key))

在上面的公式中 -hash1分布在桶中，但防止越界桶访问；为了合理地工作，hash2应该输出一个比桶数大得多的数字范围，但它根本不会做任何事情，除非键跨越的范围大于 PRIME，理想情况下它们跨越的范围比 PRIME 大得多，增加来自 hash2(key) 的哈希值在 1 和 PRIME 之间形成近乎均匀分布的几率。

推荐阅读