在C++中實現Hashtable可以使用標準庫中的unordered_map或者自己實現一個Hashtable類。以下是一個簡單的自定義Hashtable類的實現示例:
#include <iostream>
#include <vector>
#include <list>
class Hashtable {
private:
static const int TABLE_SIZE = 10;
std::vector<std::list<std::pair<int, int>>> table;
int hashFunction(int key) {
return key % TABLE_SIZE;
}
public:
Hashtable() {
table.resize(TABLE_SIZE);
}
void insert(int key, int value) {
int index = hashFunction(key);
for (auto& pair : table[index]) {
if (pair.first == key) {
pair.second = value;
return;
}
}
table[index].push_back({key, value});
}
void remove(int key) {
int index = hashFunction(key);
table[index].remove_if([key](std::pair<int, int> pair) { return pair.first == key; });
}
int get(int key) {
int index = hashFunction(key);
for (auto& pair : table[index]) {
if (pair.first == key) {
return pair.second;
}
}
return -1; // key not found
}
};
int main() {
Hashtable ht;
ht.insert(1, 10);
ht.insert(2, 20);
std::cout << ht.get(1) << std::endl; // Output: 10
std::cout << ht.get(2) << std::endl; // Output: 20
ht.remove(1);
std::cout << ht.get(1) << std::endl; // Output: -1 (key not found)
return 0;
}
在這個例子中,我們使用一個vector來存儲鏈表,每個鏈表存儲具有相同hash值的鍵值對。我們實現了插入、刪除和獲取操作。實際上,C++標準庫中的unordered_map就是使用類似的哈希表實現的。