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
|
#pragma once
#include <algorithm>
#include <list>
#include <vector>
template <typename K, typename V>
class HashTable {
public:
HashTable(size_t size)
: size { size }
, table(size)
{
}
bool insert(K key, V value)
{
std::list<std::pair<K, V>> list = get_bucket(key);
if (bucket_contains_key(list, key)) {
return false;
}
list.insert(value);
return true;
}
private:
size_t size;
std::vector<std::list<std::pair<K, V>>> table;
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 bucket_find_key(list, key) != list.end();
}
std::list<std::pair<K, V>> get_bucket(K key)
{
size_t index = hash_function(key) % size;
return table.at(index);
}
};
|