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

Extremely fast (see Performance section for details)
CPU cache friendly
Built-in configurable inline storage
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

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

InsertRndClearAndReInsert

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

InsertRndAndRemove

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

CtorSingleEmplaceDtor

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

InsertAccessWithProbability10

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

InsertAccessWithProbability50

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

SearchNonExisting

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

SearchExisting

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

ClearAndInsertRnd

Create a hash table
Insert 1,000,000 unique random int numbers
Destroy the hash table
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.

tcantenot/ExcaliburHash