unordered_map - Funkcja skrótu nie ma żadnego efektu

Question

Dlaczego następująca funkcja hash (która zwraca stałą 0) nie przynosi żadnego efektu?

Ponieważ funkcja skrótu zwraca stałą, oczekiwałem, że wszystkie wartości wyjściowe będą równe 3. Jednak wydaje się, że wartości std::vector są unikatowe, niezależnie od tego, czy moja funkcja skrótu jest stała.

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

Uzyskane wyjściowa:

1=1 
2=2 
3=3 

oczekiwany wynik:

1=3 
2=3 
3=3 

Co mi brakuje około hash?

Answer 1

Ty źle korzystanie z funkcji skrótu: to nie jest używany, aby porównać elementy. Wewnętrznie mapa organizuje elementy w segmenty, a funkcja mieszania służy do określania segmentu, w którym znajduje się element. Porównanie elementów odbywa się z innego parametru szablonu, spojrzeć na całą deklarację szablonu 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; 

Kolejnym parametrem szablonu po Hasher jest kluczem komparator. Aby uzyskać zachowanie można oczekiwać, trzeba by zrobić coś takiego:

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; 

Teraz Twoja mapa będzie mieć jeden element i wszystkie wyniki będą 3.

Answer 2

Implementacja tablic asocjacyjnych przy zdrowych zmysłach nie powinna tracić informacji, nawet w przypadku kolizji mieszania. Istnieje kilka technik, które umożliwiają rozwiązywanie kolizji (zwykle ograniczając wydajność środowiska wykonawczego do integralności danych). Oczywiście implementuje to std::unordered_map.

Patrz: Hash Collision Resolution

Answer 3

Dodaj klucz porównawczy klasy porównawczej.

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

Używaj go tak:

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

Wtedy reszta kodu będzie działać zgodnie z oczekiwaniami.