{
_tables[i] = h._tables[i];
_states[i] = h._states[i];
}
}
HashTable& operator=(HashTable h)//赋值运算符重载
{
if (this != &h)
{
swap(_tables, h._tables);
swap(_states, h._states);
swap(_capacity, h._capacity);
swap(_size, h._size);
}
return *this;
}
//bool Insert(const T& key)//插入（线性探测）
//{
//_CheckCapacity();
//int index = _HashFunc(key);
//int start = index;
//while (_states[index]==EXITS)
//{
//if (_tables[index] == key)
//{
//return false;
//}
//index++;
//if (index == _capacity)
//{
//index = 0;
//}
//if (index == start)
//{
//return false;
//}
//
//}
//_tables[index] = key;
//_states[index] = EXITS;
//_size++;
//}
bool Insert(const T& key)//插入（二次探测,即某个数的二次方,这样数据存着更稀疏）
{
_CheckCapacity();
int index = _HashFunc(key);
int start = index;
int i = 0;
while (_states[index]==EXITS)
{
if (_tables[index] == key)
{
return false;
}
index = _HashFuncT(index, ++i);
if (start = index)
{
return false;
}
if (index == _capacity)
{
index = 0;
}
}
_tables[index] = key;
_states[index] = EXITS;
_size++;
}
bool Find(const T& key)//查找
{
int index = _HashFunc(key);
int start = index;
int i = 0;
while (_states[index]!=EMPTY)
{
if (_tables[index] == key)
{
if (_states[index] != DELETE)
{
cout << "find success" << endl;
return true;
}
else
{
cout << "find fail" << endl;
return false;
}
}
index = _HashFuncT(index, ++i);
if (start = index)
{
cout << "find fail" << endl;
return false;
}
if (index == _capacity)
{
index = 0;
}
}
cout << "find fail" << endl;
return false;
}
bool Remove(const T& key)///删除
{
int index = _HashFunc(key);
int start = index;
int i = 0;
while (_states[index] == EXITS)
{
if (_tables[index] == key)
{
_states[index] = DELETE;
_size--;
return true;
}
index = _HashFuncT(index, ++i);
if (start == index)
{
return false;
}
if (index == _capacity)
{
index = 0;
}
}
return false;
}
void Print()//打印哈希表
{
for (int i = 0; i < _capacity; i++)
{
cout << '[' << _tables[i] << ',' << _states[i] << ']' << ' ';
}
cout << endl;
}
protected:
int _HashFuncT(int index,int i)
{
return (index + i*i) % _capacity;
}
int _HashFunc(const T& key)
{
return key%_capacity;
}
void _CheckCapacity()//检查容量
{
if ((10 * _size)/ _capacity == 6)//负载因子设为0.6
{
HashTable tmp(2 * _capacity);
for (int i = 0; i < _capacity; i++)
{
if (_states[i]==EXITS)
{
tmp.Insert(_tables[i]);
}
}
_swap(tmp);
}
}
void _swap(HashTable h)
{
swap(_tables, h._tables);
swap(_states, h._states);
swap(_capacity, h._capacity);
swap(_size, h._size);
}
private:
size_t _capacity;
T* _tables;
State* _states;
size_t _size;
};
}
/****************************************/
上面的代码对于key形式的相对第一种已经比较健全了。现在可以利用哈希算法可以实现一种key/value形式的功能，可以支持字典功能，key是一个信息，同时value是key的一个附带信息，比如说key为学号，那么班级就是附带的信息value，例如还有简单的英汉字典形式，现进行简单的实现。
namespace Third//支持字典形式的
{
enum State
{
EMPTY,
DELETE,
EXITS
};
template
struct HashTableNode
{
HashTableNode()
{}
HashTableNode(const T& key, const V& value)
:_key(key)
, _value(value)
{}
T _key;
V _value;
};
template
struct __HashFunc
{
size_t operator()(const T& key)
{
return key;
}
};
//实现key，value形式，并且是二次探测的
template >
class Dictionary
{
public:
Dictionary(size_t capacity=10)
:_capacity(capacity)
, _tables(new HashTableNode [_capacity])
, _states(new State[_capacity])
,_size(0)
{
for (int i = 0; i < _capacity; i++)
{
_states[i] = EMPTY;//将最开始的状态置为空
}
}
~Dictionary()
{
delete[] _tables;
delete[] _states;
}
bool Insert(const T& key,const V& value)
{
_CheckCapacity();
int index = _HashFunonce(key);
int start = index;
int i = 0;
while (_states[index] == EXITS)
{
if (_tables[index]._key == key)
{
return false;
}
index = _HashFuntwice(index, ++i);
if (index == _capacity)
{
index = 0;
}
if (index == start)
{
return false;
}
}
_tables[index] = HashTableNode(key, value);
_states[index] = EXITS;
_size++;
return true;
}
HashTableNode* Find(const T& key)
{
int index = _HashFunonce(key);
int start = index;
int i = 0;
while (_states[index]==EXITS)
{
if (_tables[index]._key == key)
{
cout << "find success" << endl;
return _tables+index;
}
index = _HashFuntwice(index, ++i);
if (start == index)
{
cout << "find fail" << endl;
return NULL;
}
}
cout << "find fail" << endl;
return NULL;
}
bool Remove(const T& key)
{
int index = _HashFunonce(key);
int start = index;
int i = 0;
while (_states[index]!=EMPTY)
{
if (_tables[index]._key == key)
{
if (_states[index]!=DELETE)
{
_states[index] = DELETE;
_size--;
return true;
}
else
{
return false;
}
}
index = _HashFuntwice(index, ++i);
if (index == start)
{
return false;
}
}
return false;
}
void Print()
{
for (int i = 0; i < _capacity; i++)
{
cout << "[" << _tables[i]._key << "," << _tables[i]._value <<","<< _states[i]<<"]" << " ";
}
cout << endl;
}
protected:
void _CheckCapacity()//将负载因子设为0.6
{
if (_size * 10 / _capacity == 6)
{
Dictionary tmp(2 * _capacity);
for (int i = 0; i < _capacity; i++)
{
if (_states[i] == EXITS)
{
tmp.Insert(_tables[i]._key,_tables[i]._value);
}
}
_Swap(tmp);
}
}
void _Swap(Dictionary tmp)
{
swap(_tables, tmp._tables);
swap(_states, tmp._states);
swap(_capacity, tmp._capacity);
swap(_size, tmp._size);
}
size_t _HashFunonce(const T& key)
{
return key %_capacity;
}
size_t _HashFuntwice(int index,int i)//获取二次探测的下标
{
return (index + i*i) % _capacity;
}
private:
size_t _capacity;
HashTableNode* _tables;
State* _states;
size_t _size;
};
}
void test3()//二次探测，负载因子，实现字典的功能
{
/*Third::Dictionary h2;
h2.Insert(10, "c语言基础");
h2.Insert(59, "c++基础");
h2.Insert(9, "数据结构");
h2.Insert(19, "Linux");
h2.Insert(18, "网络编程");*/
Third::Dictionaryh2;
h2.Insert(10, 1);
h2.Insert(59, 2);
h2.Insert(9, 3);
h2.Insert(19,4);
h2.Insert(18, 5);
//h2.Print();
cout<_value<//h2.Remove(9);
//h2.Remove(19);
//h2.Remove(10);
//h2.Print();
}
上述就是对哈希算法的简单应用。
名称栏目：哈希表的静态，动态，以及key/value形式
本文网址：http://cdkjz.cn/article/jepjsg.html
