A Fast Hash Table Implementation

The ootl::hash_map is an implementation of a hash-table ADT which uses the Paul Hseih's hash function and uses the pseudo-quadratic probing collision resolution from google::dense_hash_map.

The ootl::hash_map implementation is much faster than the STLPort 4.6.2 hash_map template (see benchmarks). The ootl::hash_map provides faster growth then a google hash map implementation, which it trades for slower indexing.

The ootl::hash_map has another useful property, which both the STLPort and Google implementations lack: memory locations are never invalidated.

The Interface

The following is the interface of the ootl::hash_map template. Since the project is still under-development only minimal functionality is provided for the time being.

  template
  <
    typename Key,
    typename Data,
    typename Hash = ootl::hasher<Key>,
    typename Compare = ootl::comparator<Key>,
    int Sparsity = 2,
  >
  struct hash_map {
  public:
    typedef Key key_type;
    typedef Data data_type;
    typedef Value value_type;
    typedef hash_map self;
    typedef Impl inherited;
    typedef typename inherited::buffer buffer;
  public:
    hash_map(const key_type& empty_key, const data_type& empty_data);
    data_type& operator[](const key_type& x);
    void insert(const value_type& x);
  };

back to the OOTL documentation home page
back to the OOTL.org home page

http://www.ootl.org
last modified: November 13, 2005
Copyright Christopher Diggins, 2005
OOTL logo copyright 2005 Paige Lybbert.