hashtable.h

字符频度统计

#ifndef HASH_TABLE_CLASS
#define HASH_TABLE_CLASS

#include "Array.h"
#include "LinkedList.h"
#include "CharNode.h"

static unsigned long hashfunc(const CharNode & cn)
{
	return ((int)cn.ch)%11;
}

template <class T>
class HashTable
{
protected:
	int bucketNum;
	Array<LinkedList<T> >buckets;
	unsigned long (*hf)(const T & key);

public:
	HashTable(int nbuckets,
		unsigned long hahsf(const T & key));
	~HashTable();
	void Insert(const T & key);
	ListNode<T> * Find(const T & key);
	void Delete(const T & key);
	void ClearList(void);
	void Update(const T & key);

	friend ostream & operator<<(ostream & os,const HashTable<T> & h);
};

template <class T>
HashTable<T>::HashTable(int nbuckets,unsigned long hashf(const T & key))
:bucketNum(nbuckets),buckets(bucketNum),hf(hashf)
{}

template <class T>
HashTable<T>::~HashTable()
{
	ClearList();
}

template <class T>
void HashTable<T>::Insert(const T & key)
{
	int hashval=int(hf(key)%bucketNum);
	LinkedList<T> & lst=buckets[hashval];
	if(lst.FindItem(key)==NULL)
		lst.InsertRear(key);
}

template <class T>
ListNode<T> * HashTable<T>::Find(const T & key)
{
	int hashval=int(hf(key)%bucketNum);
	LinkedList<T> & lst=buckets[hashval];
	return lst.FindItem(key);
}

template <class T>
void HashTable<T>::Update(const T & key)
{
	int hashval=int(hf(key)%bucketNum);
	LinkedList<T> & lst=buckets[hashval];
	if(lst.FindItem(key)!=NULL)
	{
		ListNode<T> *node=lst.FindItem(key);
		++node->data;
	}
}

template <class T>
void HashTable<T>::Delete(const T & key)
{
	int hashval=int(hf(key)%bucketNum);
	LinkedList<T> & lst=buckets[hashval];
	if(lst.FindItem(key)!=NULL)
		lst.Remove(key);
}

template <class T>
void HashTable<T>::ClearList()
{
	for(int i=0;i<bucketNum;i++)
		buckets[i].ClearList();
}


template <class T>
ostream & operator<<(ostream & os,const HashTable<T> & h)
{
	for(int i=0;i<h.bucketNum;i++)
	{
		if(h.buckets[i].IsEmpty())
			continue;
		os<<"Bucket"<<i<<endl;
		os<<h.buckets[i]<<endl;
	}
	return os;
}

#endif