geeksforgeeks - set string c++

C++: ¿Por qué boost:: hash_combine es la mejor manera de combinar valores hash?

Question

He leído en otras publicaciones que esta parece ser la mejor manera de combinar valores hash. ¿Alguien podría descomponer esto y explicar por qué esta es la mejor manera de hacerlo?

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);
}

Edit: La otra pregunta es solo pedir el número mágico, pero me gustaría conocer toda la función, no solo esta parte.

Answer 1

No es lo mejor, sorprendentemente para mí ni siquiera es particularmente bueno. Figura 1: el efecto entrópico de un solo cambio de bit en uno de los dos números aleatorios de 32 bits combinados en un solo número de 32 bits usando boost :: hash_combine

Figura 2: el efecto de un solo cambio de bit en uno de los dos números aleatorios de 32 bit sobre el resultado de boost :: hash_combine

El efecto entrópico de un solo cambio de bit en cualquier valor que se esté combinando debe ser al menos log (2) [línea negra]. Como puede verse en la figura 1, este no es el caso para el bit más alto del valor inicial y también un poco ajustado para el segundo valor más alto. Esto significa que estadísticamente los bits altos en la semilla se están perdiendo. Usando rotaciones de bits en lugar de desplazamientos de bits, xor o adición con acarreo en lugar de una simple adición, se podría crear fácilmente un hash_combine similar que conserve mejor la entropía. Además, cuando el hachís y la semilla son ambos de baja entropía, sería preferible una combinación de hachís que se propague más. La rotación que maximiza esta extensión es la sección dorada si el número de hashes que se van a combinar no se conoce de antemano o es grande. Usando estas ideas, propongo el siguiente hash_combine, que usa 6 operaciones como boost, pero está logrando un comportamiento de hash más caótico y preserva mejor los bits de entrada. Por supuesto, uno siempre puede volverse loco y ganar el concurso agregando solo una multiplicación por un entero desigual, esto distribuirá los hashes muy bien.

Figura 3: el efecto entrópico de un solo cambio de bit en uno de los dos números aleatorios de 32 bits que se combinan en un solo número de 32 bits utilizando la alternativa hash_combine propuesta

Figura 4: El efecto de un cambio de un solo bit en uno de los dos números aleatorios de 32 bits en el resultado de la alternativa de combinación hash_combine propuesta

#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;
  }
}

Answer 2

Ser el "mejor" es argumentativo.

Ser "bueno", o incluso "muy bueno", al menos superficialmente, es fácil.

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

hasher seed es un resultado anterior de hasher o este algoritmo.

^= significa que los bits a la izquierda y los bits a la derecha cambian todos los bits del resultado.

hasher(v) se presume que es un hash decente en v . Pero el resto es defensa en caso de que no sea un hash decente.

0x9e3779b9 es un valor de 32 bits (podría extenderse a 64 bits si size_t era de 64 bits posiblemente) que contiene la mitad de 0 y la mitad de 1. Básicamente es una serie aleatoria de 0s y 1s realizada al aproximar una constante irracional particular como un valor de punto fijo base-2. Esto ayuda a garantizar que si el indicador de valores devuelve valores incorrectos, aún obtengamos un borrón de 1 y 0 en nuestra salida.

(seed<<6) + (seed>>2) es un poco aleatorio de la semilla entrante.

Imagina que faltaba la constante 0x . Imagine que el hasher devuelve la constante 0x01000 para casi todos los v pasados. Ahora, cada bit de la semilla se distribuye en la siguiente iteración del hash, durante la cual se distribuye nuevamente.

La seed ^= (seed<<6) + (seed>>2) 0x00001000 convierte en 0x00041400 después de una iteración. Entonces 0x00859500 . A medida que repite la operación, cualquier bit establecido se "mancha" sobre los bits de salida. Finalmente, los bits derecho e izquierdo chocan, y el transporte mueve el bit establecido de "ubicaciones pares" a "lugares impares".

Los bits que dependen del valor de una semilla de entrada crecen relativamente rápido y de manera compleja a medida que la operación de combinación recurre en la operación de semilla. Añadir causas lleva, lo que difumina aún más las cosas. La constante 0x agrega un grupo de bits pseudoaleatorios que hacen que los valores de hash aburridos ocupen más de unos pocos bits del espacio de hash después de ser combinados.

Es asimétrico gracias a la adición (combinando los hashes de "dog" y "god" da diferentes resultados), maneja valores hash aburridos (mapeando caracteres a su valor ascii, que solo implica girar un puñado de bits). Y, es razonablemente rápido.

Las combinaciones de hash más lentas que son criptográficamente fuertes pueden ser mejores en otras situaciones. Yo, ingenuamente, presumiría que hacer los cambios sea una combinación de turnos pares e impares podría ser una buena idea (pero tal vez la adición, que mueve incluso bits de bits impares, hace que el problema sea menor: después de 3 iteraciones, semilla solitaria entrante los bits chocarán y agregarán y causarán un acarreo

La desventaja de este tipo de análisis es que solo se necesita un error para que una función hash sea realmente mala. Señalar todas las cosas buenas no ayuda mucho. Otra cosa que lo hace bueno ahora es que es razonablemente famoso y está en un repositorio de código abierto, y no he escuchado a nadie señalar por qué es malo.