hash-fct.H File Reference

Collection of general-purpose hash functions. More...

#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <string>
#include <primes.H>

Include dependency graph for hash-fct.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::Buf128Bits

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Macros
#define	hashsize(n)   (1U << (n))
#define	hashmask(n)   (hashsize(n) - 1)
#define	get16bits(d)

Functions
size_t	Aleph::add_hash (const void *key, const size_t len) noexcept
	Additive hash.
size_t	Aleph::xor_hash (const void *key, const size_t len) noexcept
	XOR hash.
size_t	Aleph::rot_hash (const void *key, const size_t len) noexcept
	Rotating hash.
size_t	Aleph::djb_hash (const void *key, const size_t len) noexcept
	Modified Bernstein hash.
size_t	Aleph::sax_hash (const void *key, const size_t len) noexcept
	Shift-Add-XOR hash.
size_t	Aleph::fnv_hash (const void *key, const size_t len) noexcept
	Fowler-Noll-Vo (FNV-1) hash function.
size_t	Aleph::oat_hash (const void *key, const size_t len) noexcept
	One-at-a-Time hash by Bob Jenkins.
size_t	Aleph::jsw_hash (const void *key, size_t len)
	JSW hash (Julienne Walker)
size_t	Aleph::elf_hash (const void *key, const size_t len) noexcept
	ELF hash.
void	Aleph::mix (size_t &a, size_t &b, size_t &c) noexcept
size_t	Aleph::jen_hash (const void *key, const size_t length, const unsigned initval=Default_Hash_Seed) noexcept
	Jenkins hash.
void	Aleph::MurmurHash3_x86_32 (const void *key, int len, uint32_t seed, void *out)
void	Aleph::MurmurHash3_x86_128 (const void *key, const int len, uint32_t seed, void *out)
void	Aleph::MurmurHash3_x64_128 (const void *key, const int len, const uint32_t seed, void *out)
template<typename Key >
size_t	Aleph::murmur3hash (const Key &key, unsigned long seed)
size_t	Aleph::murmur3hash (const char *key, const unsigned long seed)
template<>
size_t	Aleph::murmur3hash (const std::string &key, const unsigned long seed)
size_t	Aleph::SuperFastHash (const void *key, size_t len) noexcept
	Paul Hsieh super fast hash function.
template<typename Key >
size_t	Aleph::add_hash (const Key &key) noexcept
template<typename Key >
size_t	Aleph::xor_hash (const Key &key) noexcept
template<typename Key >
size_t	Aleph::rot_hash (const Key &key) noexcept
template<typename Key >
size_t	Aleph::djb_hash (const Key &key) noexcept
template<typename Key >
size_t	Aleph::sax_hash (const Key &key) noexcept
template<typename Key >
size_t	Aleph::fnv_hash (const Key &key) noexcept
template<typename Key >
size_t	Aleph::oat_hash (const Key &key) noexcept
template<typename Key >
size_t	Aleph::jsw_hash (const Key &key)
	JSW hash for arbitrary key types.
template<typename Key >
size_t	Aleph::elf_hash (const Key &key) noexcept
template<typename Key >
size_t	Aleph::jen_hash (const Key &key, const unsigned initval) noexcept
template<typename Key >
size_t	Aleph::SuperFastHash (const Key &key) noexcept
size_t	Aleph::add_hash (const char *key) noexcept
size_t	Aleph::xor_hash (const char *key) noexcept
size_t	Aleph::rot_hash (const char *key) noexcept
size_t	Aleph::djb_hash (const char *key) noexcept
size_t	Aleph::sax_hash (const char *key) noexcept
size_t	Aleph::fnv_hash (const char *key) noexcept
size_t	Aleph::oat_hash (const char *key) noexcept
size_t	Aleph::jsw_hash (const char *key)
	JSW hash for C strings.
size_t	Aleph::elf_hash (const char *key) noexcept
size_t	Aleph::SuperFastHash (const char *key) noexcept
template<>
size_t	Aleph::add_hash (const std::string &key) noexcept
size_t	Aleph::xor_hash (const std::string &key) noexcept
size_t	Aleph::rot_hash (const std::string &key) noexcept
size_t	Aleph::djb_hash (const std::string &key) noexcept
size_t	Aleph::sax_hash (const std::string &key) noexcept
size_t	Aleph::fnv_hash (const std::string &key) noexcept
size_t	Aleph::oat_hash (const std::string &key) noexcept
size_t	Aleph::jsw_hash (const std::string &key)
	JSW hash for std::string.
size_t	Aleph::elf_hash (const std::string &key) noexcept
size_t	Aleph::jen_hash (const std::string &key, unsigned initval) noexcept
size_t	Aleph::SuperFastHash (const std::string &key) noexcept
template<typename Key >
size_t	Aleph::dft_hash_fct (const Key &key) noexcept
template<typename Key >
size_t	Aleph::snd_hash_fct (const Key &key) noexcept
template<typename Key >
size_t	Aleph::dft_hash_fct (const Key &key, unsigned long seed) noexcept
template<typename Key , typename Data , typename Fct >
size_t	Aleph::map_hash_fct (Fct fct, const std::pair< Key, Data > &p) noexcept
template<typename K1 , typename K2 >
size_t	Aleph::pair_dft_hash_fct (const std::pair< K1, K2 > &p) noexcept
template<typename K1 , typename K2 >
size_t	Aleph::pair_snd_hash_fct (const std::pair< K1, K2 > &p) noexcept

