 |
aGrUM
0.20.3
a C++ library for (probabilistic) graphical models
|
|
aGrUM
0.20.3
a C++ library for (probabilistic) graphical models
|
All hash functions should inherit from this class. More...
#include <agrum/tools/core/hashFunc.h>
Inheritance diagram for gum::HashFuncBase< Key >:Public Member Functions | |
| void | resize (const Size new_size) |
| Update the hash function to take into account a resize of the hash table. More... | |
| Size | size () const |
| Returns the hash table size as known by the hash function. More... | |
| virtual Size | operator() (const Key &key) const =0 |
| Computes the hashed value of a key. More... | |
Protected Attributes | |
| Size | hash_size_ {Size(0)} |
| The size of the hash table. More... | |
| unsigned int | hash_log2_size_ {0} |
| Log of the number of slots of the hash table in base 2. More... | |
| Size | hash_mask_ {Size(0)} |
| performing y = x & hash_mask_ guarantees that y is a slot index of the hash table More... | |
| unsigned int | right_shift_ {0} |
| performing y = x >> right_shift_ guarantees that y is a slot index of the hash table More... | |
All hash functions should inherit from this class.
Whenever you create a new hash function you must inherit from this class. Otherwise, your hash function will not compile because gum::HashTable will refer directly to this class.
The way gum::HashTable work, you do not need to define constructors, destructors and assignment operators: the defaults created by C++ will work correctly. However, if your hash function contains new attributes, you must override the resize function to properly set these attributes. You may even have to redefine the default constructor and/or the assignment operator, but this should not occur very often.
In fact, usually, when you create a new hash function, you will only need to write something like:
For instance, here is how HashFunc<string> is implemented:
The gum::HashFunc::hash_size_ attribute corresponds to the number of slots in the gum::HashTable. Your function should always return a number in [0,hash_size). As the number of slots in a gum::HashTable is always a power of 2, it may be convenient to know the number of bits used by the hashed keys, this is precisely the information contained in gum::HashFunc::hash_log2_size. Finally, gum::HashFunc::hash_mask_ is a mask that can be used to ensure that the hashed key actually belongs to [0,_hash_size). This is used in particular in the hash function for hashing strings.
| Key | The type hashed by this hash function. |
Definition at line 148 of file hashFunc.h.
|
pure virtual |
Computes the hashed value of a key.
The classes inheriting from HashFuncBase should always declare Operator() as follows:
and its implementation should be something like:
By doing this, compilers optimize the code so that it is significantly speeded-up because no virtual table will be used and everything is most certainly inlined. Of course, you need to define a static method castToSize which should take as argument a const Key& and return a Size
| key | The key to compute the hashed value. |
Implemented in gum::HashFunc< Instantiation >, gum::HashFunc< Set< T, Alloc > >, gum::HashFunc< RefPtr< Type > >, gum::HashFunc< Debug >, gum::HashFunc< std::vector< Idx > >, gum::HashFunc< std::string >, gum::HashFunc< learning::EdgeDeletion >, gum::HashFunc< learning::EdgeAddition >, gum::HashFunc< learning::ArcReversal >, gum::HashFunc< learning::ArcDeletion >, gum::HashFunc< learning::ArcAddition >, gum::HashFunc< learning::GraphChange >, gum::HashFunc< std::pair< Key1, Key2 > >, gum::HashFunc< learning::IdCondSet< ALLOC > >, gum::HashFuncLargeCastKey< Key >, gum::HashFuncMediumCastKey< Key >, gum::HashFuncSmallCastKey< Key >, gum::HashFuncSmallKey< Key >, gum::HashFuncSmallKey< long >, gum::HashFuncSmallKey< unsigned long >, gum::HashFuncSmallKey< int >, gum::HashFuncSmallKey< unsigned int >, gum::HashFuncSmallKey< bool >, gum::HashFunc< credal::lp::LpCol >, and gum::HashFunc< std::tuple< unsigned int, unsigned int, unsigned int > >.
| void gum::HashFuncBase< Key >::resize | ( | const Size | new_size | ) |
Update the hash function to take into account a resize of the hash table.
When the user wishes to resize the gum::HashTable so that the array is of size s, the gum::HashTable resizes itself to the smallest power of 2 greater than or equal to s. This new size is computed by function gum::HashFuncBase::resize(gum::Size). Hence, s should be the size of the array of lists, not the number of elements stored into the gum::HashTable.
| new_size | The hashtable's size wished by the user. Actually, a hashtable of size n is an array of n lists. |
| SizeError | Raised if s is too small. |
| Size gum::HashFuncBase< Key >::size | ( | ) | const |
Returns the hash table size as known by the hash function.
|
protected |
Log of the number of slots of the hash table in base 2.
Definition at line 203 of file hashFunc.h.
|
protected |
performing y = x & hash_mask_ guarantees that y is a slot index of the hash table
To transform a Size x into a slot index of the hash table, you can either use x & hash_mask_ or x >> right_shift_ depending on whether you want to exploit the least significant bits of x (&) or the most significant one (>>).
Definition at line 214 of file hashFunc.h.
|
protected |
The size of the hash table.
Definition at line 200 of file hashFunc.h.
|
protected |
performing y = x >> right_shift_ guarantees that y is a slot index of the hash table
To transform a Size x into a slot index of the hash table, you can either use x & hash_mask_ or x >> right_shift_ depending on whether you want to exploit the least significant bits of x (&) or the most significant one (>>).
Definition at line 225 of file hashFunc.h.