¿Cómo hash una matriz bidimensional de dos estados?

Considere el siguiente código. ¿Qué es una buena función hash para la matriz en Key que se utilizará en un desordered_map?¿Cómo hash una matriz bidimensional de dos estados?

#include <unordered_map> 

using namespace std; 

enum TriState { 
    S0 = -1, 
    S1 = 0, 
    S2 = +1 
}; 

struct K { // Key for the map 
    TriState a[8][8]; 
    bool operator==(const K& k1) const { 
     for (int i = 0; i < 64; i++) 
      if (k1.a[0][i] != a[0][i]) 
       return false; 
     return true; 
    } 
}; 

struct Hash { 
    size_t operator()(const K& k) const { 
     size_t s; 
     // s = what is a good hash value? 
     return s; 
    } 
}; 

unordered_map<K, int, Hash> m;

Fuente

2011-12-16 Martin

Normalmente en los juegos de mesa se usa Zobrist-hashing. – wildplasser

El optimizador en mí se encoge al operador == método. 64 int lee que probablemente podría convertirse en una sola lectura de 16 bytes con un toquecito. –

@MichaelDorgan: error de optimización. Solo usa 'memcmp' y deja que el compilador lo simplifique :). – kennytm

Este algoritmo debe ser rápida y proporcionar hash casi uniforme:

size_t s = 0x3a7eb429; // Just some random seed value 
for (int i = 0; i != 8; ++i) 
{ 
    for (int j = 0; j != 8; ++j) 
    { 
     s = (s >> 1) | (s << (sizeof(size_t) * 8 - 1)); 
     s ^= k.a[i][j] * 0xee6b2807; 
    } 
} 
s *= 0xee6b2807; 
s ^= s >> 16;

Después de eso, si usted quiere hacer el hash aún más fuerte, el hash s otra vez usando, por ejemplo, MurmurHash3.

Fuente

2011-12-16 14:05:25 Baltram

http://ideone.com/rI9R2 Parece una distribución lo suficientemente buena para mí. –

¿Cómo hash una matriz bidimensional de dos estados?

Respuesta

Cuestiones relacionadas