哈希表的C++模拟实现
一、闭散列实现哈希表
1.1 数据结构定义
在闭散列中，数据至少包含键值对和状态表示。键值对可以是 K 或 K / V，这里我们使用 K / V。
状态分为三种：
- 空
EMPTY - 存在
EXIST - 删除
DELETE
这些状态用于提高探测效率。存储数据结构可以用一个结构体定义：
// 节点状态
enum State
{
EMPTY,
EXIST,
DELETE
};
// 存储数据结构类
template<class K, class V>
struct HashData
{
std::pair<K, V> _kv; // 键值对
State _state = EMPTY; // 状态
};
哈希表的整体框架如下：
namespace Aron
{
template<class K, class V>
class HashTable
{
public:
// ...
private:
std::vector<HashData<K, V>> _tables; // 数据表
size_t _n; // 有效数据量（用于计算负载因子）
};
}
1.2 查找
查找过程通过线性探测来实现。如果当前位置为空，则停止探测，因为后面必然不存在目标数据。
HashData<K, V>* Find(const K& key)
{
if (_n == 0)
return nullptr;
size_t hashi = key % _tables.size();
size_t index = hashi;
while (_tables[index]._state != EMPTY)
{
if (key == _tables[index]._kv.first && _tables[index]._state == EXIST)
{
return &_tables[index];
}
++index;
index %= _tables.size();
if (index == hashi)
break;
}
return nullptr;
}
1.3 插入
插入前先判断该值是否已存在。如果不存在，则进行插入。插入步骤如下：
- 计算哈希值。
- 线性探测找到可用位置。
- 插入数据并更新有效数据量。
bool Insert(const std::pair<K, V>& kv)
{
if (Find(kv.first))
return false;
size_t hashi = kv.first % _tables.size();
int i = 0;
while (_tables[hashi]._state == EXIST)
{
hashi += i;
hashi %= _tables.size();
i++;
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
++_n;
return true;
}
1.4 删除
删除操作将节点状态改为 DELETE 并减少有效数据量。
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret)
{
_n--;
ret->_state = DELETE;
return true;
}
else
return false;
}
1.5 测试
测试查找和插入功能：
void TestHT1()
{
int a[] = { 3, 33, 2, 13, 5, 12, 1002 };
HashTable<int, int> ht;
for (auto e : a)
{
ht.Insert(std::make_pair(e, e));
}
ht.Insert(std::make_pair(15, 15));
if (ht.Find(13))
{
std::cout << "13在" << std::endl;
}
else
{
std::cout << "13不在" << std::endl;
}
}
二、开散列实现哈希表
2.1 数据结构定义
开散列使用单链表解决哈希冲突。存储节点结构如下：
template<class K, class V>
struct HashNode
{
HashNode<K, V>* _next; // 指向下一个节点
std::pair<K, V> _kv;
HashNode(const std::pair<K, V>& kv)
: _next(nullptr), _kv(kv) {}
};
哈希桶中的表存储类型为节点指针：
template<class K, class V>
class HashTable
{
typedef HashNode<K, V> Node;
public:
// ...
private:
std::vector<Node*> _tables;
size_t _n = 0; // 有效数据量
};
2.2 析构函数
析构时释放单链表中的节点：
~HashTable()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}
2.3 查找
查找过程定位到具体位置后遍历单链表：
Node* Find(const K& key)
{
if (_tables.size() == 0)
return nullptr;
size_t hashi = key % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
return cur;
cur = cur->_next;
}
return nullptr;
}
2.4 插入
插入时选择头插法，并在需要时进行扩容：
bool Insert(const std::pair<K, V>& kv)
{
if (Find(kv.first))
return false;
if (_n == _tables.size())
{
size_t newSize = _tables.size() == 0 ? 5 : _tables.size() * 2;
std::vector<Node*> newTables(newSize, nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = cur->_kv.first % newTables.size();
cur->_next = newTables[hashi];
newTables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
size_t hashi = kv.first % _tables.size();
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}
2.5 删除
删除操作通过单链表的删除方法实现：
bool Erase(const K& key)
{
size_t hashi = key % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
if (prev)
prev->_next = cur->_next;
else
_tables[hashi] = cur->_next;
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
2.6 桶的长度
检查哈希桶的最大高度：
size_t MaxBucketSize()
{
size_t max = 0;
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
size_t size = 0;
while (cur)
{
++size;
cur = cur->_next;
}
if (size > max)
max = size;
}
return max;
}
void TestHash3()
{
srand((size_t)time(nullptr));
HashTable<int, int> ht;
int n = 1000000;
for (int i = 0; i < n; i++)
{
int val = rand() + i;
ht.Insert(std::make_pair(val, val));
}
std::cout << ht.MaxBucketSize() << std::endl;
}
