unordered_map - La funzione hash non ha effetto

Question

Perché in seguito la funzione di hash (che restituisce la costante 0) non sembra avere alcun effetto?

Poiché la funzione di hash restituisce una costante, mi aspettavo come uscita tutti i valori per essere 3. Tuttavia, sembra mappare in modo univoco i valori std::vector a un valore univoco, indipendentemente dalla costante della mia funzione di hash.

#include <iostream> 
#include <map> 
#include <unordered_map> 
#include <vector> 


// Hash returning always zero. 
class TVectorHash { 
public: 
    std::size_t operator()(const std::vector<int> &p) const { 
    return 0; 
    } 
}; 

int main() 
{ 
    std::unordered_map<std::vector<int> ,int, TVectorHash> table; 

    std::vector<int> value1({0,1}); 
    std::vector<int> value2({1,0}); 
    std::vector<int> value3({1,1}); 

    table[value1]=1; 
    table[value2]=2; 
    table[value3]=3; 

    std::cout << "\n1=" << table[value1]; 
    std::cout << "\n2=" << table[value2]; 
    std::cout << "\n3=" << table[value3]; 

    return 0; 
} 

Ottenuto uscita:

1=1 
2=2 
3=3 

uscita prevista:

1=3 
2=3 
3=3 

Che cosa mi manca circa hash?

Answer 1

È frainteso l'uso della funzione di hash: non è usato per confrontare gli elementi. Internamente, la mappa organizza gli elementi in bucket e la funzione di hash viene utilizzata per determinare il bucket in cui risiede l'elemento. Il confronto degli elementi viene eseguita con un altro parametro di template, cerca nella dichiarazione completa del modello unordered_map:

template< 
    class Key, 
    class T, 
    class Hash = std::hash<Key>, 
    class KeyEqual = std::equal_to<Key>, 
    class Allocator = std::allocator< std::pair<const Key, T> > 
> class unordered_map; 

Il parametro di modello successivo dopo la Hasher è il comparatore chiave. Per ottenere il comportamento che ci si aspetta, che avrebbe dovuto fare qualcosa di simile:

class TVectorEquals { 
public: 
    bool operator()(const std::vector<int>& lhs, const std::vector<int>& rhs) const { 
     return true; 
    } 
}; 

std::unordered_map<std::vector<int> ,int, TVectorHash, TVectorEquals> table; 

Ora la vostra mappa avrà un unico elemento e tutti i risultati saranno 3.

Answer 2

Un'implementazione di tabella hash sana non deve perdere informazioni, anche in presenza di collisioni di hash. Esistono diverse tecniche che consentono la risoluzione delle collisioni (in genere il trasferimento delle prestazioni di runtime all'integrità dei dati). Ovviamente, std::unordered_map lo implementa.

Vedi: Hash Collision Resolution

Answer 3

Aggiungere una classe di confronto chiave predicato.

class TComparer { 
public: 
    bool operator()(const std::vector<int> &a, const std::vector<int> &b) const { 
     return true; // this means that all keys are considered equal 
    } 
}; 

usare in questo modo:

std::unordered_map<std::vector<int> ,int, TVectorHash, TComparer> table; 

Poi il resto del codice funzionerà come previsto.