aGrUM  0.14.1
Hash functions

This module lists all hash functions provided by aGrUM. More...

+ Collaboration diagram for Hash functions:

Detailed Description

This module lists all hash functions provided by aGrUM.

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:

template <> class HashFunc<MyObject> : public HashFuncBase<MyObject> {
public:
Size operator() (const MyObject& key) const {
// here write the code using
// HashFuncBase<MyObject>::_hash_size and/or
// HashFuncBase<MyObject>::_hash_log2_size and/or
// HashFuncBase<MyObject>::_hash_mask
}
};

For instance, here is how HashFunc<string> is implemented:

template <> class HashFunc<std::string>: public HashFuncBase<std::string> {
public:
Size operator() (const std::string& key) const {
Size h = 0;
for (size_t i = 0, j = key.size(); i < j; ++i) {
h = 19 * h + key[i];
}
return ((h * GUM_HASHTABLE_INT_GOLD) & _hash_mask);
}
};

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.

Classes

class  gum::HashFunc< bool >
 Hash function for booleans. More...
 
class  gum::HashFunc< int >
 Hash function for integers. More...
 
class  gum::HashFunc< unsigned int >
 Hash function for unsigned integers. More...
 
class  gum::HashFunc< long >
 Hash function for long integers. More...
 
class  gum::HashFunc< unsigned long >
 Hash function for unsigned long integers. More...
 
class  gum::HashFunc< typename HashFuncConditionalType< std::size_t, unsigned long, unsigned int, long, int >::type >
 Hash function for std::size_t. More...
 
class  gum::HashFunc< float >
 Hash function for floats. More...
 
class  gum::HashFunc< double >
 Hash function for doubles. More...
 
class  gum::HashFunc< std::string >
 Hash function for strings. More...
 
class  gum::HashFunc< std::vector< Idx > >
 Hash function for vectors of gum::Idx. More...
 
class  gum::HashFunc< Debug >
 Hash function for gum::Debug. More...
 
class  gum::HashFunc< RefPtr< Type > >
 Hash function for RefPtr. More...
 
class  gum::HashFunc< Instantiation >
 Hash function for gum::Instantiation. More...
 
class  gum::HashFuncConst
 Useful constants for hash functions. More...
 
class  gum::HashFuncBase< Key >
 All hash functions should inherit from this class. More...
 
class  gum::HashFuncSmallKey< Key >
 Generic hash functions for numeric keys smaller than or equal to Size. More...
 
class  gum::HashFuncSmallCastKey< Key >
 Generic hash functions for keys castable as Size and whose size is strictly smaller than that of Size. More...
 
class  gum::HashFuncMediumCastKey< Key >
 Generic hash functions for keys castable as Size and whose size is precisely that of Size. More...
 
class  gum::HashFuncLargeCastKey< Key >
 Generic hash functions for keys castable as Size and whose size is precisely twice that of Size. More...
 
class  gum::HashFuncCastKey< Key >
 Generic hash functions for keys castable as Size whose size is either smaller than Size, or equal to that of one or two Size. More...
 
class  gum::HashFuncConditionalType<... >
 This class enables to safely define hash functions for types that may or may not already has defined hash functionsThere are types that are defined differently depending on the architecture or the compiler you use. More...
 
class  gum::HashFunc< key >
 Class template representing hashing function of LpCol. More...
 

Functions

unsigned int gum::__hashTableLog2 (const Size nb)
 Returns the size in bits - 1 necessary to store the smallest power of 2 greater than or equal to nb. More...
 

Function Documentation

◆ __hashTableLog2()

unsigned int gum::__hashTableLog2 ( const Size  nb)

Returns the size in bits - 1 necessary to store the smallest power of 2 greater than or equal to nb.

In aGrUM, the sizes of hash tables (number of slots) are powers of 2. This is not actually compulsory for the hash function we use. However, as it speeds up the computations of hashed values, we chose to impose this restriction.

Parameters
nbThe greatest number for which this function will return a power of 2.
Returns
Returns the size in bits - 1 necessary to store the smallest power of 2 greater than or equal to nb.

Referenced by gum::HashTable< Val, Size, IndexAllocator >::HashTable(), and gum::HashTable< Val, Size, IndexAllocator >::resize().

+ Here is the caller graph for this function: