用C或C++ 实现 一个 哈希表
时间: 2023-11-22 13:53:47 浏览: 44
好的,你可以使用C或C++来实现一个哈希表。哈希表是一种非常常见的数据结构,它提供了非常高效的插入,查找和删除操作。它是由一个数组和一个哈希函数构成的。哈希函数将数据转换为数组索引,使得每个元素都可以在常数时间内访问。以下是一个简单的C++实现示例:
```c++
#include <iostream>
#include <vector>
using namespace std;
class HashTable {
private:
vector<pair<int, int>>* table;
int size;
public:
HashTable(int size) {
this->size = size;
table = new vector<pair<int, int>>[size];
}
~HashTable() {
delete[] table;
}
void insert(int key, int value) {
int index = hash(key);
table[index].push_back(make_pair(key, value));
}
int get(int key) {
int index = hash(key);
for (auto it = table[index].begin(); it != table[index].end(); it++) {
if ((*it).first == key) {
return (*it).second;
}
}
return -1; // If key is not found
}
void remove(int key) {
int index = hash(key);
for (auto it = table[index].begin(); it != table[index].end(); it++) {
if ((*it).first == key) {
table[index].erase(it);
return;
}
}
}
private:
int hash(int key) {
return key % size;
}
};
int main() {
HashTable ht(10);
ht.insert(1, 10);
ht.insert(2, 20);
ht.insert(3, 30);
cout << ht.get(1) << endl; // Output: 10
cout << ht.get(2) << endl; // Output: 20
cout << ht.get(3) << endl; // Output: 30
ht.remove(2);
cout << ht.get(2) << endl; // Output: -1
return 0;
}
```
这个实现采用了向量存储桶,其中每个桶包含一对键值对。插入,获取和删除操作都采用哈希函数计算键的索引。这个实现并不是完整的,还可以添加更多的操作,例如调整表的大小等。