Cuckoo Hashing is nice because it has worst-case constant time lookups. It was invented in 2001 by Pagh and Rodler. You can read more about it here: https://en.wikipedia.org/wiki/Cuckoo_hashing.
This implementation is resizable, so the two tables expand if needed. It’s recommended you use a power of 2 for the size if you specify one in the constructor. Currently it uses a simple hashing policy by default, and your typical standard allocator for memory allocations. The Hash policy is very simple if you’d like to swap it out for your own custom policy: a hash function used to hash keys for the first table, and a hash2 function for the second table.
hashmap.hh
[code=cpp]#ifndef HASHMAP_HH
#define HASHMAP_HH 1
#include
#include
#include
#include
#include “hash_policy.hh”
template <
typename KeyType,
typename ValueType,
typename Predicate = std::equal_to,
template class Hash = SimpleHashPolicy,
typename Allocator = std::allocator<std::pair<KeyType, ValueType>>
class HashMap : public Hash {
Allocator allocator;
std::size_t tableSize, tableSize2, size;
std::vector<std::pair<KeyType, ValueType>*> entries, entries2;
Predicate pred;
const unsigned int getNextPowerOfTwo() const noexcept {
unsigned int pow = 2;
while (pow * 2 < tableSize) pow *= 2;
return pow;
}
public:
HashMap(const std::size_t size = 64) {
if (size <= 1) {
throw std::range_error(“Table size must be greater than one.”);
}
this->size = size;
tableSize = size / 2;
tableSize2 = size / 2;
allocator = Allocator();
entries = std::vector<std::pair<KeyType, ValueType>*>(tableSize);
entries2 = std::vector<std::pair<KeyType, ValueType>*>(tableSize2);
pred = Predicate();
}
~HashMap() {
for (auto& entry : entries) {
if (entry != nullptr) {
allocator.destroy(entry);
allocator.deallocate(entry, 1);
}
}
for (auto& entry : entries2) {
if (entry != nullptr) {
allocator.destroy(entry);
allocator.deallocate(entry, 1);
}
}
}
std::pair<KeyType, ValueType>* get(const KeyType k) const noexcept {
const unsigned int entryIndex = Hash::hash(k, tableSize);
const unsigned int entryIndex2 = Hash::hash2(k, tableSize2);
std::pair<KeyType, ValueType>* element = nullptr;
// The element can be in one of two places, get the correct KV-pair.
if (entries[entryIndex] != nullptr && pred(entries[entryIndex]->first, k)) {
element = entries[entryIndex];
} else if (entries2[entryIndex2] != nullptr && pred(entries2[entryIndex2]->first, k)) {
element = entries2[entryIndex2];
}
return element;
}
bool set(const KeyType k, ValueType v) noexcept {
unsigned int entryIndex = 0;
unsigned int nextPowerOfTwo = getNextPowerOfTwo();
unsigned int tries = 0;
bool retried = false;
std::pair<KeyType, ValueType>* element = allocator.allocate(1);
allocator.construct(element, k, v);
while (true) {
while (tries < nextPowerOfTwo) {
entryIndex = Hash::hash(element->first, tableSize);
if (entries[entryIndex] == nullptr) {
entries[entryIndex] = element;
return true;
} else {
// Kick-out any already occupying entry.
tries++;
std::pair<KeyType, ValueType>* tmp = entries[entryIndex];
entries[entryIndex] = element;
// Use the kicked-out key to hash.
entryIndex = Hash::hash2(tmp->first, tableSize2);
// Second table has an empty entry – put it there.
if (entries2[entryIndex] == nullptr) {
entries2[entryIndex] = tmp;
return true;
} else {
// Otherwise, kick-out the element there and find a new place for it
// in the first table.
element = entries2[entryIndex];
entries2[entryIndex] = tmp;
}
}
tries++;
}
if (retried) {
break;
}
size *= 2;
tableSize = size / 2;
tableSize2 = size / 2;
entries.resize(tableSize, nullptr);
entries2.resize(tableSize2, nullptr);
retried = true;
tries = 0;
nextPowerOfTwo = getNextPowerOfTwo();
}
return false;
}
bool deleteElement(const KeyType k) noexcept {
const unsigned int entryIndex = Hash::hash(k, tableSize);
const unsigned int entryIndex2 = Hash::hash2(k, tableSize2);
// The element can be in one of two places, delete the correct KV-pair.
if (entries[entryIndex] != nullptr && pred(entries[entryIndex]->first, k)) {
allocator.destroy(entries[entryIndex]);
allocator.deallocate(entries[entryIndex], 1);
entries[entryIndex] = nullptr;
return true;
} else if (entries2[entryIndex2] != nullptr && pred(entries2[entryIndex2]->first, k)) {
allocator.destroy(entries2[entryIndex2]);
allocator.deallocate(entries2[entryIndex2], 1);
entries2[entryIndex2] = nullptr;
return true;
}
return false;
}
bool exists(const KeyType k) const noexcept {
const unsigned int entryIndex = Hash::hash(k, tableSize);
const unsigned int entryIndex2 = Hash::hash2(k, tableSize2);
// The element can be in one of two places, delete the correct KV-pair.
if (entries[entryIndex] != nullptr && pred(entries[entryIndex]->first, k)) {
return true;
} else if (entries2[entryIndex2] != nullptr && pred(entries2[entryIndex2]->first, k)) {
return true;
}
return false;
}
};
#endif
[/code]
hash_policy.hh
[code=cpp]#ifndef HASH_POLICY_HH
#define HASH_POLICY_HH 1
#include
template
struct SimpleHashPolicy {
static const unsigned int hash(const KeyType k, const unsigned int tableSize) {
return k % tableSize;
}
static const unsigned int hash2(const KeyType k, const unsigned int tableSize) {
return static_cast(k / tableSize) % tableSize;
}
};
#endif
[/code]
test.cc
[code=cpp]#include
#include “hashmap.hh”
int main() {
try {
HashMap<int, int> map;
map.set(0, 123);
map.set(1, 234);
map.set(2, 345);
std::cout << map.get(0)->second << " " << map.get(1)->second << " " << map.get(2)->second << std::endl;
} catch (const std::range_error& e) {
std::cerr << e.what() << std::endl;
}
return 0;
}[/code]
;D :o :rolleyes: :eek: :mad: 