I have implemented a very simple generic hash table library. For those that
are so inclined, I would like to request a critical review and comments. Is
anything wrong? Could anything be done better?
Thanks!
Dave
// File hash_table.h
#ifndef HASH_TABLE_INCLUDED
#define HASH_TABLE_INCLUDED
#include <list>
#include <vector>
namespace dct
{
// HASH_FUNC is a policy class which must have the following public
method:
// int hash(const ELEMENT_TYPE &element) const;
//
// This method must return an integer hash value for element.
template <typename ELEMENT_TYPE, int BUCKETS, typename HASH_FUNC>
class hash_table_t: public HASH_FUNC
{
public:
hash_table_t(): buckets(BUCKETS) {}
void clear();
void delete_element(const ELEMENT_TYPE &element);
bool element_exists(const ELEMENT_TYPE &element) const;
void insert_element(const ELEMENT_TYPE &element);
private:
typedef std::list<ELEMENT_TYPE> bucket_t;
typedef std::vector<bucket_t> buckets_t;
buckets_t buckets;
};
}
#include "hash_table.inl"
#endif
// File hash_table.inl
#include <algorithm>
namespace dct
{
//
************************************************** ************************
template <typename ELEMENT_TYPE, int BUCKETS, typename HASH_FUNC>
void hash_table_t<
ELEMENT_TYPE,
BUCKETS,
HASH_FUNC
::clear() {
for (typename buckets_t::size_type i = 0; i != buckets.size(); ++i)
buckets[i].clear();
} // hash_table_t::clear
//
************************************************** ************************
template <typename ELEMENT_TYPE, int BUCKETS, typename HASH_FUNC>
void hash_table_t<
ELEMENT_TYPE,
BUCKETS,
HASH_FUNC::delete_element(const ELEMENT_TYPE &element) {
typename buckets_t::size_type
bucket_idx(static_cast<typename buckets_t::size_type>(
HASH_FUNC::hash(element) %
BUCKETS)
);
bucket_t &bucket(buckets[bucket_idx]);
bucket.remove(element);
} // hash_table_t::delete_element
//
************************************************** ************************
template <typename ELEMENT_TYPE, int BUCKETS, typename HASH_FUNC>
bool hash_table_t<
ELEMENT_TYPE,
BUCKETS,
HASH_FUNC::element_exists(const ELEMENT_TYPE &element) const {
typename buckets_t::size_type
bucket_idx(static_cast<typename buckets_t::size_type>(
HASH_FUNC::hash(element) %
BUCKETS)
);
const bucket_t &bucket(buckets[bucket_idx]);
return find(bucket.begin(), bucket.end(), element) != bucket.end();
} // hash_table_t::element_exists
//
************************************************** ************************
template <typename ELEMENT_TYPE, int BUCKETS, typename HASH_FUNC>
void hash_table_t<
ELEMENT_TYPE,
BUCKETS,
HASH_FUNC::insert_element(const ELEMENT_TYPE &element)
{
typename buckets_t::size_type
bucket_idx(static_cast<typename buckets_t::size_type>(
HASH_FUNC::hash(element) %
BUCKETS)
);
bucket_t &bucket(buckets[bucket_idx]);
// Consciously allow an element to be inserted multiple times. This
is
// for the sake of efficiency. This operation becomes O(1) and,
assuming
// that recently inserted elements are referenced the most, lookups
will
// be quicker too since recent elements are close to the front of
their
// bucket.
bucket.push_front(element);
} // hash_table_t::insert_element
}