ハッシュテーブル(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;
}