Are there any problems with this?

[Dave]

Hello all,

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.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
}

 

[Allan Bruce]

Hello all,

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

<code snipped>

How about adding an Iterator to it? I have made my own hash table recently
and found it useful to add the iterator. Also, I know this wouldnt be
portable, but remember to keep the hashtable threadsafe.
Allan