С++ - Почему boost:: hash_combine лучший способ комбинировать хэш-значения?

Ответ 1

Это "лучший" аргумент.

Это "хорошо" или даже "очень хорошо", по крайней мере поверхностно, легко.

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

Мы предположим, что seed является предыдущим результатом hasher или этого алгоритма.

^= означает, что бит слева и биты справа изменяют биты результата.

hasher(v) считается приличным хешем на v. Но остальное - защита, если это не приличный хеш.

0x9e3779b9 - это 32-битное значение (оно может быть расширено до 64 бит, если size_t, возможно, 64 бит), который содержит половину 0 с и половину 1 с. Это в основном случайный ряд из 0s и 1s, выполненный путем аппроксимации конкретной иррациональной константы как значения фиксированной точки базы-2. Это помогает убедиться, что если хешер возвращает плохие значения, мы все равно получаем мазок 1 и 0 в нашем выпуске.

(seed<<6) + (seed>>2) немного перетасовывает входящее семя.

Представьте, что константа 0x отсутствует. Представьте, что хешер возвращает константу 0x01000 для почти каждого v, переданного в. Теперь каждый бит семени распределяется по следующей итерации хэша, в течение которого он снова распространяется.

После одной итерации seed ^= (seed<<6) + (seed>>2) 0x00001000 становится 0x00041400. Тогда 0x00859500. Когда вы повторяете операцию, любые биты набора "размазаны" по выходным битам. В конце концов, правый и левый бит сталкиваются и переносят сдвиг установленного бита из "четных местоположений" в "нечетные местоположения".

Биты, зависящие от значения входного семени, растут относительно быстро и сложными способами, когда операция объединения повторяется при операции семени. Добавление причин несет, что мажет вещи еще больше. Константа 0x добавляет кучу псевдослучайных битов, которые заставляют скучные хэш-значения занимать более нескольких бит хэш-пространства после объединения.

Это несимметрично благодаря добавлению (объединение хэшей "dog" и "god" дает разные результаты), оно обрабатывает скучные значения хеша (сопоставление символов с их значением ascii, которое включает только скручивание нескольких бит). И это достаточно быстро.

Более медленные хеш-комбинации, криптографически сильные, могут быть лучше в других ситуациях. Я, наивно, предположил бы, что превращение сдвигов в комбинацию четных и нечетных сдвигов может быть хорошей идеей (но, возможно, добавление, которое перемещает четные биты из нечетных битов, делает это менее проблематичным: после 3 итераций входящее одиночное семя биты будут сталкиваться и добавлять и вызывать перенос).

Недостатком такого рода анализа является то, что только одна ошибка делает хэш-функцию очень плохой. Отказ от всех хороших вещей не очень помогает. Итак, еще одна вещь, которая делает это хорошо сейчас, - это то, что она достаточно известна и в репозитории с открытым исходным кодом, и я не слышал, чтобы кто-нибудь указывал, почему это плохо.

Ответ 2

Это не самое лучшее, удивительно для меня это даже не особенно хорошо. Рисунок 1: Энтропийный эффект изменения одного бита в одном из двух случайных 32-разрядных чисел, объединяемых в одно 32-разрядное число, с использованием boost :: hash_combine

Рисунок 2: Влияние изменения одного бита в одном из двух случайных 32-битных чисел на результат boost :: hash_combine

Энтропийный эффект изменения одного бита в любом объединяемом значении должен быть не менее log (2) [черная линия]. Как видно из рисунка 1, это не относится к старшему биту начального значения, а также немного к старшему значению. Это означает, что статистически старшие биты в семени теряются. Используя битовые вращения вместо битовых сдвигов, xor или сложения с переносом вместо простого сложения, можно легко создать аналогичный hash_combine, который лучше сохраняет энтропию. Также, когда hash и seed оба имеют низкую энтропию, предпочтительнее использовать hash_combine, который распространяет больше. Вращение, которое максимизирует этот разброс, является золотым сечением, если число хэшей, которые должны быть объединены, заранее неизвестно или велико. Используя эти идеи, я предлагаю следующий hash_combine, который использует 6 операций точно так же, как boost, но обеспечивает более хаотичное поведение хеш-функции и лучше сохраняет входные биты. Конечно, всегда можно сойти с ума и выиграть конкурс, добавив всего лишь одно умножение на неравное целое число, это очень хорошо распределит хэши.

Рисунок 3: Энтропийный эффект изменения одного бита в одном из двух случайных 32-разрядных чисел, объединяемых в одно 32-разрядное число, с использованием предложенной альтернативы hash_combine

Рисунок 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;
  }
}

Edit: В случае, если вы хотите использовать мультипликативную хеш-функцию, имейте в виду, что она каскадируется только старшим битам. Но этот недостаток можно компенсировать с помощью бинарных вращений. Три раунда последовательных умножений и вращений (всего 6 основных операций) кажутся достаточными для получения очень ровных выходных данных.

Смотрите также: fooobar.com/info/79932/...