Simple Hash Table generic implementation using templates. The underlying collection for storing hash collisions is a binary search tree.

hash.h

#ifndef DANI_SIMPLE_HASHTABLE_H_
#define DANI_SIMPLE_HASHTABLE_H_

/*
  Simple Hash Table generic implementation using templates.
  The underlying collection for storing hash collisions is a binary search tree.

  Depends: tree.h (see github for newest version).

  Author: Daniela Petruzalek (https://gist.github.com/danicat)
  Date  : October, 20th 2013
*/

#include <iostream>

#include "tree.h"

namespace dani {

template <class T>
class HashTable {
 public:
  HashTable(const int& num_entries, int (*hash_function)(const T&, const int&) ) : entries_(num_entries), hash_function_(hash_function) {
    table_ = new (std::nothrow) BinarySearchTree<T>[num_entries];
  }
  ~HashTable() {
    delete[] table_;
  }

  bool Insert(const T& value) {
    if( !hash_function_ )
      return true; // Error! Null function pointer

    return table_[hash_function_(value, entries_)].Insert(value);
  }

  void Print() const {
    for(int i = 0; i < entries_; ++i) {
      if( table_[i].GetRoot() ) { // Tree not empty
        std::cout << "Hash value " << i << " contains: " << std::endl;
        table_[i].PrintBreadthSearchFirst();
      }
    }
  }

 private:
   int entries_;

   BinarySearchTree<T>* table_;

   int (*hash_function_)(const T& value, const int& num_entries);
};

}

#endif // DANI_SIMPLE_HASHTABLE_H_