ExcaliburHash

About

Excalibur Hash is a high-speed hash map and hash set, ideal for performance-critical uses like video games. Its design focuses on being friendly to the CPU cache, making it very efficient and fast. It uses an open addressing hash table and manages removed items with a method called tombstones.

Engineered for ease of use, Excalibur Hash, in a vast majority of cases (99%), serves as a seamless, drop-in alternative to std::unordered_map. However, it's important to note that Excalibur Hash does not guarantee stable addressing. So, if your project needs to hold direct pointers to the keys or values, Excalibur Hash might not work as you expect. This aside, its design and efficiency make it a great choice for applications where speed is crucial.

Features

1. Extremely fast (see Performance section for details)
2. CPU cache friendly
3. Built-in configurable inline storage
4. Can either work as a map (key, value) or as a set (keys only)

Performance

In this section, you can see a performance comparison against a few popular hash table implementations. This comparison will show their speed and efficiency, helping you understand which hash table might work best for your project.

Unless otherwise stated, all tests were run using the following configuration

OS: Windows 11 Pro (22621.3155)
CPU: Intel i9-12900K
RAM: 128Gb 
Compiled in the Release mode using VS2022 (19.39.33520)

Performance test repositoty

absl::flat_hash_map
boost::unordered_map
boost::unordered_flat_map
ska::flat_hash_map
ska::unordered_map
folly::F14ValueMap
llvm::DenseMap
Luau::DenseHashMap
phmap::flat_hash_map
tsl::robin_map
google::dense_hash_map
std::unordered_map
Excalibur::HashTable

CtorDtor

Create and immediatly delete 300,000 hash tables on the stack, using a 'heavyweight' object as the value. This test quickly shows which hash map implementations 'cheat' by creating many key/value pairs in advance.

ClearAndInsertSeq

1. Create a hash table
2. Clear the hash table
3. Insert 599,999 sequential values
4. Repeat steps 2-3 (25 times)
5. Destroy the hash table

InsertRndClearAndReInsert

1. Create a hash table
2. Insert 1,000,000 unique random int numbers
3. Clear the hash table
4. Reinsert 1,000,000 unique random int numbers into the same cleared map.
5. Destroy the hash table
6. Repeat steps 1-5 (10 times)

InsertRndAndRemove

1. Create a hash table
2. Insert 1,000,000 unique random int numbers
3. Remove all of the inserted entries one by one until the map is empty again.
4. Destroy the hash table
5. Repeat steps 1-4 (10 times)

CtorSingleEmplaceDtor

1. Create a hash table
2. Insert a single key/value int the hash table
3. Destroy the hash table
4. Repeat steps 1-3 (300,000 times)

InsertAccessWithProbability10

1. Create a hash table
2. Insert or increment 1,000,000 values where 10% of keys are duplicates (10% of operations will be modifications and 90% will be insertions)
3. Destroy the hash table
4. Repeat steps 1-3 (8 times)

InsertAccessWithProbability50

1. Create a hash table
2. Insert or increment 1,000,000 values where 50% of keys are duplicates (50% of operations will be modifications and 50% will be insertions)
3. Destroy the hash table
4. Repeat steps 1-3 (8 times)

SearchNonExisting

1. Create a hash table
2. Insert 1,000,000 unique random int numbers
3. Search for non existent keys (10,000,000 times)
4. Destroy the hash table

SearchExisting

1. Create a hash table
2. Insert 1,000,000 unique random int numbers
3. Search for existent keys (10,000,000 times)
4. Destroy the hash table

ClearAndInsertRnd

1. Create a hash table
2. Insert 1,000,000 unique random int numbers
3. Destroy the hash table
4. Repeat steps 1-3 (25 times)

Summary

Below, you can find all the tests combined into a single table using normalized timings where 1.0 is the fastest implementation, 2.0 is twice as slow as the fastest configuration, and so on.

OS: Windows 11 Pro (22621.2861)
CPU: Intel i9-12900K
RAM: 128Gb 

OS: Windows 11 Home (22631.2861)
CPU: AMD Ryzen5 2600
RAM: 16Gb 

Usage

Here is the simplest usage example.

#include "ExcaliburHash.h"

int main()
{
  // use hash table as a hash map (key/value)
  Excalibur::HashTable<int, int> hashMap;
  hashMap.emplace(13, 6);

  // use hash table as a hash set (key only)
  Excalibur::HashTable<int, nullptr_t> hashSet;
  hashSet.emplace(13);

  return 0;
}

More detailed examples can be found in the unit tests folder.