THashTable

A Robin-Hood hash table Inspired by [https://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/](https://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/) and [http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/](http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/)

API > API/Runtime > API/Runtime/uLangCore > API/Runtime/uLangCore/uLang > API/Runtime/uLangCore/uLang/Common > API/Runtime/uLangCore/uLang/Common/Containers

References

   
Module uLangCore
Header /Engine/Source/Runtime/Solaris/uLangCore/Public/uLang/Common/Containers/HashTable.h
Include #include "uLang/Common/Containers/HashTable.h"

Syntax

template<class KeyType, class KeyValueType, class HashTraits, class AllocatorType, typename... AllocatorArgsType>  
class THashTable

Remarks

A Robin-Hood hash table Inspired by https://www.sebastiansylvan.com/post/robin-hood-hashing-should-be-your-default-hash-table-implementation/ and http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/

Variables

  Type Name Description
Protected variable AllocatorType _Allocator How to allocate the memory This allocator can be 0 in size
Protected variable SEntry * _Entries  
Protected variable uint32_t _NumEntries  
Protected variable uint32_t _NumOccupied  

Constructors

  Type Name Description
Public function  

THashTable ( AllocatorArgsType&&... AllocatorArgs
)

  
Public function  

THashTable ( const THashTable& Other
)

  
Public function  

THashTable ( THashTable&& Other
)

  

Destructors

  Type Name Description
Public function    

Functions

  Type Name Description
Protected function void Allocate memory according to currently set _NumEntries.
Public function Const ULANG_FORCEINLINEIterator< true >

begin ()

  
Public function ULANG_FORCEINLINEIterator< false >

begin ()

  
Public function Const ULANG_FORCEINLINEIterator< true >

cbegin ()

  
Public function Const ULANG_FORCEINLINEIterator< true >

cend ()

  
Protected function Static ULANG_FORCEINLINE uint32_t

ComputeNonZeroHash ( const KeyType& Key
)

 Hash values in the table must not be zero.
Public function Const ULANG_FORCEINLINE bool

Contains ( const KeyType& Key
)

  
Protected function Const ULANG_FORCEINLINE uint32_t

DesiredPos ( uint32_t Hash
)

 Get desired position for an entry given a hash value.
Public function void

Empty ()

  
Public function Const ULANG_FORCEINLINEIterator< false >

end ()

  
Public function ULANG_FORCEINLINEIterator< false >

end ()

  
Public function Const ULANG_FORCEINLINE const KeyValueType *

Find ( const KeyType& Key
)

  
Public function ULANG_FORCEINLINE KeyValueType *

Find ( const KeyType& Key
)

  
Public function KeyValueType *

FindByPredicate ( Predicate Pred
)

 Finds a key-value pair which matches a predicate functor.
Public function Const const KeyValueType *

FindByPredicate ( Predicate Pred
)

 Finds an key-value pair which matches a predicate functor.
Public function KeyValueType &

FindOrInsert ( KeyValueType&& KeyValue
)

  
Protected function void

Grow ()

 Double the size of the table.
Public function KeyValueType &

Insert ( KeyValueType&& KeyValue
)

  
Public function KeyValueType &

Insert ( const KeyValueType& KeyValue
)

  
Protected function uint32_t

InsertInternal ( uint32_t Hash,
KeyValueType&& Value,
bool* bAlreadyExists
)

 Create a new entry Use Robin Hood mechanism to rearrange entries to minimize probe distance Returns position of new entry
Protected function KeyValueType &

InsertInternal ( KeyValueType&& KeyValue
)

  
Public function Const bool

IsEmpty ()

  
Protected function Const ULANG_FORCEINLINE uint32_t

Lookup ( const KeyType& Key
)

 Look up a key, return its index.
Public function Const ULANG_FORCEINLINE uint32_t

Num ()

  
Protected function Const ULANG_FORCEINLINE uint32_t

ProbeDistance ( uint32_t Hash,
uint32_t Pos
)

 Get probe distance of an entry with given hash and position in entry array.
Public function bool

Remove ( const KeyType& Key
)

  
Public function void

Swap ( THashTable& Other
)

  

Operators

  Type Name Description
Public function THashTable &

operator= ( THashTable Other
)

  

Classes

  Type Name Description
Public class Iterator    
Protected struct SEntry    

Constants

Name Description
MaxLoadFactorDenominator  
MaxLoadFactorNumerator Load factor = what fraction of entries are occupied.

Ask questions and help your peers Developer Forums

Write your own tutorials or read those from others Learning Library

On this page