CODEWITHSUNDEEP
c++hashunordered-map
rjk
rjk

Reputation: 65

User defined hash function for unordered map

I have defined my own hash function for an unrorderd_map. But I am unable to search in the container using the find function. I have tried debugging using a print statement within the hash function and it generates the same hash value which was generated while inserting the key/value. It would be great if someone could point out the error. I am using Eclipse IDE on windows and I am compiling with -std=c++11

typedef struct tree node;

struct tree
{
int id;
node *left;
node *right;
};

class OwnHash
{
public:
    std::size_t operator() (const node *c) const
    {
       cout << "Inside_OwnHash: " <<std::hash<int>()(c->id) + std::hash<node *>()(c->left) + std::hash<node *>()(c->right) << endl;
       return std::hash<int>()(c->id) + std::hash<node *>()(c->left) + std::hash<node *>()(c->right);
    }
};

int main()
{
std::unordered_map<node *,node *,OwnHash> ut;

node * one = new node;
one->id = -1;
one->left = nullptr;
one->right = nullptr;
ut.insert({one,one});

node * zero = new node;
zero->id = 0;
zero->left = NULL;
zero->right = NULL;
ut.insert({zero,zero});

node * cur = new node;
cur->id = 5;
cur->left = zero;
cur->right = one;
ut.insert({cur,cur});

for (auto& elem : ut)
{
    std::cout << "key: " << elem.first << "\t" << "value: " << elem.second->id << std::endl;
}

node * parse = new node;
parse->id = 5;
parse->left = zero;
parse->right = one;

std::unordered_map<node *,node *>::const_iterator got1 = ut.find (parse);

if ( got1 == ut.end() )
    std::cout << "not found";
else
    std::cout << got1->first << " is " << got1->second->id << std::endl;

return EXIT_SUCCESS;
}

    Output:
    Inside_OwnHash: 4294967295
    Inside_OwnHash: 0
    Inside_OwnHash: 22946517
    key: 0xaf11b0   value: 5
    key: 0xaf1180   value: 0
    key: 0xaf1150   value: -1
    Inside_OwnHash: 22946517
    not found

Upvotes: 3

Views: 2661

Answers (1)

Jan Hudec
Jan Hudec

Reputation: 76266

Hash is not enough, you must implement equality comparison too!

The hash has to be a function such that if the items are equal, they hash equal. But since the items may be arbitrarily complex and the hash result is just size_t, the opposite implication does not and cannot hold. So to find the exact element, you need an equality comparison too.

When looking up, the hash function points it to the right "bucket", but there may be multiple elements in it or there may be an element there, but not the one you are looking for. So it takes all elements in the bucket and compares each to the one you are searching.

Now you provided a hash function, but did not provide equality comparator. So it uses the default, which is operator== and that is for pointers defined as comparing the addresses. And the addresses are not equal. You need to provide equality functor that compares the values.

Upvotes: 7

Related Questions