CODEWITHSUNDEEP
boostunordered-map
MrCartoonology
MrCartoonology

Reputation: 2067

Can boost unordered_map, or alternative hash table, skip equality comparison if only one item in bucket?

It appears to me that boost::unordered_map always checks for equality between the key you are looking up and the key(s) in the bucket, even if there is only one item in the bucket that your key hashed to. This is safe, the table could have been built with different keys then what you are looking up, and the key you are looking up may collide with one of the previous keys used to build the table.

However suppose I know what keys I will be looking up and I would like to skip the equality check if there is only one key in the bucket. That is I can guarantee that I will only look up keys that I have previously inserted into the map. Is there a way with boost to skip the equality check, or is there some other hash table implementation that does this?

Here is the example code I wrote that indicates boost::unordered_map is checking for equality if there is only one item:

#include <iostream>
#include <boost/unordered_map.hpp>

typedef void (*dispatchFunction)();

void dispatchA() { std::cout << "A" << std::endl; }
void dispatchB() { std::cout << "B" << std::endl; }

template<class T> 
struct myequal_to {
  bool operator()(const T &a, const T &b) const {
    std::cout << "myequal_to: " << a << " " << b << std::endl;
    return a==b;
  }
};

void unordered_map_example() {
  typedef boost::unordered_map<std::string, dispatchFunction,
                       boost::hash<std::string>,
                       myequal_to<std::string> > mymap_t;
  mymap_t mymap;
  mymap["eventA"]=dispatchA; 
  mymap["eventB"]=dispatchB;

  mymap_t::size_type max_elements_in_a_bucket = 0;
  for (mymap_t::size_type bucket = 0; bucket < mymap.bucket_count(); ++bucket) {
    max_elements_in_a_bucket = std::max(max_elements_in_a_bucket,
                                        mymap.bucket_size(bucket));
  }
  std::cout << "number of buckets: " << mymap.bucket_count() 
            << " max per bucket: " << max_elements_in_a_bucket << std::endl;

  dispatchFunction foo = mymap["eventA"];
  foo();
}

int main() {
  unordered_map_example();
  return 0;
}

My output shows myequal to was called:

number of buckets: 11 max per bucket: 1 myequal_to: eventA eventA A

Upvotes: 0

Views: 466

Answers (1)

Ben Jackson
Ben Jackson

Reputation: 93720

If it is possible for there to be collisions at all (and thus to require more than one element in the bucket) then you must check the hash key because the lone element you found may collide with the target without being the target. I suppose if you are searching for a key known to be in the table and are only doing the search to find it you could skip the comparision.

Upvotes: 1

Related Questions