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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
|
#pragma once
#include <algorithm>
#include <iostream>
#include <list>
#include <mutex>
#include <optional>
#include <shared_mutex>
#include <sstream>
#include <vector>
/**
* @class HashTable
* @brief Represents a generic hashtable with simple operations.
*/
template <typename K, typename V>
class HashTable {
public:
/**
* @brief Constructs a new Hashtable.
*
* @param size The number of buckets of the table.
*/
HashTable(size_t size)
: size { size }
, table(size)
, bucket_mutexes(size)
{
}
/**
* @brief Constructs a new Hashtable.
*
*/
HashTable() {}
/**
* @brief Insert a kv-pair into the hashtable.
*
* @param key The key to determine the bucket.
* @param value The value to insert.
* @return bool Successful insert of the pair.
*/
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;
}
/**
* @brief Gets the value which corresponds to the key.
*
* @param key The key to look for.
* @return std::optional The value, if the key could be found.
*/
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>();
}
/**
* @brief Removes the kv-pair which corresponds to the key.
*
* @param key The key to look for.
* @return bool The pair could be removed successfully.
*/
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;
}
/**
* @brief Constructs a string representation of the hashtable.
*
* @return std::string The string of the hashtable.
*/
std::string string()
{
std::ostringstream output;
size_t index { 0 };
for (auto bucket : table) {
output << "Bucket " << index << ": [";
std::shared_lock<std::shared_mutex> lock(bucket_mutexes.at(index));
for (auto pair : bucket) {
output << "(" << pair.first << ", " << pair.second << ")";
}
output << "]" << "\n";
++index;
}
return output.str();
}
private:
/**
* @brief The number of buckets.
*/
size_t size;
/**
* @brief The hashtable.
*/
std::vector<std::list<std::pair<K, V>>> table;
/**
* @brief A mutex for every button.
*/
std::vector<std::shared_mutex> bucket_mutexes;
/**
* @brief The hashfunction to use for the bucket determination.
*/
std::hash<K> hash_function;
/**
* @brief Finds the kv-pair inside a bucket.
*
* @param list The bucket.
* @param key The key to look for.
* @return auto The iterator element, which points to the kv-pair or list.end().
*/
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;
});
}
/**
* @brief Checks if the bucket contains the key.
*
* @param list The bucket.
* @param key The key to look for.
* @return bool The bucket contains the 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();
}
/**
* @brief Uses the hashfunction and the key to determine, which bucket to use.
*
* @param key The key.
* @return size_t The index of the bucket.
*/
size_t get_bucket_index(K key) { return hash_function(key) % size; }
};
|