unordered_map - Hash function has no effect

Question

Why in the following the hash function (which returns constant 0) seems not be taking any effect?

Since the hash function is returning constant, I was expecting as output all values to be 3. However, it seems to uniquely map the std::vector values to a unique value, regardless of my hash function being constant.

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

Obtained output:

1=1
2=2
3=3

Expected output:

1=3
2=3
3=3

What am I missing about hash?

Answer 1

You misunderstood the use of the hash function: it's not used to compare elements. Internally, the map organizes the elements into buckets and the hash function is used to determine the bucket into which the element resides. Comparison of the elements is performed with another template parameter, look at the full declaration of the unordered_map template:

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;

The next template parameter after the hasher is the key comparator. To get the behavior you expect, you would have to do something like this:

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;

Now your map will have a single element and all your results will be 3.

Answer 2

A sane hash table implementation should not lose information, even in the presence of hash collisions. There are several techniques that allow the resolution of collisions (usually trading off runtime performance to data integrity). Obviously, std::unordered_map implements it.

See: Hash Collision Resolution

Answer 3

Add a predicate key comparer class.

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

Use it like this:

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

Then the rest of your code will work as expected.