4

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
3
  • unless for educational/learning purpose... just a question : are you the thousandth that questions about the fastness and efficiency of std c++ containers while in debug mode ? You could have good reason to reimplement the hash-table no problem. Just a reflex question. Commented Apr 20, 2013 at 8:18
  • I would make do with the built in hash function if I could. But I need to define my own for a particular reason. I am using it to build Binary Decision Diagrams. The code I have posted is just to mimic the scenario I need it in. Commented Apr 20, 2013 at 8:29
  • 1
    @StephaneRolland The code uses different semantics than the standard hash function - it hashes a pointer based on the contents of the object the pointer points to. That's a very valid reason for your own hash. I didn't see a single concern about std efficiency in the question. Commented Apr 20, 2013 at 8:31

1 Answer 1

8

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.

Sign up to request clarification or add additional context in comments.

1 Comment

Right on. Thank you so much. It makes perfect sense and it worked out as well.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.