NFD

@Haowei agrees to work on this Task in 0.3 timeline.

Change boost::unordered_map to std::unordered_map because it becomes available with C++11.

The std::unordered_map supports customized hash function, and a equal_to predicate can be provided to determine if two keys match. As a result, it seems possible to use std::unordered_map to achieve hash table functions. However, I have noticed two performance related issues so far.

• lookup() The name tree lookup keys are the name prefix strings. To accelerate lookup, in the current hash table implementation, each hash table entry stores the full hash value, and string matching is required only if the hash values match.

It is not clear if the same optimization can be supported by std::unordered_map. For instance, to use the equal_to predicate, we could customize a key structure that contains both the hash value and the key. However, during a lookup, the hash value needs to be computed before calling the unordered_map.find() function, which wastes CPU cycles as the hash values would essentially be computed twice.

The following is an example using a customized key (original link: http://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key)

struct Key
{
  std::string first;
  std::string second;
  int         third;

  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }
};

int main()
{
  std::unordered_map<Key,std::string> m6 = {
    { {"John", "Doe", 12}, "example"},
    { {"Mary", "Sue", 21}, "another"}
  };
}

• Hash table resize()

The other benefit of storing hash values in the hash table is that, during resize(), we don't need to recompute the hash values.

The std::unordered_map rehash() function would require rehash all the items stored in the hash table. When the table size is large, the rehash() function may take considerable amount of time. So far, I have not found alternative methods for rehash().

I will continue exploring ways to accelerate lookup() and resize(). Please let me know if you are aware of any alternative methods.

any news here?

20160526 call decides to abandon this task, because there's no evidence that Haowei's hash table implementation has bugs, and switching to STL is likely to worsen performance.