为什么Jenkins one-at-a-time hash function中没有溢出检查？

Question

uint32_t jenkins_one_at_a_time_hash(const uint8_t* key, size_t length) {
  size_t i = 0;
  uint32_t hash = 0;
  while (i != length) {
    hash += key[i++];
    hash += hash << 10;
    hash ^= hash >> 6;
  }
  hash += hash << 3;
  hash ^= hash >> 11;
  hash += hash << 15;
  return hash;
}

来源：https://en.wikipedia.org/wiki/Jenkins_hash_function

hash<<10与hash相加时，如果字符串长度过大，可能会溢出。在使用多项式哈希函数对字符串进行哈希处理时，我们在每次迭代中取 mod p 值（p 是 uint32_t 范围内的一个大素数），并返回 hash % hash_table_length.但是在这个算法中，我们为什么不取hash = (hash + (hash<<10)) % p来防止溢出呢？我们如何确保返回的 hash 值保持在散列 table 长度内？

Answer 1

一次一个散列旨在将一串字节作为输入，然后输出一个（大致）均匀分布的 32 位值。重要的是，这意味着如果您想使用散列函数将键分布到散列 table 中，您将需要执行一些辅助数学运算以将 32 位散列转换为 table 索引，因为哈希函数本身并不是为了将其输出限制在较少数量的槽中而设计的。因此，例如，如果你想用它来分发密钥，你可以 mod table 个插槽的结果。

上一段中的推理基本上可以归结为“正如最初所写的那样，哈希函数不会尝试适应少量的槽”。但这里也有一个更深层次的问题：为什么哈希函数不对处理整数溢出做出任何规定，为什么它不在每一步 mod 其内部值乘以素数？这与指导哈希函数的设计原则有关。 an article about building families of hash functions with certain desirable properties using invertible transformations. The idea is to build a hash of a long byte stream by incrementally applying invertible transforms that combine together the existing hash value and new bytes. Doing so has the useful property that if you’ve hashed byte streams X and Y and didn’t get a collision, then there’s a no chance of getting a collision if you append the same byte sequence to both X and Y. The specific operations used in the hash 中描述了一次一个散列，但是关于为什么的理由很微妙，并且依赖于这样一个事实，即添加移位并允许计算溢出对应于乘法 modulo 2³² 可逆值。从这个意义上说，这里有意没有 mods，因为由溢出计算的隐式 modulo 执行“正确的”modulo 以使所有步骤可逆。

这与多项式散列形成对比modulo 一些素数。你是正确的，当使用多项式哈希策略时，你需要注意整数溢出，因为你特别不希望这些隐式 mod 开始 - 毕竟，您mod差了一个不同的数字！但这特定于特定的哈希策略。有很多不同的方法来构建哈希函数，每种方法都使用不同的方法。

为什么Jenkins one-at-a-time hash function中没有溢出检查？

Why is there no overflow check in the Jenkins one-at-a-time hash function?

string

algorithm

hash

overflow

mod