#pragma once
#include
#include
using namespace std;
enum State
{
EMPTY,
DELETE,
EXIST,
};
template
struct HashTableNode
{
K _key;
V _value;
};
template
struct __HashFunc //默认的返回哈希键值key的 仿函数
{
size_t operator()(const K& key)
{
return key;
}
};
//特化string的__HashFunc 仿函数
template<>
struct __HashFunc
{
size_t operator()(const string& str)
{
size_t key = 0;
for (size_t i = 0; i < str.size(); i++)
{
key += str[i];
}
return key;
}
};
//实现哈希表的Key/Value形式的二次探测
template>
class HashTable
{
typedef HashTableNode Node;
public:
HashTable(size_t capacity = 10)
:_tables(new Node[capacity])
, _size(0)
, _states(new State[capacity])
, _capacity(capacity)
{
// memset 有问题 是以字节为单位初始化的 但第二个参数值为int
//memset(_states, EMPTY, sizeof(State) * capacity);
for (size_t i = 0; i < capacity; i++)
{
_states[i] = EMPTY;
}
}
~HashTable()
{
if (NULL != _tables)
{
delete[] _tables;
_tables = NULL;
}
if (NULL != _states)
{
delete[] _states;
_states = NULL;
}
}
bool Insert(const K& key, const V& value)
{
_CheckCapacity();
//用GetNextIndex 解决哈希冲突
size_t index = _HashFunc(key);
// 二次探测
size_t i = 1;
while (_states[index] == EXIST)
{
index = _GetNextIndex(index, i++);
if (index >= _capacity)
{
index = index % _capacity;
}
}
_tables[index]._key = key;
_tables[index]._value = value;
_states[index] = EXIST;
_size++;
return true;
}
Node* Find(const K& key)
{
size_t index = _HashFunc(key);
size_t start = index;
size_t i = 1;
// 存在 或者 被删除 两种状态
while (_states[index] != EMPTY)
{
if (_tables[index]._key == key)
{
if (_states[index] == EXIST)
{
return index;
}
else // 被删除 DELETE
{
return -1;
}
}
index = _GetNextIndex(index, i++);
if (index >= _capacity)
{
index = index % _capacity;
}
// 因为有填充因子 不为100% 不会出现全满且key！=_key 导致死循环的情况
}
return -1;
}
bool Remove(const K& key)
{
int index = Find(key);
if (index != -1)
{
_states[index] = DELETE;
--_size;
return true;
}
return false;
}
// 二次探测计算出存放位置
size_t _HashFunc(const K& key)
{
HashFunc hf;
return hf(key) % _capacity; // 仿函数hf()
}
// 哈希冲突时 得到下一个index的可以利用上一个index的值 这样能提高效率 比如 string的index计算就比较费时
size_t _GetNextIndex(size_t prev, size_t i)
{
return prev + 2 * i - 1;
}
void Print()
{
for (size_t i = 0; i < _capacity; i++)
{
if (_states[i] == EXIST)
{
cout << i << "EXIST:" << _tables[i]._key << "-------" << _tables[i]._value << endl;
}
else if (_states[i] == DELETE)
{
cout << i << "DELETE:" << _tables[i]._key << "-------" << _tables[i]._value << endl;
}
else
{
cout << i << "EMPTY:" << _tables[i]._key << "-------" << _tables[i]._value << endl;
}
}
}
void Swap(HashTable& ht)
{
swap(_size, ht._size);
swap(_states, ht._states);
swap(_tables, ht._tables);
swap(_capacity, ht._capacity);
}
protected:
void _CheckCapacity() // 扩容
{
// 动态的 可扩容的
// 高效哈希表的载荷因子大概在0.7-0.8较好
if (10 * _size / _capacity >= 7) // _size/_capacity为0 因为都是××× 所以乘10
// 保证载荷因子在0.7之内
{
HashTable tmp(2 * _capacity);
for (size_t i = 0; i < _capacity; i++)
{
if (_states[i] == EXIST)
{
tmp.Insert(_tables[i]._key, _tables[i]._value);
}
}
Swap(tmp);
}
}
protected:
Node* _tables;
State* _states;//状态表
size_t _size;
size_t _capacity;
};
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
成都创新互联公司主打移动网站、
做网站、成都网站设计、网站改版、网络推广、网站维护、
域名申请、等互联网信息服务，为各行业提供服务。在技术实力的保障下，我们为客户承诺稳定，放心的服务，根据网站的内容与功能再决定采用什么样的设计。最后，要实现符合网站需求的内容、功能与设计，我们还会规划稳定安全的技术方案做保障。
本文题目：哈希表（散列表）二次探测-创新互联
文章起源：
http://bzwzjz.com/article/djiodp.html
