c++如何不用stl实现哈希表
时间: 2023-08-22 20:08:59 浏览: 67
要在C++中实现哈希表,可以通过以下步骤进行:
1. 定义一个哈希函数,将键(key)映射到哈希表中的索引。哈希函数应该是高效的,尽可能地减少哈希冲突。
2. 定义一个数组,用于存储哈希表中的元素(键值对)。
3. 在数组中插入一个元素时,先使用哈希函数计算出该元素的索引,然后将元素插入到该索引处。如果该索引处已经有元素,则需要解决哈希冲突,例如使用开放寻址法或链表法。
4. 在数组中查找一个元素时,同样使用哈希函数计算出该元素的索引,然后在该索引处查找元素。如果该索引处没有元素,则说明该元素不在哈希表中。
以下是一个简单的示例代码,演示了如何实现一个基本的哈希表,其中使用了开放寻址法来解决哈希冲突:
```c++
#include <iostream>
const int TABLE_SIZE = 128;
class HashTable {
private:
struct Node {
int key;
int value;
bool is_deleted; // 标记是否被删除
};
Node table[TABLE_SIZE];
// 哈希函数
int hash(int key) const {
return key % TABLE_SIZE;
}
public:
HashTable() {
for (int i = 0; i < TABLE_SIZE; ++i) {
table[i].key = -1;
table[i].value = -1;
table[i].is_deleted = false;
}
}
// 插入元素
void insert(int key, int value) {
int index = hash(key);
while (table[index].key != -1 && table[index].is_deleted == false) {
// 线性探测
index = (index + 1) % TABLE_SIZE;
}
table[index].key = key;
table[index].value = value;
table[index].is_deleted = false;
}
// 查找元素
int find(int key) const {
int index = hash(key);
while (table[index].key != -1) {
if (table[index].key == key && table[index].is_deleted == false) {
return table[index].value;
}
index = (index + 1) % TABLE_SIZE;
}
return -1;
}
// 删除元素
void remove(int key) {
int index = hash(key);
while (table[index].key != -1) {
if (table[index].key == key && table[index].is_deleted == false) {
table[index].is_deleted = true;
return;
}
index = (index + 1) % TABLE_SIZE;
}
}
};
int main() {
HashTable ht;
ht.insert(1, 10);
ht.insert(2, 20);
ht.insert(3, 30);
std::cout << ht.find(2) << std::endl; // 输出 20
ht.remove(2);
std::cout << ht.find(2) << std::endl; // 输出 -1
return 0;
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)