C++でハシバケツを実現(挿入、削除、検索)

3112 ワード

#include<iostream>
#include<vector>
#include<string>

using namespace std;
struct DefaultHashFuncString   //     
{
	size_t operator()(const string & key)
	{
		size_t ret = 0;
		for (size_t i = 0; i < key.size(); i++)
		{
			ret += key[i];
		}
		return ret;
	}
};
template<class K>
struct DefaultHashFunc  //     
{
	size_t operator()(const K & key)
	{
		return key;
	}
};
template<class K,class V>

struct HashTableNode  //     
{
	K _key;
	V _value;
	HashTableNode *_next;
};
template<class K, class V, class HashFunc = DefaultHashFunc<K>>
class HashTable
{
	typedef HashTableNode<K,V> Node;
public:
	HashTable(size_t size = 10)
		:_size(0)
	{
		_table.resize(size);
	}
	~HashTable()
	{
		for (size_t i = 0; i < _table.size(); i++)
		{
			Node *cur = _table[i];
			while (cur)
			{
				Node* tmp = cur;
				cur = cur->_next;
				delete tmp;
			}
		}
		_size = 0;
	}
public:
	void Insert(const K &key,const V& value) //  
	{
		_CheckCapacity();
		size_t index = HashFun(key);
		Node *cur = _table[index];
		if (cur)
		{
			while (cur->_next)
			{
				cur = cur->_next;
			}
			cur->_next = new Node;
			cur = cur->_next;
			cur->_key = key;
			cur->_value = value;
			cur->_next = NULL;
		}
		else
		{
			_table[index] = new Node;
			_table[index]->_key = key;
			_table[index]->_value = value;
			_table[index]->_next = NULL;
		}
		++_size;
	}
	Node * Find(const K& key)  //  
	{
		size_t index = HashFun(key);
		Node *cur = _table[index];
		while (cur)
		{
			if (cur->_key == key)
			{
				return cur;
			}
			cur = cur->_next;
		}
		return NULL;
	}
	bool Remove(const K& key)  //  
	{
		size_t index = HashFun(key);
		Node *cur = _table[index];
		if (!cur)
		{
			return false;
		}
		else if (cur->_next == NULL)
		{
			delete cur;
			_table[i] = NULL;
			return true;
		}
		else
		{
			Node * prev = cur;
			cur = cur->_next;
			while (cur)
			{
				if (cur->_key == key)
				{
					Node tmp = cur;
					cur = cur->_next;
					prev->next = tmp->_next;
					return true;
				}
			}
		}
	}
	void Printf()
	{
		for (size_t i = 0; i < _table.size(); i++)
		{
			printf("_table[%d]:", i);
			Node *cur = _table[i];
			while (cur)
			{
				cout << cur->_key << "->";
				cur = cur->_next;
			}
			cout << "NULL"<<endl;
		}
	}
protected:
	size_t HashFun(const K & key)  //  index
	{
		return HashFunc()(key) % _table.size();
	}
	void _CheckCapacity()  //    <span style="font-family: Arial, Helvetica, sans-serif;">(    )</span>
	{
		if (_size >= _table.size())
		{
			size_t size = 2 * _size;
			HashTable<K,V>tmp;/* = new Node[size];*/
			tmp._table.resize(size);
			for (size_t i = 0; i < _table.size(); i++)
			{
				Node *cur = _table[i];
				while (cur)
				{
					tmp.Insert(cur->_key,cur->_value);
					cur = cur->_next;
				}
			}
			_table.swap(tmp._table);
		}
	}
protected:
	vector<Node*> _table;
	size_t _size;
};