ハッシュテーブル(Key値のみ)簡易版

3016 ワード

#include<iostream>
using namespace std;
enum Status
{
	EXIST,
	EMPTY,
	DELETE
};
template<class K>
class  HashTable
{
public:
	HashTable(int capacity)
		:_table(new K[capacity])
		, _capacity(capacity)
		, _size(0)
		, _statu(new Status[capacity])
	{
		memset(_table, 0, sizeof(K)*capacity);// , _statu
		for (int i = 0; i < capacity; ++i)
		{
			_statu[i] = EMPTY;
		}
	}
	~HashTable()
	{
		if (_table)
			delete[] _table;
		if (_statu)
			delete[] _statu;
		_size = 0;
		_capacity = 0;
	}

	bool Insert(const K& key)
	{
		if (_size * 10 / _capacity >= 7)// 0.7 0.8
		{
			size_t newCapacity = _capacity * 2;
			HashTable<K> tmp(newCapacity);
			for (int i = 0; i < _capacity; ++i)
			{
				if (_statu[i] == EXIST)
				{
					tmp.Insert(_table[i]);
				}
			}
			this->_Swap(tmp);// 
		}
		size_t index = _HashFunc(key, _capacity);
		size_t begin = index;
		do
		{
			if (_statu[index] == EMPTY||_statu[index]==DELETE)
				break;
			if (_statu[index] == EXIST&&_table[index]== key)
				return false;
			++index;
			if (index == _capacity)
				index = 0;
		} while (index != begin);
		if (_statu[index] == EXIST)// 
			return false;
		_table[index] = key;
		_statu[index] = EXIST;
		++_size;
		return true;
	}
	bool Find(const K& key)
	{
		size_t index = _HashFunc(key, _capacity);
		size_t begin = index;
		do
		{
			if (_statu[index] == EMPTY)
				break;
			if (_statu[index] == EXIST&&_table[index] == key)
				return true;
			++index;
			if (index == _capacity)
				index = 0;
		} while (index != begin);
		return false;
	}
	// 
	bool  Remove(const K& key)
	{
		size_t index = _HashFunc(key, _capacity);
		size_t begin = index;
		do
		{
			if (_statu[index] == EMPTY)
				break;
			if (_statu[index] == EXIST&&_table[index] == key)
			{
				_statu[index] = DELETE;
				--_size;
				return true;
			}
			++index;
			if (index == _capacity)
				index = 0;
		} while (index != begin);
		return false;
	}
	void Print()
	{
		for (int i = 0; i < _capacity; ++i)
		{
			printf("%d:%d-->", _table[i], _statu[i]);
		}
		cout << endl;
	}
protected:
	size_t _HashFunc(const K& key, size_t capacity)
	{
		return key%capacity;// 
	}
	void _Swap(HashTable<K>& hs)
	{
		swap(_table, hs._table);
		swap(_capacity, hs._capacity);
		swap(_size, hs._size);
		swap(_statu, hs._statu);
	}
protected:
	K* _table;
	size_t _capacity;
	size_t _size;
	Status* _statu;
};
void Test1()
{
	HashTable<int> hs(10);
	hs.Insert(1);
	hs.Insert(11);
	hs.Insert(2);
	hs.Insert(3);
	hs.Insert(6);
	hs.Insert(9);
	hs.Insert(12);
	hs.Insert(8);
	cout << "Find(1)" << hs.Find(1) << "Find(7)" << hs.Find(7) 
		<< "Find(11)" << hs.Find(11) << endl;
	hs.Print();
	cout << "Remove(11)" << hs.Remove(11) << "Remove(0)" << hs.Remove(0) << endl;
	cout << "Find(11)" << hs.Find(11) << endl;
}