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;
};