Hashing

Functions
uint32_t	hashlittle (const void *key, size_t length, uint32_t initval)
uint32_t	hashword (const uint32_t *k, size_t length, uint32_t initval)

Detailed Description

MADNESS uses hashing functions are modeled after Boost.Functional/Hash. It has many similar function calls including hash_value, hash_combine, and hash_range. In addition, it is also compatible with C++ TR1 hashing functors. The madness::Hash functor interface is identical to both boost::hash and std::hash , and any one of these may be used. By default, MADNESS hashing functions can hash all fundamental types including integral types, floating point types, pointer types, std::string, std::wstring, and std::array. Presently hashT is typedef to std::size_t .

Since having a good hash is important, we are using Bob Jenkin's "lookup v3" hash from http://www.burtleburtle.net/bob/c/lookup3.c. The preferred interface for these function is with the madness::Hash<T> functor, but you can also use hash_value or the "lookup v3" interface directly.

Note: Bob Jenkin's "lookup v3" hash returns a uint32_t hash value, which is cast to std::size_t. This is done for compatibility with std::hash.

WARNING: While both std::hash and madness::Hash have the same interface, they will not generate the same hash values from the same key value.

MADNESS hashing consists of one functor and three functions

• madness::Hash is the hash functor and the primary interface for hashing
• hash_value() is for hashing a single value and is the function used by the Hash functor
• hash_range() is for hashing a group of values. You can use this function to hash an iterator range, a C-style array, or a pointer.
• hash_combine() hashs a given value and combines it with a seed. This is useful for combining multiple elements into a single hash value.

There are several options for creating and using hash functions for your custom types. The easiest method is to define a hash_value function for your key type in the same namespace. This function will automatically be used by MADNESS hashing containers. The hashing function should have the following form.

namespace MyNamespace {
 
    class Key {
        // ...
    };
 
    madness::hashT hash_value(const Key& t) {
        // ...
    }
 
} // namespace MyNamespace

If your object is in the madness namespace, you may also use the intrusive method and define a hash member function for your key.

namespace madness {
    class Key {
    public:
 
        // ...
 
        madness::hashT hash() const {
            // ...
        }
    };
}

You can create a specialization of madness::Hash for your type directly.

class Key {
  // ...
};
 
namespace madness {
 
    template <>
    struct Hash<Key> {
        hashT operator()(const Key& a) const {
            // ...
        }
    };
 
} // namespace madness

If you use any of the above methods, MADNESS hash_combine and hash_range functions will be able to hash your custom types.

In addition to these methods, you can use std::hash, boost::hash, or create your own custom hashing functor that has the same form as madness::hash. However, if you want to use a hashing functor other than madness::Hash, you will need to provide the appropriate template parameter to the hashing container.

Function Documentation

hashlittle()

uint32_t hashlittle	(	const void *	key,
		size_t	length,
		uint32_t	initval
	)

References a, b, c, HASH_LITTLE_ENDIAN, k, length, mix, and u().

Referenced by madness::hash_range(), and madness::hash_value().

hashword()

uint32_t hashword	(	const uint32_t *	k,
		size_t	length,
		uint32_t	initval
	)

References a, b, c, k, length, and mix.

Referenced by madness::hash_range(), and madness::hash_value().