A Generic Open-address Hash Table Implementation with an STL-like Interface

Download source code - 16.9 KB

Introduction

Hash tables are very common data structures. They provide efficient key based operations to insert and search for data in containers. Like many other things in Computer Science, there are trade offs associated to the use of hash tables. They are not good choices when there is a need for sort and select operations.

There are two main issues regarding the implementation of hash based containers: the hash function and the collision resolution mechanism. The hash function is responsible for the arithmetic operation that transforms a particular key into a particular table address. The collision resolution mechanism is responsible for dealing with keys that hash to the same address.

Although the C++ STL (Standard Template Library) does not support hash based containers, most compilers like GCC or Visual C++ have their own implementation - it is worth noting that TR1 (Technical Report 1) already offers unordered map and set structures. Also, a good alternative is STLport [1], which provides the following class templates:

hash_set
hash_map
hash_multiset
hash_multimap

Interfaces of hash table implementations from different compilers may vary. Besides, not all of them support TR1. Integrating STLport into your code might not be that easy (unless you are already using it, of course). Finally, most of these hash based containers use separate chaining as the collision resolution mechanism, which is a straightforward method, but not the only one.

Open addressing is a method for handling collisions through sequential probes in the hash table. It can be very useful when there is enough contiguous memory and knowledge of the approximate number of elements in the table is available. Two well known open addressing strategies are linear probing and double hashing, which I briefly discuss in the next section.

In this article, I present a generic standalone STL-like implementation of a hash table that uses either linear probing or double hashing as the collision resolution mechanism. It serves as the underlying implementation of the four class templates mentioned above, and it is constructed with many C++ techniques applied in STLport. The code follows very closely to the STL and extended SGI concepts. Precisely, only one operation is not implemented (the reason is explained later). In addition, the code also works as an interesting introduction to generic programming. This is a brief article, and I do not provide neither theoretical discussion about hash tables nor all the implementation details. I am more interested in providing the source code so others can inspect, give suggestions, and hopefully benefit from it.

Hash Table Parameterization

The following class template is the underlying implementation of hash_set, hash_map, hash_multiset, and hash_multimap.

template <
  class key_t, 
  class value_t, 
  class hash_fcn_t,
  class increment_t,
  class equal_key_t,
  class get_key_t,
  class alloc_t> 
class hash_table__
{
  //...
};

Most of the template parameters above have meaningful names and a straightforward role. The first one, key_t, is the type of the hash table key. The second, value_t, is the type of the value. (In a set, the value is the actual the key; in a map, the value is a pair containing the key and value.) The hash function is represented by the third parameter. Skipping the fourth parameter, which I will explain in the next paragraph, the fifth parameter, equal_key_t, is a binary predicate used to determine whether two keys are equal. The parameter get_key_t has an interesting responsibility: it is a unary function used to obtain the key of a value stored in the hash table. This parameter must be set in accordance to the type of the value. The last template parameter is the allocator type.

There is only one significant difference between linear probing and double hashing. With linear probing, when a collision is detected, the algorithm looks for the position right next to the current table address to check if it is available. It keeps doing that until it finds an empty spot (once it reaches the end of the table, it starts over). Naturally, it is important that the table is not full. (This implementation assumes a maximum load factor of 5/10.) With double hashing, a second hash function is used as the increment from the current table address to the other positions the algorithm looks for. In this particular case, there is an extra concern of writing a second hash function that will not lead to an infinite loop. A good usual choice is an increment that is prime to the size of the table. I already provide two template specializations (for integral types) to use as the argument for the parameter increment_t.

//For linear probing.
template <class key_t>
struct unit_increment
{
  std::size_t operator()(const key_t&){ return 1; }
};

//For double hashing.
template <class key_t>
struct hash_increment{};

//Specialization for integral types are just like this one.
template <> 
struct hash_increment<short>
{
  std::size_t operator()(short x){return (x % 97) + 1;}
};

The behaviours of linear probing and double hashing are very similar. However, double hashing is less subjected to the formation of clusters, since keys that hash to the same address are likely to be spread throughout the table. On the other hand, implementation of linear probing might be a little bit simpler because of issues related to the erase operation. See [2] for more details.

As I mentioned before, hash_table__ is the underlying implementation of the map and set class templates. This is done through composition as shown in the code below for the case of hash_map.

template <
  class key_t, 
  class value_t, 
  class hash_fcn_t = hash<key_t>, 
  class increment_t = unit_increment<key_t>,
  class equal_key_t = std::equal_to<key_t>, 
  class alloc_t = std::allocator<std::pair<key_t, value_t> > >
class hash_multimap 
{
private:
  typedef std::pair<key_t, value_t> Map_pair;
  typedef hash_table__<
    key_t,
    Map_pair,
    hash_fcn_t,
    increment_t,
    equal_key_t,
    select1st<Map_pair>,
    alloc_t> HT; 
  HT underlying_;  
  //...
};

Iterators

Under the hood, the hash table is implemented with std::vector. Therefore, implementation of an iterator is relatively simple. Basically, it is necessary to have a pointer to the vector, an integral type to indicate the current position (or index), and some intelligence for the iteration process. There is, though, one point that is worth talking about.

When an iterator is dereferenced, a reference to an instance is provided. However, when a const_iterator is dereferenced, a constant reference is provided. Since this is just a mater of type difference, instead of writing two implementations for the iterators, we could use an auxiliary traits class template to do the job.

One of the template parameters of the iterator implementation is the hash table type. The other is the traits type. For the definition of the type iterator, the class template non_const_traits is used. For the definition of the type const_iterator, the class template const_traits is used. The following code shows the idea:

template <class value_t>
struct const_traits
{
  typedef const value_t* pointer;
  typedef const value_t& reference;
};

template <class value_t>
struct non_const_traits
{
  typedef value_t* pointer;
  typedef value_t& reference;
};

//Iterator implementation.
template <
  class hash_container_t,
  class constness_traits_t>  
struct hash_table_iterator__
{  
  //...
  typedef typename constness_traits_t::pointer pointer;
  typedef typename constness_traits_t::reference reference;
  reference operator*()const {return (*this->container_)[this->current_].value_;}
  pointer operator->()const {return &(operator*());}
};

A final issue is that conversion between an iterator and a const_iterator should be handled properly. Please refer to the source code for examples.

Using the Code

The usage of the code is just like for any STL container. Here is an example:

#include "hash_map.h"
#include <iostream>

int main()
{
  using namespace hashcol;
  
  typedef hash_map<int,double> Map;
  typedef Map::value_type value_type;
  typedef Map::iterator iterator;

  Map map;  
  map.insert(value_type(8, 8.888));
  map.insert(value_type(1, 1.111));
  map.insert(value_type(12, 12.12));
  map.insert(value_type(3, 3.3));
  map.insert(value_type(122, 122.122));
  
  std::cout << "\nSize is: " << map.size();
  std::cout << "\nElements are:";
  for (iterator it = map.begin(); it != map.end(); ++it)
  {
    std::cout << "\n\tKey = " << it->first 
              << "   Value = " << it->second;
  }
  
  return 0;
}

References

[1] STLport - http://www.stlport.org/
[2] Sedgewick R. Algorithms in C++ - Fundamentals, Data Structures, Sorting and Searching (3^rd edn). Addison-Wesley, 1998