A Comparison of C++ Hash Tables

This is a comparison I did before. It is hard to say which one is the best. They have different performance with different test data. We can only determine the best one in specific scenario. Generally, std::__unordered_map with __cache_hash_code=true outperforms the others in most of conditions, google::dense_hash_map has worse performance with short or few keys. This test was done with 64bit gcc 4.5.1 on a multi-core 3.6GHz cpu.

# with key based on sprintf(s, "%lx_x", i, rand()%1000)
INFO - test_Hash(std::__unordered_map with __cache_hash_code=true (w)): 0.246489(s)
INFO - test_Hash(std::__unordered_map with __cache_hash_code=true (r)): 13.9586(s)
INFO - test_Hash(std::unordered_map (w)): 0.351654(s)
INFO - test_Hash(std::unordered_map (r)): 16.2773(s)
INFO - test_hash(google::dense_hash_map (w)): 0.253774(s)
INFO - test_hash(google::dense_hash_map (r)): 14.4838(s)
INFO - test_Hash(boost hash table (w)): 0.473683(s)
INFO - test_Hash(boost hash table (r)): 15.6317(s)

# with key based on sprintf(s, "%lx", i)
INFO - test_Hash(std::__unordered_map with __cache_hash_code=true (w)): 0.137569(s)
INFO - test_Hash(std::__unordered_map with __cache_hash_code=true (r)): 10.5713(s)
INFO - test_Hash(std::unordered_map (w)): 0.179186(s)
INFO - test_Hash(std::unordered_map (r)): 12.1257(s)
INFO - test_hash(google::dense_hash_map (w)): 0.570974(s)
INFO - test_hash(google::dense_hash_map (r)): 18.6572(s)
INFO - test_Hash(boost hash table (w)): 0.216315(s)
INFO - test_Hash(boost hash table (r)): 11.17(s)

struct Hash
{
  size_t operator()(const char* s) const
  {
#if 0
    /* magic numbers bits from http://www.isthe.com/chongo/tech/comp/fnv/ */
    // FNV-1a
    size_t h = 14695981039346656037U;
    while (*s) {
      h ^= *s; 
      h *= 1099511628211U;
      ++s;
    }
    return h;
#else
    std::size_t seed = 0;
    for (; *s; ++s) {
      boost::hash_combine(seed, *s);
    }   
    return seed;
#endif
  }
};

BOOST_AUTO_TEST_CASE(test_Hash)
{
  typedef std::__unordered_map<const char*, size_t, Hash, eqstr, 
    std::allocator<std::pair<const char*, size_t> >, true> THash1;
  typedef std::unordered_map<const char*, size_t, Hash, eqstr> THash2;
  typedef google::dense_hash_map<const char*, size_t, Hash, eqstr> GHash;
  GHash gh;
  gh.set_empty_key("");
  typedef boost::unordered_map<const char*, size_t, Hash, eqstr> BHash;
  THash1 th1;
  THash2 th2;
  BHash bh;
  std::vector<const char*> strs;
  const size_t loops = 1e+6;
  const size_t rloops = 50;
  for (size_t i = 0; i < loops; ++i) {
    char* s = new char[16];
    sprintf(s, "%lx_%x", i, rand()%1000); // or sprintf(s, "%lx", i)
    strs.push_back(s);
  }
  {
    {
      MyTimer t("test_Hash(std::__unordered_map with __cache_hash_code=true (w))");
      for (size_t i = 0; i < loops; ++i)
        th1[strs[i]] = i;
    }

    {
      MyTimer t("test_Hash(std::__unordered_map with __cache_hash_code=true (r))");
      for (size_t j = 0; j < rloops; ++j)
        for (size_t i = 0; i < loops; ++i)
          BOOST_CHECK(th1[strs[i]] == i);
    }
  }
  {
    {
      MyTimer t("test_Hash(std::unordered_map (w))");
      for (size_t i = 0; i < loops; ++i)
        th2[strs[i]] = i;
    }

    {
      MyTimer t("test_Hash(std::unordered_map (r))");
      for (size_t j = 0; j < rloops; ++j)
        for (size_t i = 0; i < loops; ++i)
          BOOST_CHECK(th2[strs[i]] == i);
    }
  }
  {
    {
      MyTimer t("test_hash(google::dense_hash_map (w))");
      for (size_t i = 0; i < loops; ++i)
        gh[strs[i]] = i;
    }

    {
      MyTimer t("test_hash(google::dense_hash_map (r))");
      for (size_t j = 0; j < rloops; ++j)
        for (size_t i = 0; i < loops; ++i)
          BOOST_CHECK(gh[strs[i]] == i);
    }
  }
  {
    {
      MyTimer t("test_Hash(boost hash table (w))");
      for (size_t i = 0; i < loops; ++i)
        bh[strs[i]] = i;
    }

    {
      MyTimer t("test_Hash(boost hash table (r))");
      for (size_t j = 0; j < rloops; ++j)
        for (size_t i = 0; i < loops; ++i)
          BOOST_CHECK(bh[strs[i]] == i);
    }
  }
}