在C++里手动实现一个简单的哈希表，本质是构建一个数组作为桶，每个桶用链表解决哈希冲突，再通过哈希函数把键转换成数组下标。下面从结构定义到基本操作逐步说明。
一、设计哈希表的基本结构
我们使用链地址法，每一个桶存放一个单链表的头指针。节点中保存键值对，哈希函数采用取模方式。
1. 节点与哈希表类定义
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 链表节点
struct Node {
string key;
int value;
Node* next;
Node(string k, int v) : key(k), value(v), next(nullptr) {}
};
// 简单哈希表
class SimpleHashMap {
private:
vector<Node*> buckets;
int size;
int hashFunc(const string& key) {
int sum = 0;
for (char c : key) {
sum += c;
}
return sum % size;
}
public:
SimpleHashMap(int n) : size(n) {
buckets = vector<Node*>(size, nullptr);
}
~SimpleHashMap();
void put(string key, int value);
int get(string key);
void remove(string key);
};
二、实现插入、查找与删除
1. 插入逻辑
先算下标，若桶内无相同键则头插，有相同键则更新值。
void SimpleHashMap::put(string key, int value) {
int idx = hashFunc(key);
Node* head = buckets[idx];
while (head) {
if (head->key == key) {
head->value = value;
return;
}
head = head->next;
}
Node* newNode = new Node(key, value);
newNode->next = buckets[idx];
buckets[idx] = newNode;
}
2. 查找与删除
查找遍历对应桶的链表，删除需记录前驱节点。
int SimpleHashMap::get(string key) {
int idx = hashFunc(key);
Node* head = buckets[idx];
while (head) {
if (head->key == key) {
return head->value;
}
head = head->next;
}
return -1; // 未找到
}
void SimpleHashMap::remove(string key) {
int idx = hashFunc(key);
Node* head = buckets[idx];
Node* prev = nullptr;
while (head) {
if (head->key == key) {
if (prev) {
prev->next = head->next;
} else {
buckets[idx] = head->next;
}
delete head;
return;
}
prev = head;
head = head->next;
}
}
SimpleHashMap::~SimpleHashMap() {
for (int i = 0; i < size; i++) {
Node* head = buckets[i];
while (head) {
Node* tmp = head;
head = head->next;
delete tmp;
}
}
}
三、使用示例
下面代码演示如何创建表并做基本操作。
int main() {
SimpleHashMap map(10);
map.put("apple", 3);
map.put("banana", 5);
cout << map.get("apple") << endl;
map.remove("apple");
cout << map.get("apple") << endl;
return 0;
}
四、小结
手动实现HashMap关键在于选好哈希函数与冲突处理方式。上面例子用取模和链表，逻辑清晰但未做扩容。实际中当元素过多时应重建更大的桶数组以保证效率。