aGrUM  0.13.2
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::pair< int, int > >
 Hash function for pairs of integers. More...
 
class  gum::HashFunc< std::pair< unsigned int, unsigned int > >
 Hash function for pairs of unsigned integers. More...
 
class  gum::HashFunc< std::pair< long, long > >
 Hash function for pairs of long integers. More...
 
class  gum::HashFunc< std::pair< unsigned long, unsigned long > >
 Hash function for pairs of unsigned long integers. More...
 
class  gum::HashFunc< std::pair< float, float > >
 Hash function for pairs of float. More...
 
class  gum::HashFunc< std::pair< double, double > >
 Hash function for pairs of double. More...
 
class  gum::HashFunc< std::pair< double, long unsigned int > >
 Hash function for pairs of double and long unsigned int. More...
 
class  gum::HashFunc< std::pair< double, long int > >
 Hash function for pairs of double and long int. More...
 
class  gum::HashFunc< RefPtr< Type > >
 Hash function for RefPtr. More...
 
class  gum::HashFunc< std::string >
 Hash function for strings. More...
 
class  gum::HashFunc< std::pair< std::string, std::string > >
 Hash function for pairs of 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< Instantiation >
 Hash function for gum::Instantiation. More...
 
class  gum::HashFuncConst
 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 keys smaller than or equal to long integers. More...
 
class  gum::HashFuncSmallCastKey< Key >
 Generic hash functions for keys castable as unsigned longs and whose size is strictly smaller than that of unsigned longs. More...
 
class  gum::HashFuncMediumCastKey< Key >
 Generic hash functions for keys castable as unsigned longs and whose size is precisely that of unsigned longs. More...
 
class  gum::HashFuncLargeCastKey< Key >
 Generic hash functions for keys castable as unsigned longs and whose size is precisely twice that of unsigned longs. More...
 
class  gum::HashFuncSmallKeyPair< Key1, Key2 >
 Generic hash functions for pairs of, at most, two long integer keys. More...
 
class  gum::HashFuncAllCastKeyPair< Key1, Key2, Func1, Func2 >
 Generic hash functions for pairs of keys whose sizes are precisely twice that of unsigned longs and which can be cast into unsigned longs. More...
 
class  gum::HashFuncCastKey< T >
 Generic hash functions for keys castable as unsigned longs whose size is either smaller than unsigned long, or equal to that of one or two unsigned longs. More...
 
class  gum::HashFuncCastKeyPair< T1, T2 >
 Generic hash functions for keys castable as unsigned longs whose size is either smaller than unsigned long, or equal to that of one or two unsigned longs. 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 or equal to nb. More...
 

Function Documentation

unsigned int gum::__hashTableLog2 ( const Size nb)

Returns the size in bits - 1 necessary to store the smallest power of 2 greater 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 wich 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< Key, Val, Alloc >::HashTable(), gum::HashFuncBase< Key >::resize(), and gum::HashTable< Key, Val, Alloc >::resize().

+ Here is the caller graph for this function: