HashTable
Engine/source/core/util/tDictionary.h
A HashTable template class.
Classes:
Public Types
Private Attributes
Private Functions
Public Functions
begin()
Iterator to first element.
Returns the average number of nodes per bucket.
end()
Iterator to last element + 1.
findOrInsert(const Key & key)
Find the key, or insert a one if it doesn't exist.
insertEqual(const Key & key, const Value & )
Insert the key value pair and allow duplicates.
insertUnique(const Key & key, const Value & )
Insert the key value pair but don't insert duplicates.
bool
isEmpty()
Returns true if the table is empty.
Detailed Description
A HashTable template class.
The hash table class maps between a key and an associated value. Access using the key is performed using a hash table. The class provides methods for both unique and equal keys. The global ::hash(Type) function is used for hashing, see util/hash.h
Public Types
typedef _Iterator< const Pair, const Node, const HashTable > ConstIterator
typedef const Pair & ConstReference
typedef S32 DifferenceType
typedef _Iterator< Pair, Node, HashTable > Iterator
typedef Pair & Reference
typedef U32 SizeType
typedef Pair ValueType
Private Attributes
ClassChunker< Node > mNodeAllocator
U32 mSize
Number of keys in the table.
Node ** mTable
Hash table.
S32 mTableSize
Hash table size.
Private Functions
_destroy()
_hash(const Key & key)
_index(const Key & key)
_next(U32 index)
_resize(U32 size)
Public Functions
HashTable()
HashTable(const HashTable & p)
~HashTable()
begin()
Iterator to first element.
begin()
Iterator to first element.
clear()
Empty the HashTable.
collisions()
Returns the average number of nodes per bucket.
count(const Key & )
Count the number of matching keys in the table.
end()
Iterator to last element + 1.
end()
Iterator to last element + 1.
erase(const Key & key)
Erase all matching keys from the table.
erase(const Key & key, const Value & value)
Erase entry for this key-value pair.
erase(Iterator )
Erase the given entry.
find(const Key & )
Find the first entry for the given key.
find(const Key & )
Find the first entry for the given key.
find(const Key & key, Value & value)
Find the first entry for the given key.
findOrInsert(const Key & key)
Find the key, or insert a one if it doesn't exist.
Returns the first key in the table that matches, or inserts one if there are none.
insertEqual(const Key & key, const Value & )
Insert the key value pair and allow duplicates.
This insert method allows duplicate keys. Keys are grouped together but are not sorted.
insertUnique(const Key & key, const Value & )
Insert the key value pair but don't insert duplicates.
This insert method does not insert duplicate keys. If the key already exists in the table the function will fail and end() is returned.
isEmpty()
Returns true if the table is empty.
operator=(const HashTable & p)
resize(U32 size)
Resize the bucket table for an estimated number of elements.
This method will optimize the hash bucket table size to hold the given number of elements. The size argument is a hint, and will not be the exact size of the table. If the table is sized down below it's optimal size, the next insert will cause it to be resized again. Normally this function is used to avoid resizes when the number of elements that will be inserted is known in advance.
size()
Return the number of elements.
tableSize()
Return the size of the hash bucket table.