Loading...
Searching...
No Matches
DataHashTable< HashItem, Info > Class Template Reference Generic hash table for data objects. More...
Detailed DescriptionGeneric hash table for data objects. Class DataHashTable provides a generic hash table for Data Objects, i.e., a map that maps arguments called HashItems to values called Infos. HashItem and Info types are passed as template arguments. HashItems must provide a comparison operator==(). Furthermore, both the HashItem and Info must be data objects in the sense that the assignment operator is equivalent to a The construction of a DataHashTable requires a hash function that assigns an integer value to every HashItem. Provided this, pairs of a HashItem and a Info can be added to the DataHashTable. No more than one Info can be assigned to the same HashItem at a time. The Info to a HashItem can be accessed through the subscript operator[]() with the Info object as a subscript. The maximum number of elemens a DataHashTable can hold can be specified upon construction and may be reset with reMax() later on. Further, a value hash size value is required. This value must be less then the maximum number of elements and must not have a common dominator with the maximum number of elements. If not specified explicitely, it is set automatically to a reasonable value. The implementation relies on an array of DataHashTable::Elements, from now on referred to as elements. Upon construction, all elements are marked as Removing elements is simply done by marking it as Further, memory management with resizing of the element array is straight forward. Definition at line 88 of file datahashtable.h. Member Typedef Documentation◆ ElemDefinition at line 112 of file datahashtable.h. Constructor & Destructor Documentation◆ DataHashTable() [1/2]
default constructor. Allocates a DataHashTable for
Definition at line 293 of file datahashtable.h. References DataHashTable< HashItem, Info >::autoHashSize(), DataHashTable< HashItem, Info >::clear(), DataHashTable< HashItem, Info >::isConsistent(), DataHashTable< HashItem, Info >::m_hashsize, DataHashTable< HashItem, Info >::m_memfactor, DataHashTable< HashItem, Info >::nprimes, and DataHashTable< HashItem, Info >::primes. ◆ DataHashTable() [2/2]
copy constructor. Definition at line 372 of file datahashtable.h. References DataHashTable< HashItem, Info >::isConsistent(), DataHashTable< HashItem, Info >::m_memfactor, and DataHashTable< HashItem, Info >::primes. Member Function Documentation◆ add()adds a new entry to the hash table. Adds a new entry consisting of HashItem Definition at line 177 of file datahashtable.h. References DataHashTable< HashItem, Info >::has(), HASHTABLE_FILLFACTOR, DataHashTable< HashItem, Info >::m_elem, DataHashTable< HashItem, Info >::m_hashfun, DataHashTable< HashItem, Info >::m_hashsize, DataHashTable< HashItem, Info >::m_memfactor, DataHashTable< HashItem, Info >::m_used, DataHashTable< HashItem, Info >::reMax(), and DataArray< T >::size(). Referenced by DataHashTable< HashItem, Info >::reMax(). ◆ autoHashSize()determine a good m_hashsize. Determine next larger prime number for new m_hashsize
Definition at line 395 of file datahashtable.h. References DataHashTable< HashItem, Info >::m_elem, DataHashTable< HashItem, Info >::nprimes, DataHashTable< HashItem, Info >::primes, and DataArray< T >::size(). Referenced by DataHashTable< HashItem, Info >::DataHashTable(), and DataHashTable< HashItem, Info >::reMax(). ◆ autoHashSizeold()automatically computes a good m_hashsize. Computes a good m_hashsize as the product of all prime numbers not divisors of the number of elements that are <= the maximum divisor of the number of elemens.
Definition at line 432 of file datahashtable.h. References DataHashTable< HashItem, Info >::m_elem, and DataArray< T >::size(). ◆ clear()remove all entries from DataHashTable. Definition at line 218 of file datahashtable.h. References DataHashTable< HashItem, Info >::m_elem, DataHashTable< HashItem, Info >::m_used, and DataArray< T >::size(). Referenced by DataHashTable< HashItem, Info >::DataHashTable(), and DataHashTable< HashItem, Info >::reMax(). ◆ get()returns const pointer to Info of HashItem Returns a pointer to Info component of hash element Definition at line 151 of file datahashtable.h. References DataHashTable< HashItem, Info >::index(), and DataHashTable< HashItem, Info >::m_elem. ◆ has()Is item Definition at line 141 of file datahashtable.h. References DataHashTable< HashItem, Info >::index(). Referenced by DataHashTable< HashItem, Info >::add(), DataHashTable< HashItem, Info >::isConsistent(), DataHashTable< HashItem, Info >::operator[](), and DataHashTable< HashItem, Info >::remove(). ◆ index()returns hash index of HashItem Using the hash function m_hashfun, the hash value of
Definition at line 475 of file datahashtable.h. References DataHashTable< HashItem, Info >::m_elem, DataHashTable< HashItem, Info >::m_hashsize, DataHashTable< HashItem, Info >::m_used, and DataArray< T >::size(). Referenced by DataHashTable< HashItem, Info >::get(), DataHashTable< HashItem, Info >::has(), DataHashTable< HashItem, Info >::operator[](), and DataHashTable< HashItem, Info >::remove(). ◆ isConsistent()checks whether DataHashTable is consistent Definition at line 251 of file datahashtable.h. References DataHashTable< HashItem, Info >::has(), DataArray< T >::isConsistent(), DataHashTable< HashItem, Info >::m_elem, DataHashTable< HashItem, Info >::m_used, MSGinconsistent, and DataArray< T >::size(). Referenced by DataHashTable< HashItem, Info >::DataHashTable(), DataHashTable< HashItem, Info >::DataHashTable(), and DataHashTable< HashItem, Info >::operator=(). ◆ operator=()
assignment operator. Definition at line 356 of file datahashtable.h. References DataHashTable< HashItem, Info >::isConsistent(), DataHashTable< HashItem, Info >::m_elem, DataHashTable< HashItem, Info >::m_hashfun, DataHashTable< HashItem, Info >::m_hashsize, DataHashTable< HashItem, Info >::m_memfactor, DataHashTable< HashItem, Info >::m_used, DataHashTable< HashItem, Info >::nprimes, and DataHashTable< HashItem, Info >::primes. ◆ operator[]()references Info of HashItem Index operator for accessing the Info associated to HashItem Definition at line 164 of file datahashtable.h. References DataHashTable< HashItem, Info >::has(), DataHashTable< HashItem, Info >::index(), and DataHashTable< HashItem, Info >::m_elem. ◆ reMax()reset size of the DataHashTable. Reset the maximum number of elements of a DataHashTable to Definition at line 231 of file datahashtable.h. References DataHashTable< HashItem, Info >::add(), DataHashTable< HashItem, Info >::autoHashSize(), DataHashTable< HashItem, Info >::clear(), DataHashTable< HashItem, Info >::m_elem, DataHashTable< HashItem, Info >::m_hashsize, DataHashTable< HashItem, Info >::m_used, DataArray< T >::reSize(), and DataArray< T >::size(). Referenced by DataHashTable< HashItem, Info >::add(). ◆ remove()remove HashItem Definition at line 205 of file datahashtable.h. References DataHashTable< HashItem, Info >::has(), DataHashTable< HashItem, Info >::index(), DataHashTable< HashItem, Info >::m_elem, and DataHashTable< HashItem, Info >::m_used. Member Data Documentation◆ m_elemstores all elements of the hash table Definition at line 119 of file datahashtable.h. Referenced by DataHashTable< HashItem, Info >::add(), DataHashTable< HashItem, Info >::autoHashSize(), DataHashTable< HashItem, Info >::autoHashSizeold(), DataHashTable< HashItem, Info >::clear(), DataHashTable< HashItem, Info >::get(), DataHashTable< HashItem, Info >::index(), DataHashTable< HashItem, Info >::isConsistent(), DataHashTable< HashItem, Info >::operator=(), DataHashTable< HashItem, Info >::operator[](), DataHashTable< HashItem, Info >::reMax(), and DataHashTable< HashItem, Info >::remove(). ◆ m_hashfunpointer to hash function (mapping: HashItem -> int) Definition at line 125 of file datahashtable.h. Referenced by DataHashTable< HashItem, Info >::add(), and DataHashTable< HashItem, Info >::operator=(). ◆ m_hashsizeincrement added to hash index, if allready used Definition at line 121 of file datahashtable.h. Referenced by DataHashTable< HashItem, Info >::add(), DataHashTable< HashItem, Info >::DataHashTable(), DataHashTable< HashItem, Info >::index(), DataHashTable< HashItem, Info >::operator=(), and DataHashTable< HashItem, Info >::reMax(). ◆ m_memfactormemory is reMax()ed by this factor if a new element does't fit Definition at line 127 of file datahashtable.h. Referenced by DataHashTable< HashItem, Info >::add(), DataHashTable< HashItem, Info >::DataHashTable(), DataHashTable< HashItem, Info >::DataHashTable(), and DataHashTable< HashItem, Info >::operator=(). ◆ m_usedcurrent number of entries in the hash table Definition at line 123 of file datahashtable.h. Referenced by DataHashTable< HashItem, Info >::add(), DataHashTable< HashItem, Info >::clear(), DataHashTable< HashItem, Info >::index(), DataHashTable< HashItem, Info >::isConsistent(), DataHashTable< HashItem, Info >::operator=(), DataHashTable< HashItem, Info >::reMax(), and DataHashTable< HashItem, Info >::remove(). ◆ nprimesnumber of stored prime numbers Definition at line 131 of file datahashtable.h. Referenced by DataHashTable< HashItem, Info >::autoHashSize(), DataHashTable< HashItem, Info >::DataHashTable(), and DataHashTable< HashItem, Info >::operator=(). ◆ primessome prime numbers for fast access Definition at line 129 of file datahashtable.h. Referenced by DataHashTable< HashItem, Info >::autoHashSize(), DataHashTable< HashItem, Info >::DataHashTable(), DataHashTable< HashItem, Info >::DataHashTable(), and DataHashTable< HashItem, Info >::operator=().
|