C++ - 为什么boost :: hash_combine是组合哈希值的最佳方法？

Question

我在其他帖子中读到,这似乎是组合哈希值的最佳方式.有人可以打破这一点,并解释为什么这是最好的方法吗？

template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

编辑:另一个问题只是要求神奇的数字,但我想知道整个功能,而不仅仅是这一部分.

Answer 1

它是"最好的"是有争议的.

它"好",甚至"非常好",至少表面上看,很容易.

seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);

我们假设seed是先前的结果hasher或此算法.

^= 表示左边的位和右边的位都改变了结果的位.

hasher(v)被认为是一个不错的哈希v.但其余的是防御,以防它不是一个体面的哈希.

0x9e3779b9是32位值(可以扩展到64位,如果size_t是64位可以说),包含半0和半1.它基本上是0和1的随机序列,通过将特定的无理常数近似为基-2固定点值来完成.这有助于确保如果hasher返回错误值,我们的输出中仍会得到1s和0s的拖尾.

(seed<<6) + (seed>>2) 传入的种子有点混乱.

想象一下,0x常数不见了.想象一下,hasher 0x01000几乎每次v传入都会返回常量.现在,种子的每一位都在散列的下一次迭代中展开,在此期间它再次展开.

将seed ^= (seed<<6) + (seed>>2) 0x00001000成为0x00041400一个迭代后.然后0x00859500.重复操作时,任何设置位都会在输出位上"抹黑".最终,右和左位发生冲突,并且进位将设置位从"偶数位置"移动到"奇数位置".

当组合操作在种子操作上进行递归时,依赖于输入种子的值的比特以相对快的速度和复杂的方式增长.添加原因带来更多东西.该0x常数增加了大量的伪随机比特,使枯燥的哈希值进行组合后占据小于哈希空间的几位多.

由于添加(结合哈希"dog"并"god"给出不同的结果),它是不对称的,它处理无聊的哈希值(将字符映射到它们的ascii值,这只涉及使少数几个位错误).并且,它相当快.

在其他情况下,密码强的较慢散列组合可能更好.我天真地认为,使移位成为偶数和奇数移位的组合可能是一个好主意(但可能是加法,即使奇数位中的位移动,也不会产生问题:在3次迭代后,传入的单独种子位将发生冲突并添加并导致进位).

这种分析的缺点是,只有一个错误才能使哈希函数变得非常糟糕.指出所有好事并没有多大帮助.现在另一件让它变得更好的事情是,它在一个开源的存储库中是相当有名的,我没有听到有人指出它为什么是坏的.

Answer 2

这不是最好的,令我惊讶的是它甚至都不是特别好. 图1:使用boost :: hash_combine将两个随机32位数之一中的单个位变化的熵效应组合成单个32位数

图2:两个随机32位数之一的单个位改变对boost :: hash_combine结果的影响

正在组合的任一值中的单个位改变的熵效应需要至少为log(2)[黑线].从图1中可以看出,种子值的最高位不是这种情况,对于第二到最高值也不是这样.这意味着统计上种子中的高位丢失了.使用位旋转而不是位移,xor或带有进位的加法而不是简单的加法,可以很容易地创建类似的hash_combine,以更好地保留熵.此外,当散列和种子都具有低熵时,散布更多的hash_combine将是优选的.如果要组合的哈希数预先不知道或者很大,则最大化这种传播的旋转是黄金分割.使用这些想法,我提出了以下hash_combine,就像使用boost一样使用6个操作但是实现了更多混乱的散列行为并更好地保留了输入位.当然,人们可以总是疯狂地赢得比赛,只需通过一个不均匀的整数加一个乘法,这将很好地分配哈希.

图3:使用建议的hash_combine替代方案将两个随机32位数之一中的单个位改变的熵效应组合成单个32位数

图4:两个随机32位数之一的单个位改变对建议的hash_combine替代结果的影响

#include <iostream>
#include <limits>
#include <cmath>
#include <random>
#include <bitset>
#include <iomanip>
#include "wmath.hpp"

using wmath::popcount;
using wmath::reverse;

using std::cout;
using std::endl;
using std::bitset;
using std::setw;


constexpr uint32_t hash_combine_boost(const uint32_t& a, const uint32_t& b){
  return a^( b + 0x9e3779b9 + (a<<6) + (a>>2) );
}

template <typename T,typename S>
typename std::enable_if<std::is_unsigned<T>::value,T>::type
constexpr rol(const T n, const S i){
  const T m = (std::numeric_limits<T>::digits-1);
  const T c = i&m;
  return (n<<c)|(n>>((-c)&m)); // this is usually recognized by the compiler to mean rotation, try it with godbolt
}

template <typename T,typename S>
typename std::enable_if<std::is_unsigned<T>::value,T>::type
constexpr ror(const T n, const S i){
  const T m = (std::numeric_limits<T>::digits-1);
  const T c = i&m;
  return (n>>c)|(n<<((-c)&m)); // this is usually recognized by the compiler to mean rotation, try it with godbolt
}

template <typename T>
typename std::enable_if<std::is_unsigned<T>::value,T>::type
constexpr circadd(const T& a,const T& b){
  const T t = a+b;
  return t+(t<a);
}

template <typename T>
typename std::enable_if<std::is_unsigned<T>::value,T>::type
constexpr circdff(const T& a,const T& b){
  const T t = a-b;
  return t-(t>a);
}

constexpr uint32_t hash_combine_proposed(const uint32_t&seed, const uint32_t& v){
  return rol(circadd(seed,v),19)^circdff(seed,v);
}

int main(){
  size_t boost_similarity[32*64]    = {0};
  size_t proposed_similarity[32*64] = {0};
  std::random_device urand;
  std::mt19937 mt(urand());
  std::uniform_int_distribution<uint32_t> bit(0,63);
  std::uniform_int_distribution<uint32_t> rnd;
  const size_t N = 1ull<<24;
  uint32_t a,b,c;
  size_t collisions_boost=0,collisions_proposed=0;
  for(size_t i=0;i!=N;++i){
    const size_t n = bit(mt);
    uint32_t t0 = rnd(mt);
    uint32_t t1 = rnd(mt);
    uint32_t t2 = t0;
    uint32_t t3 = t1;
    if (n>31){
      t2^=1ul<<(n-32);
    }else{
      t3^=1ul<<n;
    }
    a = hash_combine_boost(t0,t1);
    b = hash_combine_boost(t2,t3);
    c = a^b;
    size_t count = 0;
    for (size_t i=0;i!=32;++i) boost_similarity[n*32+i]+=(0!=(c&(1ul<<i)));
    a = hash_combine_proposed(t0,t1);
    b = hash_combine_proposed(t2,t3);
    c = a^b;
    for (size_t i=0;i!=32;++i) proposed_similarity[n*32+i]+=(0!=(c&(1ul<<i)));
  }

  for (size_t j=0;j!=64;++j){
    for (size_t i=0;i!=32;++i){
      cout << setw(12) << boost_similarity[j*32+i] << " ";
    }
    cout << endl;
  }

  for (size_t j=0;j!=64;++j){
    for (size_t i=0;i!=32;++i){
      cout << setw(12) << proposed_similarity[j*32+i] << " "; 
    }
    cout << endl;
  }
}