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
|
#pragma once
#include <algorithm>
#include <iostream>
#include <list>
#include <mutex>
#include <optional>
#include <shared_mutex>
#include <vector>
template <typename K, typename V>
class HashTable {
public:
HashTable(size_t size)
: size { size }
, table(size)
, bucket_mutexes(size)
{
}
bool insert(K key, V value)
{
size_t index = get_bucket_index(key);
std::unique_lock<std::shared_mutex> lock(bucket_mutexes.at(index));
std::list<std::pair<K, V>>& list = table.at(index);
if (bucket_contains_key(list, key)) {
return false;
}
list.push_back(std::pair(key, value));
return true;
}
std::optional<V> get(K key)
{
size_t index = get_bucket_index(key);
std::shared_lock<std::shared_mutex> lock(bucket_mutexes.at(index));
std::list<std::pair<K, V>>& list = table.at(index);
auto iter = bucket_find_key(list, key);
if (iter != list.end()) {
return std::optional<V>((*iter).second);
}
return std::optional<V>();
}
bool remove(K key)
{
size_t index = get_bucket_index(key);
std::unique_lock<std::shared_mutex> lock(bucket_mutexes.at(index));
std::list<std::pair<K, V>>& list = table.at(index);
auto iter = bucket_find_key(list, key);
if (iter != list.end()) {
list.erase(iter);
return true;
}
return false;
}
void print()
{
size_t index { 0 };
for (auto bucket : table) {
std::cout << "Bucket " << index << ": [";
std::shared_lock<std::shared_mutex> lock(bucket_mutexes.at(index));
for (auto pair : bucket) {
std::cout << "(" << pair.first << ", " << pair.second << ")";
}
std::cout << "]" << "\n";
++index;
}
}
private:
size_t size;
std::vector<std::list<std::pair<K, V>>> table;
std::vector<std::shared_mutex> bucket_mutexes;
std::hash<K> hash_function;
auto bucket_find_key(std::list<std::pair<K, V>>& list, K key)
{
return std::find_if(list.begin(), list.end(), [&key](const std::pair<K, V>& pair) {
return pair.first == key;
});
}
bool bucket_contains_key(std::list<std::pair<K, V>>& list, K key)
{
return list.begin() != list.end() && bucket_find_key(list, key) != list.end();
}
size_t get_bucket_index(K key) { return hash_function(key) % size; }
};
|