1+ #include < algorithm>
2+ #define bucket_num 1543
3+ using namespace std ;
4+
5+ /*
6+ hash_map可以用hash_table构建键值对直接实现
7+ 重写一遍为了能单独拿来参考
8+ */
9+ template <class Key , class Value >
10+ class hash_map
11+ {
12+ // 冲突以开链法解决
13+ struct node
14+ {
15+ node* next;
16+ pair<Key, Value> value;
17+ node (): next(nullptr ) {};
18+ node (pair<Key, Value> val): next(nullptr ), value(val) {}
19+ };
20+ private:
21+ node* buckets;
22+ public:
23+ // 桶的大小通常根据需求选择某个质数
24+ hash_map (): buckets(new node[bucket_num]) {};
25+ ~hash_map ()
26+ {
27+ destroy (buckets);
28+ delete[] buckets;
29+ }
30+
31+ // 不能有重复值
32+ bool insert (const pair<Key, Value> value)
33+ {
34+ int hashcode = value.first % bucket_num;
35+ node* head = &buckets[hashcode];
36+ while (head->next != nullptr && head->next ->value .first != value.first ) head = head->next ;
37+ if (head->next == nullptr )
38+ head->next = new node (value);
39+ else
40+ return false ;
41+ return true ;
42+ }
43+
44+ bool remove (const Key key)
45+ {
46+ int hashcode = key % bucket_num;
47+ node* head = &buckets[hashcode];
48+ while (head->next != nullptr && head->next ->value .first != key) head = head->next ;
49+ if (head->next == nullptr ) return false ;
50+ else
51+ {
52+ node* temp = head->next ;
53+ head->next = head->next ->next ;
54+ delete temp;
55+ }
56+ return true ;
57+ }
58+
59+
60+ pair<bool , Value> find (const Key key)
61+ {
62+ int hashcode = key % bucket_num;
63+ node* head = &buckets[hashcode];
64+ while (head->next != nullptr && head->next ->value .first != key) head = head->next ;
65+ if (head->next == nullptr ) return make_pair (false , head->value .second );
66+ else return make_pair (true , head->next ->value .second );
67+ }
68+
69+ private:
70+ void destroy (node* buckets)
71+ {
72+ for (int i = 0 ; i < bucket_num; ++i)
73+ {
74+ node* head = &buckets[i];
75+ head = head->next ;
76+ while (head != nullptr )
77+ {
78+ node* temp = head;
79+ head = head->next ;
80+ delete temp;
81+ }
82+ }
83+ }
84+ };
85+
86+ // 在cpp文件里测试
87+ // #include"hash_map.h"
88+ // #include<iostream>
89+ // int main(int argc, char const *argv[])
90+ // {
91+ // hash_map<int, string> m;
92+ // m.insert(make_pair(1, "hello"));
93+ // m.insert(make_pair(2, "world"));
94+ // m.insert(make_pair(3, "this"));
95+ // m.insert(make_pair(4, "is"));
96+ // m.insert(make_pair(5, "Shey's"));
97+ // m.insert(make_pair(6, "map"));
98+ // m.remove(2);
99+ // if (m.find(1).first) cout << m.find(1).second << endl;
100+ // if (m.find(2).first) cout << m.find(2).second << endl;
101+ // if (m.find(3).first) cout << m.find(3).second << endl;
102+ // if (m.find(4).first) cout << m.find(4).second << endl;
103+ // if (m.find(5).first) cout << m.find(5).second << endl;
104+ // if (m.find(6).first) cout << m.find(6).second << endl;
105+ // return 0;
106+ // }
107+ // hello
108+ // this
109+ // is
110+ // Shey's
111+ // map
0 commit comments