Blender  V3.3
Classes | Namespaces | Macros | Functions
BLI_hash.hh File Reference
#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.

Classes

struct  blender::DefaultHash< T >
 
struct  blender::DefaultHash< const T >
 
struct  blender::DefaultHash< float >
 
struct  blender::DefaultHash< double >
 
struct  blender::DefaultHash< bool >
 
struct  blender::DefaultHash< std::string >
 
struct  blender::DefaultHash< StringRef >
 
struct  blender::DefaultHash< StringRefNull >
 
struct  blender::DefaultHash< std::string_view >
 
struct  blender::DefaultHash< T * >
 
struct  blender::DefaultHash< std::unique_ptr< T > >
 
struct  blender::DefaultHash< std::shared_ptr< T > >
 
struct  blender::DefaultHash< std::reference_wrapper< T > >
 
struct  blender::DefaultHash< std::pair< T1, T2 > >
 

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)
 

Detailed Description

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.

Definition in file BLI_hash.hh.

Macro Definition Documentation

◆ TRIVIAL_DEFAULT_INT_HASH

#define TRIVIAL_DEFAULT_INT_HASH (   TYPE)
Value:
template<> struct DefaultHash<TYPE> { \
uint64_t operator()(TYPE value) const \
{ \
return static_cast<uint64_t>(value); \
} \
}
SIMD_FORCE_INLINE btVector3 operator()(const btVector3 &x) const
Return the transform of the vector.
Definition: btTransform.h:90
unsigned __int64 uint64_t
Definition: stdint.h:90

Definition at line 118 of file BLI_hash.hh.