TSherwoodHashTable

Implementation of Robin Hood hash table based on sherwood_v3_table by Malte Skarupke.

Choose your operating system:

Windows

macOS

Linux

References

Module

Core

Header

/Engine/Source/Runtime/Core/Public/Experimental/Containers/SherwoodHashTable.h

Include

#include "Experimental/Containers/SherwoodHashTable.h"

Syntax

template<typename KeyType, typename ValueType, typename KeyFuncs>
struct TSherwoodHashTable

Remarks

Implementation of Robin Hood hash table based on sherwood_v3_table by Malte Skarupke. Good for small keys and values. If key is already a high quality hash, then identity hash function should be used. Current limitations:

  • Requires key and value to be trivial types.

  • Does not allow move or copy.

  • Does not support custom allocators.

Variables

Name Description

Public variable

FData

 

CurrentData

Public variable

int8

 

MaxLookups

Public variable

int32

 

NumElements

Public variable

uint32

 

NumSlotsMinusOne

Constructors

Destructors

Name Description

Public function

~TSherwoodHashTable()

Functions

Name Description

Public function

ValueType &#...

 

Add

(
    int8 Distance,
    FData& Data,
    uint32 Cursor,
    KeyType Key,
    HashType Hash,
    ValueType Value
)

Public function Static

FData

 

AllocateData

(
    uint32 Count
)

Public function Static

T *

 

AllocateUninitialized

(
    uint32 Count
)

Public function Static

uint8

 

ComputeMaxLookups

(
    uint32 InNumSlots
)

Public function Static

void

 

Deallocate

(
    void* Ptr
)

Public function Static

void

 

DeallocateData

(
    FData& Data
)

Public function

void

 

Empty()

Public function Const

TTuple< cons...

 

Find

(
    KeyType Key
)

Public function

ValueType &#...

 

FindOrAdd

(
    KeyType Key,
    ValueType Value,
    bool* bIsAlreadyInContainerPtr
)

Public function

ValueType &#...

 

FindOrAddByHash

(
    KeyType Key,
    HashType Hash,
    ValueType Value,
    bool* bIsAlreadyInContainerPtr
)

Public function

void

 

Grow()

Public function Const

uint32

 

NumSlots()

Public function

void

 

Rehash

(
    uint32 DesiredNumSlots
)

Public function

void

 

Reserve

(
    uint32 DesiredNumElements
)

Public function

void

 

Reset()

Operators

Name Description

Public function

TSherwoodHas...

 

operator=

(
    const TSherwoodHashTable&
)

Public function

TSherwoodHas...

 

operator=

(
    TSherwoodHashTable&&
)

Classes

Name

Description

Public struct

FData

Typedefs

Name

Description

HashType

Constants

Name

Description

bIsMap

TSherwoodHashTable can be used to implement a set or a map.

MaxLoadFactor

Ratio between number of stored elements and allocated capacity beyond which the container will be grown (doubled in size).

MinNumLookups

Minimum probing distance when searching for an entry slot.

MinNumSlots

Smallest capacity of non-empty container.