Blender
V3.3
|
#include <functional>
#include <memory>
#include <string>
#include <utility>
#include "BLI_math_base.h"
#include "BLI_string_ref.hh"
#include "BLI_utildefines.h"
Go to the source code of this file.
Namespaces | |
blender | |
Macros | |
#define | TRIVIAL_DEFAULT_INT_HASH(TYPE) |
Functions | |
blender::TRIVIAL_DEFAULT_INT_HASH (int8_t) | |
blender::TRIVIAL_DEFAULT_INT_HASH (uint8_t) | |
blender::TRIVIAL_DEFAULT_INT_HASH (int16_t) | |
blender::TRIVIAL_DEFAULT_INT_HASH (uint16_t) | |
blender::TRIVIAL_DEFAULT_INT_HASH (int32_t) | |
blender::TRIVIAL_DEFAULT_INT_HASH (uint32_t) | |
blender::TRIVIAL_DEFAULT_INT_HASH (int64_t) | |
blender::TRIVIAL_DEFAULT_INT_HASH (uint64_t) | |
uint64_t | blender::hash_string (StringRef str) |
template<typename T > | |
uint64_t | blender::get_default_hash (const T &v) |
template<typename T1 , typename T2 > | |
uint64_t | blender::get_default_hash_2 (const T1 &v1, const T2 &v2) |
template<typename T1 , typename T2 , typename T3 > | |
uint64_t | blender::get_default_hash_3 (const T1 &v1, const T2 &v2, const T3 &v3) |
template<typename T1 , typename T2 , typename T3 , typename T4 > | |
uint64_t | blender::get_default_hash_4 (const T1 &v1, const T2 &v2, const T3 &v3, const T4 &v4) |
A specialization of blender::DefaultHash<T>
provides a hash function for values of type T. This hash function is used by default in hash table implementations in blenlib.
The actual hash function is in the operator()
method of DefaultHash<T>
. The following code computes the hash of some value using DefaultHash.
T value = ...; DefaultHash<T> hash_function; uint32_t hash = hash_function(value);
Hash table implementations like blender::Set support heterogeneous key lookups. That means that one can do a lookup with a key of type A in a hash table that stores keys of type B. This is commonly done when B is std::string, because the conversion from e.g. a #StringRef to std::string can be costly and is unnecessary. To make this work, values of type A and B that compare equal have to have the same hash value. This is achieved by defining potentially multiple operator()
in a specialization of #DefaultHash. All those methods have to compute the same hash for values that compare equal.
The computed hash is an unsigned 64 bit integer. Ideally, the hash function would generate uniformly random hash values for a set of keys. However, in many cases trivial hash functions are faster and produce a good enough distribution. In general it is better when more information is in the lower bits of the hash. By choosing a good probing strategy, the effects of a bad hash function are less noticeable though. In this context a good probing strategy is one that takes all bits of the hash into account eventually. One has to check on a case by case basis to see if a better but more expensive or trivial hash function works better.
There are three main ways to provide a hash table implementation with a custom hash function.
hash
member function to it. The function should return uint64_t
and take no arguments. This method will be called by the default implementation of #DefaultHash. It will automatically be used by hash table implementations.When you want to provide a default hash function for a type that you cannot modify: Add a new specialization to the #DefaultHash struct. This can be done by writing code like below in either global or BLI namespace.
template<> struct blender::DefaultHash<TheType> { uint64_t operator()(const TheType &value) const { return ...; } };
When you want to provide a different hash function for a type that already has a default hash function: Implement a struct like the one below and pass it as template parameter to the hash table explicitly.
struct MyCustomHash { uint64_t operator()(const TheType &value) const { return ...; } };
Definition in file BLI_hash.hh.
#define TRIVIAL_DEFAULT_INT_HASH | ( | TYPE | ) |
Definition at line 118 of file BLI_hash.hh.