Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE > Class Template Reference

#include <hashtable.h>

Detailed Description

template<class KEYTYPE, class VALUETYPE, int TABLE_SIZE = 128, int STACK_SIZE = 1>
class Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >

Organizes key/value pairs by a hash code.

Looks very similar to a Dictionary, but may provide better search times (up to O(1)) by computing a (ideally unique) hash code on the key and using that as an index into an array. The flipside is that the key class must provide a hash code and the memory footprint may be larger then Dictionary.

The default capacity is 128. Matching the capacity against the number of expected elements in the hash table is one key to get optimal insertion and search times, the other is to provide a good (and fast) hash code computation which produces as few collissions as possible for the key type.

The key class must implement the following method in order to work with the HashTable:
uint32_t HashCode() const;

The Util::String class implements this method as an example. Internally the hash table is implemented as a fixed array of sorted arrays. The fixed array is indexed by the hash code of the key, the sorted arrays contain all values with identical keys.

Copyright

(C) 2006 Radon Labs GmbH (C) 2013-2020 Individual contributors, see AUTHORS file

Classes
class	Iterator

Public Member Functions
	HashTable ()
	default constructor
	HashTable (const HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE > &rhs)
	copy constructor
	HashTable (HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE > &&rhs)
	move constructor
void	operator= (const HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE > &rhs)
	assignment operator
void	operator= (HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE > &&rhs)
	move assignment operator
VALUETYPE &	operator[] (const KEYTYPE &key) const
	read/write [] operator, assertion if key not found
SizeT	Size () const
	return current number of values in the hashtable
SizeT	Capacity () const
	return fixed-size capacity of the hash table
void	Clear ()
	clear the hashtable
void	Reset ()
	reset the hashtable arrays to 0 size, but don't run destructor
bool	IsEmpty () const
	return true if empty
void	BeginBulkAdd ()
	begin bulk adding to the hashtable, which will amortize the cost of sorting the hash buckets upon end
const bool	IsBulkAdd () const
	returns true if currently bulk adding
IndexT	Add (const KeyValuePair< KEYTYPE, VALUETYPE > &kvp)
	add a key/value pair object to the hash table, returns index within hash array where item is stored
IndexT	Add (const KEYTYPE &key, const VALUETYPE &value)
	add a key and associated value
VALUETYPE &	Emplace (const KEYTYPE &key)
	adds element only if it doesn't exist, and return reference to it
void	EndBulkAdd ()
	end bulk adding, which sorts all affected tables
void	Merge (const HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE > &rhs)
	merge two dictionaries
void	Erase (const KEYTYPE &key)
	erase an entry
void	EraseIndex (const KEYTYPE &key, IndexT i)
	erase an entry with known index
bool	Contains (const KEYTYPE &key) const
	return true if key exists in the array
IndexT	FindIndex (const KEYTYPE &key) const
	find index in bucket
VALUETYPE &	ValueAtIndex (const KEYTYPE &key, IndexT i) const
	get value from key and bucket
StackArray< KeyValuePair< KEYTYPE, VALUETYPE >, STACK_SIZE >	Content () const
	return array of all key/value pairs in the table (slow)
StackArray< KEYTYPE, STACK_SIZE >	KeysAsArray () const
	get all keys as an Util::Array (slow)
StackArray< VALUETYPE, STACK_SIZE >	ValuesAsArray () const
	get all keys as an Util::Array (slow)
Iterator	Begin ()
	get iterator to first element
Iterator	End ()
	get iterator to last element

Private Member Functions
template<typename HASHKEY >
const uint32_t	GetHashCode (const typename std::enable_if< std::is_integral< HASHKEY >::value, HASHKEY >::type &key) const
	if type is integral, just use that value directly
template<typename HASHKEY >
const uint32_t	GetHashCode (const HASHKEY &key) const
	if not, call the function on HashCode on HASHKEY
template<typename HASHKEY >
const uint32_t	GetHashCode (const typename std::enable_if< std::is_pointer< HASHKEY >::value, HASHKEY >::type &key) const
	if type is pointer, convert using questionable method

Private Attributes
FixedArray< StackArray< KeyValuePair< KEYTYPE, VALUETYPE >, STACK_SIZE > >	hashArray
int	size
FixedArray< bool >	bulkDirty
bool	inBulkAdd

Constructor & Destructor Documentation

HashTable() [1/3]

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::HashTable

(

)

default constructor

HashTable() [2/3]

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::HashTable

(

const HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE > &

rhs

)

copy constructor

HashTable() [3/3]

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::HashTable

(

HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE > &&

rhs

)

move constructor

Member Function Documentation

Add() [1/2]

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

