Come hash un array bidimensionale tristato?

Considerare il seguente codice. Che cos'è una buona funzione di hashing per l'array in Key da utilizzare in una unordered_map?Come hash un array bidimensionale tristato?

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

fonte

2011-12-16 Martin

Normalmente nei giochi da tavolo è usato l'hashing di Zobristo. – wildplasser

L'ottimizzatore in me si riduce all'operatore == metodo. 64 int legge che potrebbe diventare un singolo 16 byte letto con un po 'di giocherellando. –

@MichaelDorgan: errore di ottimizzazione. Basta usare 'memcmp' e lasciare che il compilatore lo semplifichi :). – kennytm

Questo algoritmo dovrebbe essere veloce e fornire hashing pressoché 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;

Dopo di che, se si vuole fare l'hashing ancora più forte, hash s un'altra volta usando per esempio MurmurHash3.

fonte

2011-12-16 14:05:25 Baltram

http://ideone.com/rI9R2 Sembra una distribuzione abbastanza buona per me. –

Come hash un array bidimensionale tristato?

risposta

Problemi correlati