Alex Rivera | Logout

Why would map be much faster than unordered_map?

Asked 2011-01-31T01:07:15.620
13

I implemented a search caching results that consist of keys of type State (a class with 7 short ints) and values of type Score (a class of 3 doubles.) Using unordered_map was at least 20 times slower than map. Why?

Edit: Darn it! My hash function was

namespace std {
    size_t hash<State>::operator()(State const& s) const {
        size_t retval = hash<short>()(s.s[0]);
        for (int i = 1; i < R; i += 2) {  // 1 3 5
            int x = (static_cast<int>(s.s[i + 1]) << 16)
                + (static_cast<int>(s.s[i]));
            hash_combine(retval, x);
        }
    }
}

I forgot to return retval, so it was all colliding! I wish unordered_map had a hash_function_quality() function that reports the average number of collisions.

Edit
Report

1 Answer

0

For

I wish unordered_map had a hash_function_quality() function that reports the average number of collisions.

I think the following function might be helpful.

unordered_map::load_factor
    float load_factor() const;
The member function returns the average number of elements per bucket.

Lower the load_factor, better is the hash function.

answered 2011-01-31T03:38:26.747

Your Answer