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

nb	The 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.