Hash functions and containers

Classes
class	cplib::HashTable< T, Hash, Eq >
	Linear probing hash table with std non-compliant interface. More...
struct	cplib::WyHash< T >
	Hash function class like std::hash but uses wyhash. More...

Functions
static uint64_t	wyhash_bytes (const void *key, size_t len)
	Hash function for arbitrary bytes using wyhash.
static uint64_t	wyhash_combine (uint64_t a, uint64_t b)
	Combine two hash values to produce a new hash value.

Detailed Description

Function Documentation

wyhash_bytes()

template<typename T >

static uint64_t wyhash_bytes ( const void *  key, size_t  len  )

related

Hash function for arbitrary bytes using wyhash.

Calls wyhash from https://github.com/wangyi-fudan/wyhash/blob/master/wyhash.h, with a random seed initialized from system random source on startup.

Wyhash is chosen for several characteristics that are specially suited for competitive programming:

• One of the fastest general purpose hash functions as of 2022.
• Very short implementation, little concern about code length limit.
• No known simple attack that can be reasonably carried out during a contest.
• Largely unknown in the competitive programming community, further reducing the likelihood of being hacked.

See also

WyHash<std::string> an example of implementing WyHash specialization using this function.

wyhash_combine()

template<typename T >

static uint64_t wyhash_combine ( uint64_t  a, uint64_t  b  )

related

Combine two hash values to produce a new hash value.

Calls wyhash64 from https://github.com/wangyi-fudan/wyhash/blob/master/wyhash.h.

Use this to implement hash function for types with multiple fields that are recursively hashed, similar to how boost::hash_combine is used for the same purpose.

See also

WyHash<std::pair<T1, T2>> an example of implementing WyHash specialization using this function.