实现C++经典hashmap_c++实现hashmap

C++经典hash是指使用哈希表实现的一种数据结构，可以快速地存储、查找和删除数据。在C++中，可以使用STL中的unordered_map或者手写哈希表来实现。

关于C++经典hash的一些知识点包括：

哈希函数：将关键字映射到哈希表中的索引位置的函数。常见的哈希函数包括取模法、乘法哈希、MD5等。

哈希冲突：当两个不同的关键字被映射到同一个哈希表索引位置时，就会发生哈希冲突。解决哈希冲突的方法有开放地址法、链表法、再哈希法等。

#include <iostream>
#include <string>

using namespace std;

const int TABLE_SIZE = 100;

class HashNode {
public:
    string key;
    int value;
    HashNode* next;

    HashNode(string key, int value) {
        this->key = key;
        this->value = value;
        this->next = nullptr;
    }
};

class HashMap {
private:
    HashNode** table;
public:
    HashMap() {
        table = new HashNode*[TABLE_SIZE];
        for (int i = 0; i < TABLE_SIZE; i++) {
            table[i] = nullptr;
        }
    }

    ~HashMap() {
        for (int i = 0; i < TABLE_SIZE; i++) {
            HashNode* entry = table[i];
            while (entry != nullptr) {
                HashNode* prev = entry;
                entry = entry->next;
                delete prev;
            }
            table[i] = nullptr;
        }
        delete[] table;
    }

    int hash(string key) {
        int hashVal = 0;
        for (int i = 0; i < key.length(); i++) {
            hashVal = 37 * hashVal + key[i];
        }
        hashVal %= TABLE_SIZE;
        if (hashVal < 0) {
            hashVal += TABLE_SIZE;
        }
        return hashVal;
    }

    void insert(string key, int value) {
        int hashVal = hash(key);
        HashNode* prev = nullptr;
        HashNode* entry = table[hashVal];
        while (entry != nullptr && entry->key != key) {
            prev = entry;
            entry = entry->next;
        }
        if (entry == nullptr) {
            entry = new HashNode(key, value);
            if (prev == nullptr) {
                table[hashVal] = entry;
            } else {
                prev->next = entry;
            }
        } else {
            entry->value = value;
        }
    }

    int get(string key) {
        int hashVal = hash(key);
        HashNode* entry = table[hashVal];
        while (entry != nullptr && entry->key != key) {
            entry = entry->next;
        }
        if (entry == nullptr) {
            return -1;
        } else {
            return entry->value;
        }
    }

    void remove(string key) {
        int hashVal = hash(key);
        HashNode* prev = nullptr;
        HashNode* entry = table[hashVal];
        while (entry != nullptr && entry->key != key) {
            prev = entry;
            entry = entry->next;
        }
        if (entry == nullptr) {
            return;
        } else {
            if (prev == nullptr) {
                table[hashVal] = entry->next;
            } else {
                prev->next = entry->next;
            }
            delete entry;
        }
    }
};

int main() {
    HashMap myMap;

    // 插入数据
    myMap.insert("apple", 1);
    myMap.insert("banana", 2);
    myMap.insert("orange", 3);

    // 查找数据
    cout << "apple: " << myMap.get("apple") << endl;

    // 删除数据
    myMap.remove("banana");

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

该示例代码中使用了链表法解决哈希冲突。如果发生哈希冲突，就将新的节点插入到链表的末尾。在查找时，遍历链表查找对应的节点。在删除时，将链表中对应的节点删除即可。