16.4. Open hashing

One collision-resolution strategy is separate chaining, also called open hashing. In separate chaining, the hash table is an array of buckets. Each bucket refers to a collection that can hold every key mapped to that bucket. A linked list is a traditional choice for the collection, which is where the term "chaining" originates, but other containers are possible.

The first item in a bucket is not itself a collision. A collision occurs when a second or later key maps to the same bucket index. The bucket's collection stores all of those keys together.

Example set

The following diagram uses seven buckets. The bucket assignments are shown directly so that the two chains are easy to follow; a real table would compute each assignment with its hash function.

Example map

When the ADT is a map, the process is similar. The value hashed is the map key, since the key uniquely identifies a map entry. Each bucket provides access to one or more key-value pairs.

The linked lists allow the contents of each bucket to grow as needed, while the array provides the first lookup step. A fixed bucket count is used here to keep the implementation focused; production hash tables also monitor load factor and rehash when appropriate.

A set provides a simple demonstration of a hashed data structure. Recall that set stores unique items. The implementation below is similar to a set, but intentionally leaves out iterators over all buckets, rehashing, allocator support, and many other standard-library features.

hash_set

The template parameters describe the key type, the fixed number of buckets, the hash function, and the equality predicate. Equivalent keys must compare equal and must produce the same hash value.

Simplified interface

template <class Key,
          std::size_t N,
          class Hash = std::hash<Key>,
          class KeyEqual = std::equal_to<Key>>
class hash_set {
  using iterator = typename Container::iterator;
  using const_iterator = typename Container::const_iterator;

  std::pair<iterator, bool> insert(const Key& value);
  iterator find(const Key& value);
  const_iterator find(const Key& value) const;
  std::size_t count(const Key& value) const;
  std::size_t erase(const Key& value);
};

find

Finding a value using separate chaining has two steps:

1. Compute the hash value and reduce it to a bucket index.

2. Search the selected bucket, comparing keys with the equality predicate.

The following diagram uses value % 10 as its illustrative hash for integer keys. The chain in bucket 4 contains two values, so finding 54 requires checking more than one entry.

To find 54, the table computes 54 % 10 == 4 and selects bucket 4. It compares 54 with 34 first, then with 54. The equality predicate confirms the match, and find returns an iterator to the stored value. If the value is absent, it returns the bucket's end() iterator.

Pseudocode

bucket <- buckets[hash(value) % bucket_count]
for each item in bucket:
    if equal(item, value):
        return iterator to item
return bucket.end()

A hash function that always returns 42 still satisfies the basic hash contract: equivalent keys produce the same hash value, and collisions are allowed. It is nevertheless a poor choice. Every key would be placed in bucket 42 % bucket_count, so a lookup would linearly scan one growing chain and lose the expected constant-time benefit.

insert

Inserting into a set follows the same two steps as finding:

1. Select the bucket.

2. Search for an equivalent key.

If the key is already present, the set remains unchanged. Otherwise, the new key is appended to the bucket. Returning an iterator and a Boolean follows the contract used by standard associative containers: the Boolean is true only when a new key was inserted.

Pseudocode

bucket <- buckets[hash(value) % bucket_count]
position <- find equivalent value in bucket
if position != bucket.end():
    return {position, false}
append value to bucket
return {iterator to new value, true}

erase

Erasing is also a bucket search followed by an equality comparison. If the key is found, remove it and return 1. Otherwise return 0.

Pseudocode

bucket <- buckets[hash(value) % bucket_count]
position <- find equivalent value in bucket
if position == bucket.end():
    return 0
erase position from bucket
return 1

Run it

This complete example uses an identity hash for positive integers so that its bucket assignments are predictable. Values such as 34 and 45 deliberately collide in bucket 1 when there are 11 buckets.

#include <algorithm>
#include <array>
#include <cstddef>
#include <functional>
#include <iostream>
#include <iterator>
#include <list>
#include <ostream>
#include <utility>

struct identity_hash {
  std::size_t operator()(int value) const noexcept {
    return static_cast<std::size_t>(value);
  }
};

template <class Key,
          std::size_t N,
          class Hash = std::hash<Key>,
          class KeyEqual = std::equal_to<Key>>
class hash_set {
  static_assert(N > 0, "hash_set needs at least one bucket");

  using container_type = std::list<Key>;

public:
  using value_type = Key;
  using key_type = Key;
  using size_type = std::size_t;
  using iterator = typename container_type::iterator;
  using const_iterator = typename container_type::const_iterator;
  using insert_result = std::pair<iterator, bool>;

  insert_result insert(const Key& value) {
    auto& bucket = find_bucket(value);
    const auto position = find_in_bucket(bucket, value);
    if (position != bucket.end()) {
      return {position, false};
    }

    bucket.push_back(value);
    ++size_;
    return {std::prev(bucket.end()), true};
  }

  iterator find(const Key& value) {
    return find_in_bucket(find_bucket(value), value);
  }

  const_iterator find(const Key& value) const {
    return find_in_bucket(find_bucket(value), value);
  }

  size_type count(const Key& value) const {
    const auto& bucket = find_bucket(value);
    return find_in_bucket(bucket, value) == bucket.end() ? 0 : 1;
  }

  size_type erase(const Key& value) {
    auto& bucket = find_bucket(value);
    const auto position = find_in_bucket(bucket, value);
    if (position == bucket.end()) {
      return 0;
    }

    bucket.erase(position);
    --size_;
    return 1;
  }

  size_type size() const noexcept {
    return size_;
  }

  bool empty() const noexcept {
    return size_ == 0;
  }

  friend std::ostream& operator<<(std::ostream& os,
                                  const hash_set& set) {
    os << '[';
    for (size_type bucket_index = 0;
         bucket_index < N; ++bucket_index) {
      for (const auto& value : set.buckets_[bucket_index]) {
        os << bucket_index << ':' << value << ' ';
      }
    }
    return os << ']';
  }

private:
  container_type& find_bucket(const Key& value) {
    return buckets_[hasher_(value) % N];
  }

  const container_type& find_bucket(const Key& value) const {
    return buckets_[hasher_(value) % N];
  }

  iterator find_in_bucket(container_type& bucket,
                          const Key& value) {
    return std::find_if(bucket.begin(), bucket.end(),
                        [this, &value](const Key& item) {
                          return equal_(item, value);
                        });
  }

  const_iterator find_in_bucket(const container_type& bucket,
                                const Key& value) const {
    return std::find_if(bucket.begin(), bucket.end(),
                        [this, &value](const Key& item) {
                          return equal_(item, value);
                        });
  }

  std::array<container_type, N> buckets_;
  Hash hasher_;
  KeyEqual equal_;
  size_type size_ = 0;
};

int main() {
  hash_set<int, 11, identity_hash> values;

  const auto first = values.insert(34);
  const auto duplicate = values.insert(34);
  values.insert(45);
  values.insert(21);

  std::cout << std::boolalpha
            << "first insertion: " << first.second << '\n'
            << "duplicate insertion: " << duplicate.second << '\n'
            << "count(45): " << values.count(45) << '\n'
            << "values: " << values << '\n';

  values.erase(34);
  std::cout << "after erase, count(34): " << values.count(34)
            << '\n';
}

---

More to Explore

• Resolving collisions

• Open addressing (closed hashing)

• std::unordered_set

• std::unordered_map