IndexT Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::Add	(	const KEYTYPE &	key,
		const VALUETYPE &	value )

add a key and associated value

Add() [2/2]

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

IndexT Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::Add

(

const KeyValuePair< KEYTYPE, VALUETYPE > &

kvp

)

add a key/value pair object to the hash table, returns index within hash array where item is stored

Begin()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::Iterator Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::Begin

(

)

get iterator to first element

BeginBulkAdd()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

void Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::BeginBulkAdd

(

)

begin bulk adding to the hashtable, which will amortize the cost of sorting the hash buckets upon end

Capacity()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

SizeT Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::Capacity

(

)

const

return fixed-size capacity of the hash table

Clear()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

void Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::Clear

(

)

clear the hashtable

Contains()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

bool Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::Contains

(

const KEYTYPE &

key

)

const

return true if key exists in the array

Content()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

StackArray< KeyValuePair< KEYTYPE, VALUETYPE >, STACK_SIZE > Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::Content

(

)

const

return array of all key/value pairs in the table (slow)

Emplace()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

VALUETYPE & Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::Emplace

(

const KEYTYPE &

key

)

adds element only if it doesn't exist, and return reference to it

End()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::Iterator Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::End

(

)

get iterator to last element

EndBulkAdd()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

void Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::EndBulkAdd

(

)

end bulk adding, which sorts all affected tables

Erase()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

void Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::Erase

(

const KEYTYPE &

key

)

erase an entry

EraseIndex()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

void Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::EraseIndex	(	const KEYTYPE &	key,
		IndexT	i )

erase an entry with known index

FindIndex()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

IndexT Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::FindIndex

(

const KEYTYPE &

key

)

const

find index in bucket

GetHashCode() [1/3]

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE = 128, int STACK_SIZE = 1>

template<typename HASHKEY >

const uint32_t Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::GetHashCode ( const HASHKEY & key ) const

inlineprivate

if not, call the function on HashCode on HASHKEY

GetHashCode() [2/3]

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE = 128, int STACK_SIZE = 1>

template<typename HASHKEY >

const uint32_t Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::GetHashCode ( const typename std::enable_if< std::is_integral< HASHKEY >::value, HASHKEY >::type & key ) const

inlineprivate

if type is integral, just use that value directly

GetHashCode() [3/3]

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE = 128, int STACK_SIZE = 1>

template<typename HASHKEY >

const uint32_t Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::GetHashCode ( const typename std::enable_if< std::is_pointer< HASHKEY >::value, HASHKEY >::type & key ) const

inlineprivate

if type is pointer, convert using questionable method

IsBulkAdd()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

const bool Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::IsBulkAdd ( ) const

inline

returns true if currently bulk adding

IsEmpty()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

bool Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::IsEmpty

(

)

const

return true if empty

KeysAsArray()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

StackArray< KEYTYPE, STACK_SIZE > Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::KeysAsArray

(

)

const

get all keys as an Util::Array (slow)

Merge()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

void Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::Merge

(

const HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE > &

rhs

)

merge two dictionaries

operator=() [1/2]

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

void Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::operator=

(

const HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE > &

rhs

)

assignment operator

operator=() [2/2]

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

void Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::operator=

(

HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE > &&

rhs

)

move assignment operator

operator[]()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

VALUETYPE & Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::operator[]

(

const KEYTYPE &

key

)

const

read/write [] operator, assertion if key not found

Reset()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

void Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::Reset

(

)

reset the hashtable arrays to 0 size, but don't run destructor

Size()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

SizeT Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::Size

(

)

const

return current number of values in the hashtable

ValueAtIndex()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

VALUETYPE & Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::ValueAtIndex	(	const KEYTYPE &	key,
		IndexT	i ) const

get value from key and bucket

ValuesAsArray()

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE, int STACK_SIZE>

StackArray< VALUETYPE, STACK_SIZE > Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::ValuesAsArray

(

)

const

get all keys as an Util::Array (slow)

Member Data Documentation

bulkDirty

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE = 128, int STACK_SIZE = 1>

FixedArray<bool> Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::bulkDirty

private

hashArray

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE = 128, int STACK_SIZE = 1>

FixedArray<StackArray<KeyValuePair<KEYTYPE, VALUETYPE>, STACK_SIZE> > Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::hashArray

private

inBulkAdd

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE = 128, int STACK_SIZE = 1>

bool Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::inBulkAdd

private

size

template<class KEYTYPE , class VALUETYPE , int TABLE_SIZE = 128, int STACK_SIZE = 1>

int Util::HashTable< KEYTYPE, VALUETYPE, TABLE_SIZE, STACK_SIZE >::size

private

---

The documentation for this class was generated from the following file:

• /github/workspace/code/foundation/util/hashtable.h