16.4. Open hashingΒΆ

One collision avoidance strategy is separate chaining. In separate chaining the hash table is implemented as an array of variable sized containers that can hold however many elements that have actually collided at each array location.

A linked list is a typical choices for implementing the chain, which is where the term "chaining" actually originates.

Example set

Fruit set

Example map

When the ADT is a map, the process is similar. In a map ADT, the value hashed is the map key, since this is what uniquely identifies map items.

Each bucket provides access to one or more map entries (key-value pairs).

Fruit inventory map

The linked lists allows the hash table to be dynamically sized, and each array element is its own bucket.

A set provides a simple demonstration of the capabilities of a hashed data structure. Recall that set defines a container that stores unique items.

hash_set

The template variables for a hash set defines the type of data stored in the set: the Key. This hash table will be fixed size, so we denote that with the non-type template parameter N. The Comparator allows the template to accept a function used to find items in the chain. The default is equal, but another binary predicate can be substituted.

template <class Key,
          size_t N,
          class Comparator=std::equal_to<Key>>
class hash_set
{
  public:
    using Container = std::list<Key>;
    using value_type = Key;
    using key_type   = Key;
    using iterator   = typename Container::iterator;
    using const_iterator  = const iterator;

    hash_set () = default;

  private:
    std::array<Container, N> buckets;
    Comparator compare;
    int sz = 0;

};

find

Finding anything in a hash table using separate chaining is a two step process. Consider the following hash table:

Simple hash table

How does the software find the value 34 in this data structure?

First we need to find the right bucket. The hash override is used to compute the bucket. In this case the bucket is at index position 8.

Note we use std::hash<> here. Any Key type stored in this set must override std::hash.

private:
   Container& find_bucket (const Key& value)
   {
     return buckets[std::hash<Key>()(value) % N];
   }

Next, we search through the list stored in that bucket looking for a specific value. Each element in the list stored in the bucket is evaluated using operator== - the default for std::equal_to. As soon as operator== evaluates to true the value is returned.

iterator find (const Key& value)
{
  Container& b = find_bucket(value);
  return find_if(b.begin(), b.end(),
           [this, &value](Key x) {
             return compare(x, value);
           });
}

It should be clear that the performance of this data structure is highly dependent upon the quality of the hash function. Always returning 42 is a legitimate value for a hash, but an extremely poor one, because your hash table is no better than a linked list.

insert

Insert is similar to find. We use find_bucket to get the correct array element, if it exists. The we search to see if the value already exists in the linked list. If it does, replace the existing value with the new one. Otherwise, we add it to the list.

void insert (const Key& value)
{
  Container& b = find_bucket(value);
  iterator pos =
    find_if(b.begin(), b.end(),
        [this, &value](Key x) { return compare(x, value); });
  if (pos == b.end()) {
    b.push_back(value);
    ++sz;
  }
  else {
    *pos = value;
  }
}

erase

Erase is similar to insert.

  1. Find the bucket

  2. Search for the value

  3. If you find it, erase it.

    Otherwise, do nothing.

void erase (const Key& value)
{
Container& b = find_bucket(value);
iterator pos =
  find_if(b.begin(), b.end(),
      [this, &value](Key x) { return compare(x, value); });
if (pos != b.end()) {
  b.erase(pos);
  --sz;
  }
}

Run it

  1#include <array>
  2#include <algorithm>
  3#include <cstddef>
  4#include <functional>
  5#include <iomanip>
  6#include <iostream>
  7#include <list>
  8#include <utility>
  9
 10using std::list;
 11using std::array;
 12
 13
 14template <class Key,
 15         size_t N,
 16         class Comparator=std::equal_to<Key>>
 17class hash_set
 18{
 19  public:
 20    using Container = list<Key>;
 21    using value_type = Key;
 22    using key_type   = Key;
 23    using iterator   = typename Container::iterator;
 24    using const_iterator  = const iterator;
 25
 26    hash_set() = default;
 27
 28    iterator find (const Key& value)
 29    {
 30      Container& b = find_bucket(value);
 31      return find_if(b.begin(), b.end(),
 32            [this, &value](Key x) { return compare(x, value); });
 33    }
 34
 35    const_iterator find (const Key& value) const
 36    {
 37      const Container& b = find_bucket(value);
 38      return find_if(b.begin(), b.end(),
 39            [this, &value](Key x) { return compare(x, value); });
 40    }
 41
 42    int count (const Key& value) const
 43    {
 44      const Container& b = find_bucket(value);
 45      return (find_if(b.begin(), b.end(),
 46            [this, &value](Key x) { return compare(x, value); })
 47        == b.end()) ? 0 : 1;
 48    }
 49
 50    void insert (const Key& value)
 51    {
 52      Container& b = find_bucket(value);
 53      iterator pos =
 54        find_if(b.begin(), b.end(),
 55            [this, &value](Key x) { return compare(x, value); });
 56      if (pos == b.end()) {
 57        b.push_back(value);
 58        ++sz;
 59      }
 60      else {
 61        * pos = value;
 62      }
 63    }
 64
 65    void erase (const Key& value)
 66    {
 67      Container& b = find_bucket(value);
 68      iterator pos =
 69        find_if(b.begin(), b.end(),
 70            [this, &value](Key x) { return compare(x, value); });
 71      if (pos != b.end()) {
 72        b.erase(pos);
 73        --sz;
 74      }
 75    }
 76
 77    constexpr
 78      size_t size() const noexcept { return sz; }
 79
 80    constexpr
 81      bool empty() const noexcept { return sz == 0; }
 82
 83  private:
 84    array<Container, N> buckets;
 85    Comparator compare;
 86    size_t sz = 0;
 87
 88    Container& find_bucket (const Key& value)
 89    {
 90      return buckets[std::hash<Key>()(value) % N];
 91    }
 92
 93    constexpr
 94      const Container& find_bucket (const Key& value) const
 95      {
 96        return buckets[std::hash<Key>()(value) % N];
 97      }
 98
 99    friend
100    std::ostream& operator<<(std::ostream& os, const hash_set& rhs)
101    {
102      os << '[';
103      int i = 0;
104      for (const auto& bucket: rhs.buckets) {
105        for (const auto& value: bucket) {
106          os << i << ':' << value << ',';
107        }
108        ++i;
109      }
110      return os << ']';
111    }
112};
113
114int main() {
115  auto foo = hash_set<int, 11>{};
116  foo.insert(72);
117  foo.insert(72);
118  std::cout << "count: " << foo.count(72) << std::endl;
119
120  foo.erase(72);
121  std::cout << "count: " << foo.count(72) << std::endl;
122
123  foo.insert(-1);
124  foo.insert(0);
125  foo.insert(1);
126  foo.insert(2);
127  foo.insert(9);
128  foo.insert(81);
129  foo.insert(121);
130  foo.insert(572);
131  foo.insert(999);
132  std::cout << foo << std::endl;
133  auto it = foo.find(572);
134  std::cout << "value 572: " << *it << std::endl;
135}

More to Explore