帮我使用C++实现哈希表并对外提供创建和增删改查功能的接口,不要调用自带的库函数
时间: 2024-09-21 11:01:19 浏览: 61
C++实现的同义词林相似度计算库,可供python、java等其它语言调用.zip
在C++中,我们可以手动实现哈希表,也称为关联数组或字典,通常通过使用数组和链表来存储元素。这里是一个简单的示例,我们将实现一个基本的哈希表,包含`HashTable`类,提供`insert`, `find`, `delete`, 和 `update` 函数:
```cpp
#include <iostream>
#include <vector>
class Node {
public:
int key;
int value;
Node* next;
Node(int k, int v) : key(k), value(v), next(nullptr) {}
};
class HashTable {
private:
const static int TABLE_SIZE = 10;
std::vector<Node*> table[TABLE_SIZE];
unsigned hashFunction(const int& key) {
return key % TABLE_SIZE;
}
public:
void insert(int key, int value) {
auto index = hashFunction(key);
if (!table[index]) {
table[index] = new Node(key, value);
} else {
for (Node* node = table[index]; node; node = node->next) {
if (node->key == key) {
node->value = value;
break;
}
}
if (!node) {
node = new Node(key, value);
node->next = table[index];
table[index] = node;
}
}
}
bool find(int key, int& value) {
auto index = hashFunction(key);
for (Node* node = table[index]; node; node = node->next) {
if (node->key == key) {
value = node->value;
return true;
}
}
value = -1; // 表示未找到
return false;
}
void update(int key, int new_value) {
if (find(key, new_value)) {
table[hashFunction(key)] = nullptr; // 首先删除旧节点
insert(key, new_value); // 然后插入新值
}
}
void deleteItem(int key) {
auto index = hashFunction(key);
for (Node** node = &table[index]; *node; ) {
Node* temp = *node;
*node = (*node)->next;
delete temp;
if (*node && (*node)->key == key) {
// 如果删除后还有同名键,则需要继续搜索
return;
}
}
}
};
int main() {
HashTable ht;
ht.insert(5, 10);
ht.insert(7, 20);
int foundValue;
std::cout << "Find key 5: " << (ht.find(5, foundValue) ? "Found, value: " + std::to_string(foundValue) : "Not found") << std::endl;
ht.update(5, 15);
std::cout << "Update key 5 to 15: " << (ht.find(5, foundValue) ? "Found, updated value: " + std::to_string(foundValue) : "Not found") << std::endl;
ht.deleteItem(7);
return 0;
}
```
这个例子中,我们只实现了最基础的功能,并没有处理冲突(当两个键映射到同一个位置)。实际应用中,你可能会选择更复杂的解决冲突策略,如开放寻址法或链地址法。
阅读全文