RobinHoodMap.hpp

Robin Hood hashing - minimize how “wrong” a position can be in a hash table.

This file is part of Empirical, https://github.com/devosoft/Empirical Copyright (C) 2025 Michigan State University MIT Software license; see doc/LICENSE.md

Note

Status: ALPHA

Defines

INCLUDE_EMP_DATASTRUCTS_ROBIN_HOOD_MAP_HPP_GUARD

template<typename Key, typename T> class RobinHoodMap

#include <RobinHoodMap.hpp>

Public Functions

RobinHoodMap() = default

RobinHoodMap(RobinHoodMap&&) = default

RobinHoodMap &operator=(RobinHoodMap&&) = default

inline ~RobinHoodMap()

inline size_t size() const

inline size_t capacity() const

inline bool empty() const

inline bool contains(const T &key) const

inline void insert(std::pair<Key, T> in)

inline void Insert(const Key &key, const T &value)

inline const T *FindPtr(const Key &key) const

inline T *FindPtr(const Key &key)

inline T &operator[](const Key &key)

inline bool erase(const Key &key)

Private Functions

inline size_t CalcDist(size_t pos) const

inline void Rehash(size_t new_capacity)

inline const T *FindPtr_impl(const Key &key) const

Private Members

vector<Entry> table = {INIT_CAPACITY}

size_t num_elements = 0

Private Static Attributes

static constexpr double MAX_LOAD_FACTOR = 0.8

static constexpr size_t INIT_CAPACITY = 15

static constexpr double GROW_FACTOR = 2.0

static constexpr size_t GROW_OFFSET = 1

struct Entry

Public Members

Key key

T value

size_t hash = 0

bool occupied = false