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
|
#pragma once
#include <assert.h>
#include <limits.h>
#include <stddef.h>
#include <stdint.h>
#include <vector>
namespace vst {
// Custom open addressing hashtable that supports custom view types
// for keys to avoid expensive conversions in find() method.
// A typical use case would be std::string_view for std::string keys.
// Key must be constructible from KeyView, KeyView must be convertable
// to Key and both types must be comparable with each other.
template<typename Key, typename Value, typename KeyView = Key>
class HashTable {
public:
HashTable() { array_.resize(initialCapacity); };
template<typename U>
bool insert(const KeyView& key, U&& value) {
return insert(Key{key}, std::forward<U>(value));
}
template<typename U>
bool insert(Key&& key, U&& value);
const Value* find(const KeyView& key) const;
template<typename U>
Value findOr(const KeyView& key, U&& value) const {
if (auto result = find(key)) {
return *result;
} else {
return std::forward<U>(value);
}
}
size_t size() const {
return count_;
}
void clear() {
for (auto& e : array_) {
e = Entry{};
}
count_ = 0;
}
private:
static constexpr size_t initialCapacity = 8;
using HashType = uint32_t;
static constexpr HashType flag = (HashType)1 << (sizeof(HashType) * CHAR_BIT - 1);
static HashType makeHash(const KeyView& key) {
HashType hash = std::hash<KeyView>{}(key);
return hash & ~flag;
}
void rehash() {
auto newSize = array_.size() * 2;
auto oldArray = std::move(array_);
array_ = std::vector<Entry>(newSize);
for (auto& e : oldArray) {
if (!e.empty()) {
auto success = insert(std::move(e.key_), std::move(e.value_));
assert(success);
}
}
}
struct Entry {
Key key_{};
HashType hash_{}; // highest bit is reserved (1 = slot is occupied)
Value value_{};
HashType hash() const {
return hash_ & ~flag;
}
bool empty() const {
return !(hash_ & flag);
}
};
std::vector<Entry> array_;
size_t count_ = 0;
};
template<typename Key, typename Value, typename KeyView>
template<typename U>
inline bool HashTable<Key, Value, KeyView>::insert(Key&& key, U&& value) {
// rehash if load factor exceeds 0.5
if (count_ >= array_.size() / 2) {
rehash();
}
const auto hash = makeHash(key);
// NB: array size is always power of two!
const auto mask = array_.size() - 1;
for (size_t index = hash;; ++index) {
index = index & mask;
if (array_[index].empty()) {
// found free slot
array_[index].key_ = std::move(key);
array_[index].hash_ = hash | flag; // mark as occupied!
array_[index].value_ = std::forward<U>(value);
count_++;
return true;
} else {
// check if key already exists!
if (hash == array_[index].hash() && key == array_[index].key_) {
return false;
}
}
}
// unreachable (the hashtable should always contain empty slots)
assert(false);
return false;
}
template<typename Key, typename Value, typename KeyView>
const Value* HashTable<Key, Value, KeyView>::find(const KeyView& key) const {
const auto hash = makeHash(key);
// NB: array size is always power of two!
const auto mask = array_.size() - 1;
for (size_t index = hash;; ++index) {
index = index & mask;
if (array_[index].empty()) {
return nullptr; // hit empty slot
} else {
if (hash == array_[index].hash() && key == array_[index].key_) {
return &array_[index].value_; // found match!
}
}
}
// unreachable (the hashtable should always contain empty slots)
assert(false);
return nullptr;
}
} // namespace vst
|