Detailed Description

Collection of general-purpose hash functions.

This file provides a comprehensive collection of hash functions suitable for use in hash tables, bloom filters, checksums, and other applications requiring hash computation.

Hash Function Categories

The functions are organized into several categories:

Simple Hash Functions (Educational/Legacy)

• add_hash() - Simple additive hash (poor distribution)
• xor_hash() - XOR folding hash (poor distribution)
• rot_hash() - Rotating hash (acceptable minimum)

Production-Quality Hash Functions

• djb_hash() - Dan Bernstein's hash (good for small strings)
• sax_hash() - Shift-Add-XOR hash (flexible, good distribution)
• fnv_hash() - Fowler-Noll-Vo hash (simple, effective)
• oat_hash() - One-at-a-Time hash by Bob Jenkins
• jsw_hash() - Julienne Walker's hash (uses random table)
• elf_hash() - ELF object file hash (well-tested)

High-Quality Hash Functions

• jen_hash() - Jenkins hash (excellent avalanche properties)
• SuperFastHash() - Paul Hsieh's fast hash
• murmur3hash() - MurmurHash3 (modern, high-quality)

Usage Examples

#include <hash-fct.H>
using namespace Aleph;
 
// Hash a string
std::string key = "example";
size_t h1 = dft_hash_fct(key);  // Uses SuperFastHash
size_t h2 = fnv_hash(key);      // Uses FNV hash
 
// Hash an integer
int value = 42;
size_t h3 = djb_hash(value);
 
// Hash raw bytes
char data[] = {1, 2, 3, 4};
size_t h4 = jen_hash(data, sizeof(data));
 
// Hash with seed (for double hashing)
size_t h5 = murmur3hash(key, 12345);

References

Most simple hash functions are adapted from Julienne Walker's tutorial: http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

MurmurHash3 is ported from Austin Appleby's implementation: https://github.com/aappleby/smhasher

SuperFastHash is by Paul Hsieh: http://www.azillionmonkeys.com/qed/hash.html

Author

Julienne Walker (original simple hashes)

Bob Jenkins (Jenkins hash, One-at-a-Time)

Austin Appleby (MurmurHash3)

Paul Hsieh (SuperFastHash)

Leandro Rabindranath Leon (adaptation and integration)

This file provides a comprehensive collection of hash functions suitable for use in hash tables, bloom filters, checksums, and other applications requiring hash computation.

Hash Function Categories

The functions are organized into several categories:

Simple Hash Functions (Educational/Legacy)

• add_hash() - Simple additive hash (poor distribution)
• xor_hash() - XOR folding hash (poor distribution)
• rot_hash() - Rotating hash (acceptable minimum)

Production-Quality Hash Functions

• djb_hash() - Dan Bernstein's hash (good for small strings)
• sax_hash() - Shift-Add-XOR hash (flexible, good distribution)
• fnv_hash() - Fowler-Noll-Vo hash (simple, effective)
• oat_hash() - One-at-a-Time hash by Bob Jenkins
• jsw_hash() - Julienne Walker's hash (uses random table)
• elf_hash() - ELF object file hash (well-tested)

High-Quality Hash Functions

• jen_hash() - Jenkins hash (excellent avalanche properties)
• SuperFastHash() - Paul Hsieh's fast hash
• murmur3hash() - MurmurHash3 (modern, high-quality)

Usage Examples

#include <hash-fct.H>
using namespace Aleph;
 
// Hash a string
std::string key = "example";
size_t h1 = dft_hash_fct(key);  // Uses SuperFastHash
size_t h2 = fnv_hash(key);      // Uses FNV hash
 
// Hash an integer
int value = 42;
size_t h3 = djb_hash(value);
 
// Hash raw bytes
char data[] = {1, 2, 3, 4};
size_t h4 = jen_hash(data, sizeof(data));
 
// Hash with seed (for double hashing)
size_t h5 = murmur3hash(key, 12345);

References

Most simple hash functions are adapted from Julienne Walker's tutorial: http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

MurmurHash3 is ported from Austin Appleby's implementation: https://github.com/aappleby/smhasher

SuperFastHash is by Paul Hsieh: http://www.azillionmonkeys.com/qed/hash.html

Author

Julienne Walker (original simple hashes)

Bob Jenkins (Jenkins hash, One-at-a-Time)

Austin Appleby (MurmurHash3)

Paul Hsieh (SuperFastHash)

Leandro Rabindranath Leon (adaptation and integration)

Definition in file hash-fct.H.

Macro Definition Documentation

get16bits

#define get16bits

(

d

)

Value:

                      ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \
                      +(uint32_t)(((const uint8_t *)(d))[0]) )

Definition at line 629 of file hash-fct.H.

hashmask

#define hashmask

(

n

)

(hashsize(n) - 1)

Definition at line 460 of file hash-fct.H.

hashsize

#define hashsize

(

n

)

(1U << (n))

Definition at line 459 of file hash-fct.H.