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
|
#pragma once
#include "Assert.h"
#include "BasicTypes.h"
#include "Impl/OptionalStorage.h"
#include "WAVM/Platform/Intrinsic.h"
namespace WAVM {
struct DefaultHashTableAllocPolicy
{
static constexpr Uptr minBuckets = 8;
static Uptr divideAndRoundUp(Uptr numerator, Uptr denominator)
{
return (numerator + denominator - 1) / denominator;
}
static Uptr getMaxDesiredBuckets(Uptr numDesiredElements)
{
const Uptr maxDesiredBuckets
= Uptr(1) << WAVM::ceilLogTwo(divideAndRoundUp(numDesiredElements * 20, 7));
return maxDesiredBuckets < minBuckets ? minBuckets : maxDesiredBuckets;
}
static Uptr getMinDesiredBuckets(Uptr numDesiredElements)
{
if(numDesiredElements == 0) { return 0; }
else
{
const Uptr minDesiredBuckets
= Uptr(1) << WAVM::ceilLogTwo(divideAndRoundUp(numDesiredElements * 20, 16));
return minDesiredBuckets < minBuckets ? minBuckets : minDesiredBuckets;
}
}
};
/*
struct HashTablePolicy
{
static const Key& getKey(const Element&);
static bool areKeysEqual(const Key&, const Key&);
};
*/
template<typename Element> struct HashTableBucket
{
OptionalStorage<Element> storage;
Uptr hashAndOccupancy;
static constexpr Uptr isOccupiedMask = Uptr(1) << (sizeof(Uptr) * 8 - 1);
static constexpr Uptr hashMask = ~isOccupiedMask;
};
// A lightly encapsulated hash table, used internally by HashMap and HashSet.
//
// It has a concept of both elements and keys: the key is something derivable from an element
// that is used to find an element in the table. For a set, Key=Element, but for a map,
// Key!=Element, and HashTablePolicy::getKey(Element) is used to derive the key of an element in
// the hash table.
//
// The implementation is a Robin Hood hash table.
//
// The buckets are a linear array of elements paired with pointer-sized metadata that uses 1
// bit to indicate whether the bucket is occupied, and the rest of the bits to store the hash of
// the occupying element. The array is indexed by a hash of the element's key, modulo the number
// of buckets, which is always a power of two.
//
// Storing the hash and occupancy of a bucket imposes some overhead on the simplest cases
// where the key is small/easy to hash and has a null value, but avoids pathological performance
// in the general case. It also makes it easier to write good debugger visualizers for the hash
// tables.
//
// If more than one element hashes to the same bucket, the extra elements will be stored in
// the buckets following the "ideal bucket" in the table. There is an abstract concept of how
// "rich" an element is by how close it is stored to its ideal bucket.
// When inserting new elements, they are stored in the leftmost bucket, starting from their
// ideal bucket, that is empty or holds an element that hashes to a higher bucket than their
// ideal bucket. If the bucket contains an element, that element, and the elements from any
// subsequent consecutively occupied buckets are moved one bucket right to make space for it.
// When removing an element, the chain of elements in following buckets are shifted left into
// the hole until an empty bucket is found, or an element that is in its ideal bucket.
// This insert/remove strategy maintains the invariant that all elements that hash to the same
// ideal bucket are stored in consecutive buckets at or following the ideal bucket, and elements
// that hash to different buckets are sorted w.r.t. their ideal bucket. This invariant allows
// searches to stop once they reach an element whose ideal bucket is to the right of the search
// key's ideal bucket, limiting the worst case search time.
//
// This is more complex than an externally chained hash table, which stored a list of elements
// in each hash bucket, but has far better cache coherency as searching for a key is a linear
// walk through memory, and less allocator overhead as the entire table uses a single
// allocation.
//
// For the table to function correctly, it must contain at least one empty bucket. As the
// table approaches 100% occupancy, the collision rate increases, and the worst case search time
// increases quickly.
// The table is dynamically resized as dictated by the AllocPolicy. The default
// policy keeps the table between 35% and 80% occupied. This gives an average occupancy of 65%,
// or about 2x space usage compared to just storing an array of the elements.
template<typename Key,
typename Element,
typename HashTablePolicy,
typename AllocPolicy = DefaultHashTableAllocPolicy>
struct HashTable
{
typedef HashTableBucket<Element> Bucket;
HashTable(Uptr estimatedNumElements = 0);
HashTable(const HashTable& copy);
HashTable(HashTable&& movee) noexcept;
~HashTable();
HashTable& operator=(const HashTable& copyee);
HashTable& operator=(HashTable&& movee) noexcept;
void clear();
void resize(Uptr newNumBuckets);
bool remove(Uptr hash, const Key& key);
const Bucket* getBucketForRead(Uptr hash, const Key& key) const;
Bucket* getBucketForModify(Uptr hash, const Key& key);
Bucket& getBucketForAdd(Uptr hash, const Key& key);
Uptr size() const { return numElements; }
Uptr numBuckets() const { return hashToBucketIndexMask + 1; }
Bucket* getBuckets() const { return buckets; }
// Compute some statistics about the space usage of this hash table.
void analyzeSpaceUsage(Uptr& outTotalMemoryBytes,
Uptr& outMaxProbeCount,
F32& outOccupancy,
F32& outAverageProbeCount) const;
private:
Bucket* buckets;
Uptr numElements;
Uptr hashToBucketIndexMask;
// Calculates the distance of the element in the bucket from its ideal bucket.
Uptr calcProbeCount(Uptr bucketIndex) const;
Bucket& getBucketForWrite(Uptr hash, const Key& key);
void evictHashBucket(Uptr bucketIndex);
void eraseHashBucket(Uptr eraseBucketIndex);
void destruct();
void copyFrom(const HashTable& copy);
void moveFrom(HashTable&& movee) noexcept;
};
// The implementation is defined in a separate file.
#include "Impl/HashTableImpl.h"
}
|
