· 4 years ago · May 07, 2021, 07:42 PM
1#include <functional>
2#include <iostream>
3#include <vector>
4
5template <typename Key, typename T>
6class HashNode {
7public:
8 Key key;
9 T value;
10 HashNode* next;
11 HashNode(Key key, T value) : key(key), value(value), next(nullptr) {
12 }
13};
14
15template <typename Key, typename T, typename Hash = std::hash<Key>,
16 typename KeyEqual = std::equal_to<Key>>
17class HashTable {
18public:
19 /*
20 * See https://en.cppreference.com/w/cpp/container/unordered_map/unordered_map (1)
21 *
22 * Constructs new container. The number of buckets to create is implementation-defined.
23 */
24 HashTable() : table_(128, nullptr), bucket_count_(128), size_(0){};
25
26 /*
27 * See https://en.cppreference.com/w/cpp/container/unordered_map/unordered_map (1)
28 *
29 * Constructs new container, uses bucket_count parameter as a minimal number of buckets to
30 * create.
31 */
32 explicit HashTable(size_t bucket_count)
33 : table_(bucket_count, nullptr), bucket_count_(bucket_count), size_(0){};
34
35 HashTable(const HashTable& other) {
36 *this = other;
37 };
38
39 ~HashTable() {
40 Clear();
41 };
42
43 /*
44 * See https://en.cppreference.com/w/cpp/container/unordered_map/empty
45 *
46 * Returns true if the tree is empty, false otherwise
47 */
48 bool Empty() const {
49 return (Size() == 0);
50 };
51
52 /*
53 * See https://en.cppreference.com/w/cpp/container/unordered_map/size
54 *
55 * Returns the number of elements in the container
56 */
57 size_t Size() const {
58 return size_;
59 };
60
61 double LoadFactor() {
62 return (size_ / bucket_count_);
63 }
64
65 void ReHash() {
66 if (LoadFactor() > 0.75) {
67 std::vector<HashNode<Key, T>*> temp_table;
68 temp_table = table_;
69 table_.clear();
70 bucket_count_ *= 2;
71 table_.resize(bucket_count_, nullptr);
72 for (size_t i = 0; i < temp_table.size(); i++) {
73 if (temp_table[i] != nullptr) {
74 Insert(temp_table[i]->key, temp_table[i]->value);
75 }
76 }
77 temp_table.clear();
78 }
79 }
80
81 /*
82 * See https://en.cppreference.com/w/cpp/container/unordered_map/clear
83 *
84 * Erases all elements from the container.
85 */
86 void Clear() {
87 for (size_t i = 0; i < bucket_count_; i++) {
88 HashNode<Key, T>* temp = table_[i];
89 while (temp != nullptr) {
90 HashNode<Key, T>* parrent = temp;
91 temp = temp->next;
92 delete parrent;
93 }
94 table_[i] = nullptr;
95 }
96 size_ = 0;
97 };
98
99 /*
100 * See https://en.cppreference.com/w/cpp/container/unordered_map/insert
101 *
102 * Returns a bool value set to true if the insertion took place.
103 */
104 bool Insert(const Key& key, const T& value) {
105 if (!Contains(key)) {
106 size_t hash_value = hash_function_(key) % bucket_count_;
107 HashNode<Key, T>* temp = table_[hash_value];
108 HashNode<Key, T>* inserted_hash_node = new HashNode<Key, T>(key, value);
109 HashNode<Key, T>* parrent = nullptr;
110
111 while (temp != nullptr) {
112 parrent = temp;
113 temp = temp->next;
114 }
115 if (parrent != nullptr) {
116 parrent->next = inserted_hash_node;
117 } else {
118 table_[hash_value] = inserted_hash_node;
119 }
120 size_++;
121 ReHash();
122 return true;
123 } else {
124 return false;
125 }
126 };
127
128 /*
129 * See https://en.cppreference.com/w/cpp/container/unordered_map/erase
130 *
131 * Removes the element from the container with set key.
132 * Returns true if the erase took place.
133 */
134 bool Erase(const Key& key) {
135 size_t hash_value = hash_function_(key) % bucket_count_;
136 HashNode<Key, T>* temp = table_[hash_value];
137 HashNode<Key, T>* parrent = nullptr;
138
139 while (temp != nullptr && !(equal_(temp->key, key))) {
140 parrent = temp;
141 temp = temp->next;
142 }
143 if (temp == nullptr) {
144 return false;
145 } else {
146 if (parrent != nullptr) {
147 parrent->next = temp->next;
148 } else {
149 table_[hash_value] = temp->next;
150 }
151 delete temp;
152 size_--;
153 return true;
154 }
155 };
156
157 /*
158 * See https://en.cppreference.com/w/cpp/container/unordered_map/contains
159 *
160 * Returns true if an element with key equivalent to value exists in the container.
161 */
162 bool Contains(const Key& key) const {
163 size_t hash_value = hash_function_(key) % bucket_count_;
164 HashNode<Key, T>* temp = table_[hash_value];
165
166 while (temp != nullptr) {
167 if (equal_(temp->key, key)) {
168 return true;
169 }
170 temp = temp->next;
171 }
172 return false;
173 };
174
175 /*
176 * See https://en.cppreference.com/w/cpp/container/unordered_map/operator_at
177 *
178 * Returns a reference to the value that is mapped to a key equivalent to key, performing an
179 * insertion if such key does not already exist.
180 */
181 T& operator[](const Key& key) {
182 size_t hash_value = hash_function_(key) % bucket_count_;
183 HashNode<Key, T>* temp = table_[hash_value];
184 while (temp != nullptr) {
185 if (temp->key == key) {
186 return temp->value;
187 }
188 }
189 return temp->value;
190 };
191
192private:
193 std::vector<HashNode<Key, T>*> table_;
194 size_t bucket_count_;
195 size_t size_;
196 Hash hash_function_;
197 KeyEqual equal_;
198};
199
200int main() {
201 size_t n;
202 std::cin >> n;
203 HashTable<int, int, std::hash<int>, std::equal_to<int>> hash_table;
204 for (size_t i = 0; i < n; i++) {
205 std::string command;
206 std::cin >> command;
207 if (command == "Insert") {
208 int new_key;
209 int new_value;
210 std::cin >> new_key;
211 std::cin >> new_value;
212 std::cout << hash_table.Insert(new_key, new_value) << std::endl;
213 }
214 if (command == "operator") {
215 int new_key;
216 int new_value;
217 std::cin >> new_key;
218 std::cin >> new_value;
219 if (hash_table.Contains(new_key)) {
220 std::cout << new_key << " " << hash_table[new_key] << std::endl;
221 hash_table[new_key] = new_value;
222 } else {
223 hash_table.Insert(new_key, new_value);
224 std::cout << new_key << " " << new_value << std::endl;
225 }
226 }
227 if (command == "Delete") {
228 int new_key;
229 std::cin >> new_key;
230 std::cout << hash_table.Erase(new_key) << std::endl;
231 }
232 if (command == "Find") {
233 int new_key;
234 std::cin >> new_key;
235 std::cout << hash_table.Contains(new_key) << std::endl;
236 }
237 if (command == "Size") {
238 std::cout << hash_table.Size() << std::endl;
239 }
240 if (command == "Clear") {
241 hash_table.Clear();
242 std::cout << "Clear" << std::endl;
243 }
244 if (command == "Empty") {
245 std::cout << hash_table.Empty() << std::endl;
246 }
247 }
248}