hash_table.h

采用迭代器模式实现hash算法

#ifndef __HASHTABLE_INCLUDE
#define __HASHTABLE_INCLUDE

/*******************************************
 * author: 李国强
 * date: 2006-1-10
 * desc: 实现HASH表,每个桶采用链表实现
 * 
 ******************************************/
#include "config_types.h"
#include "hash_fun.h"           //HASH函数
#pragma warning(disable:4284)

/******************************************
 * HASH表的链表节点,节点保存KEY和VALUE
 *****************************************/
template<typename KEY, typename ITEM>
struct HashItem
{
	KEY  key_;
	ITEM val_;
};
template<typename KEY, typename ITEM >
struct HashNode
{
    HashItem<KEY, ITEM>  item_;
	HashNode<KEY, ITEM>* next_;
};

template<typename KEY, typename ITEM > class HashTable;
/******************************************
 * HASH 迭代器基类,提供常用的方法
 *****************************************/
template<typename KEY, typename ITEM >
class HashIteratorBase
{
public:
    typedef HashTable<KEY, ITEM>* HashPtr;
	typedef HashNode<KEY, ITEM>*  NodePtr;
public:
    explicit HashIteratorBase(HashPtr hash, NodePtr node) //缺省构造函数
        : hash_table_(hash), cur_node_(node)
    {
    }
protected:
    HashPtr hash_table_;
	NodePtr cur_node_;
};
/******************************************
 * HASH 迭代器从基类派生,实现基类方法
 *****************************************/
template<typename KEY, typename ITEM >
class HashIterator : public HashIteratorBase<KEY, ITEM>
{
    typedef HashIterator<KEY, ITEM> Self;
    typedef HashItem<KEY, ITEM>     ThrItem;
	typedef typename HashIteratorBase<KEY, ITEM>::HashPtr HashPtr;
	typedef typename HashIteratorBase<KEY, ITEM>::NodePtr NodePtr;
    typedef ThrItem*                ItemPtr;
    typedef ThrItem&                ItemRef;
public:
	typedef size_t size_type;
	
	explicit HashIterator()                             //缺省构造函数
		: HashIteratorBase<KEY, ITEM>(0, 0) {}
    explicit HashIterator (HashPtr hash, NodePtr node)
        : HashIteratorBase<KEY, ITEM>(hash, node){}
    HashIterator (const Self& obj)    //拷贝构造函数
        : HashIteratorBase<KEY, ITEM>(obj.hash_table_, obj.cur_node_) {}

    Self& operator = (const Self& obj);         //赋值操作符
    bool  operator == (const Self& obj) const;  //比较操作符,等式
    bool  operator != (const Self& obj) const;  //比较操作符,不等式
    Self& operator ++ (void);
    Self  operator ++ (int);
    ItemPtr operator -> (void) const;
    ItemRef operator * (void);
};
/******************************************
 * HASH 表,带两个模板参数,第一个为链表节点
 * 第二个模板为保持节点的链表
 * 用户可以通过输入修改默认的模板参数
 * 加同步机制,但具体由使用者决定。
 *****************************************/
template<typename KEY, typename ITEM >
class HashTable
{
public:
    typedef KEY             Key;
    typedef ITEM            Value;
    typedef HashIterator<KEY, ITEM> Iterator;
	typedef typename Iterator::size_type    size_type;
    typedef HashTable<Key, Value >   Self;
    typedef HashFunc<Key>            KeyFunc;   //HASH函数
    typedef HashNode<Key, Value>     ThrNode;
    typedef ThrNode*                 NodePtr;
    typedef ThrNode&                 NodeRef;

	friend class HashIterator<Key, Value>;   //指定友元类      

    explicit HashTable(size_type buckets = 1024); //缺省
    HashTable(const Self& obj);       //拷贝构造函数
    ~HashTable();

    Self& operator = (const Self& obj);        //赋值操作符
    
    Iterator begin () const;                         //开始迭代器
    Iterator end () const;                           //结束迭代器
	
    size_type   size ()const;                          //当前总元素
    size_type   bucket_count()const;                   //当前被占用的桶数
    size_type   bucket_elems(size_type bucket)const;      //指定的桶中的元素个数
    size_type   bucket_pos(const Key& key) const;       //根据KEY返回所处的桶位置

    Iterator insert (const Key& key, const Value& val); //根据key插入对象
    void     insert (const Iterator& first, const Iterator& last);
	
    Iterator find (const Key& key) const;           //根据KEY值进行查找
    
    size_type   erase (const Key& key);
	size_type   erase (const Iterator& it);
	size_type   erase (const Iterator& first, const Iterator& last);
	
	void     clear ();
    void     clear_bucket(size_type bucket);     //清空给定桶中的元素
private:
    size_type   get_key_num (const Key& key) const   //根据KEY值生成索引
    { return key_func_(key); }
	const NodePtr  end_node () const              //标识一个链表的末尾
	{	return (NodePtr)0;	}
	NodePtr  create_node ()                 //构造一个新节点,目前只是简单的new
	{	return new ThrNode;	}
	void     release_node (NodePtr node)    //释放一个节点
	{	delete node; elements_--; }
	void     init_buckets();
	void     unini_buckets();
private:
    size_type   bucket_size_;  //桶数组的边界
    size_type   elements_;     //总元素个数
    NodePtr* buckets_;      //桶数组,双指针
    KeyFunc  key_func_;     //实例化HASH函数
};

#include "hash_table.inl"

#ifdef UNITTEST
#include <cppunit/extensions/HelperMacros.h>
class HashTableTest : public CPPUNIT_NS::TestFixture
{
public:
    CPPUNIT_TEST_SUITE(HashTableTest);
        CPPUNIT_TEST(test_hashtable);
    CPPUNIT_TEST_SUITE_END();
public:
    void setUp();
    void tearDown();
    void test_hashtable();
};
#endif

#endif