哈希算法

哈希模板和哈希算法实现 更多...

类
struct	neforce::hash< coroutine_handle< Promise > >
	coroutine_handle的哈希特化 更多...
struct	neforce::hash< Key, Dummy >
	哈希函数的主模板 更多...
struct	neforce::hash< T * >
	指针类型的哈希特化 更多...
struct	neforce::hash< T, enable_if_t< is_enum_v< T > > >
	枚举类型的哈希特化 更多...
struct	neforce::murmur_hash
	MurmurHash_x64的128位哈希结果容器 更多...
struct	neforce::is_nothrow_hashable< Key, Dummy >
	判断类型是否可无异常哈希 更多...
struct	neforce::is_hash< Func, Arg, Dummy >
	判断类型是否为有效的哈希函数 更多...
struct	neforce::hash< T, enable_if_t< is_base_of< ihashable< T >, T >::value > >
	ihashable的哈希特化 更多...
struct	neforce::hash< shared_ptr< T > >
	shared_ptr的哈希特化 更多...
struct	neforce::hash< unique_ptr< T, Deleter > >
	unique_ptr的哈希特化 更多...

函数
constexpr size_t	neforce::FNV_hash (const byte_t *first, const size_t count) noexcept
	FNV-1a哈希算法
template<typename T>
constexpr size_t	neforce::FNV_hash_integer (const T value) noexcept
	整数类型的FNV哈希
template<typename CharT>
constexpr size_t	neforce::FNV_hash_string (const CharT *str, const size_t len) noexcept
	字符串类型的FNV哈希
constexpr size_t	neforce::low_level_hash (size_t x) noexcept
	快速位混合哈希函数
constexpr size_t	neforce::DJB2_hash (const char *str, const size_t len) noexcept
	DJB2哈希算法
murmur_hash	neforce::murmur_hash64 (const void *key, size_t len, uint32_t seed) noexcept
	MurmurHash3_x64_128算法
uint32_t	neforce::murmur_hash32 (const void *key, size_t len, uint32_t seed) noexcept
	MurmurHash3_x86_32算法
constexpr uint32_t	neforce::XXH32 (const void *input, size_t len, uint32_t seed=0) noexcept
	XXH32 哈希算法
constexpr uint64_t	neforce::XXH64 (const void *input, size_t len, uint64_t seed=0) noexcept
	XXH64 哈希算法
uint64_t	neforce::wyhash (const void *key, size_t len, uint64_t seed) noexcept
	wyhash 哈希算法
size_t	neforce::city_hash64 (const void *key, size_t len) noexcept
	CityHash64 哈希算法
uint64_t	neforce::XXH3_64 (const void *data, size_t len) noexcept
	XXH3_64bits 哈希算法

变量
constexpr size_t	neforce::constants::FNV_OFFSET_BASIS
	FNV哈希算法的偏移基础值
constexpr size_t	neforce::constants::FNV_PRIME = 1099511628211ULL
	FNV哈希算法的质数乘数
template<typename Key>
constexpr bool	neforce::is_nothrow_hashable_v = is_nothrow_hashable<Key>::value
	is_nothrow_hashable的便捷变量模板
template<typename Func, typename Arg>
constexpr bool	neforce::is_hash_v = is_hash<Func, Arg>::value
	is_hash的便捷变量模板

详细描述

哈希模板和哈希算法实现

遵循的国际标准

本实现中的哈希算法参考以下标准规范与学术文献：

哈希算法规范参考：

• **IETF RFC 6234**：US 安全哈希算法 (SHA) 及基于 SHA 的 HMAC 和 HKDF（加密哈希参考） https://www.rfc-editor.org/rfc/rfc6234.html

非加密哈希算法文献：

• **FNV-1a 哈希算法**：Fowler–Noll–Vo 哈希函数规范 https://datatracker.ietf.org/doc/html/draft-eastlake-fnv-17
• **MurmurHash3 算法**：Austin Appleby 设计的非加密哈希函数 https://github.com/aappleby/smhasher/wiki/MurmurHash3
• **DJB2 哈希算法**：Daniel J. Bernstein 设计的字符串哈希函数 http://www.cse.yorku.ca/~oz/hash.html
• **xxHash 算法**：Yann Collet 设计的极速非加密哈希函数族（XXH32/XXH64/XXH3） https://github.com/Cyan4973/xxHash
• **wyhash 算法**：Wang Yi 设计的现代非加密哈希函数 https://github.com/wangyi-fudan/wyhash
• **CityHash 算法**：Google 设计的非加密哈希函数族 https://github.com/google/cityhash

哈希函数安全标准：

• **NIST SP 800-185**：SHA-3 派生函数 — cSHAKE、KMAC、TupleHash、ParallelHash https://csrc.nist.gov/pubs/sp/800/185/final
• **NIST SP 800-107 Rev. 1**：使用已批准哈希算法的应用推荐 https://csrc.nist.gov/pubs/sp/800/107/r1/final

哈希算法对比

算法	输出位数	特点	适用场景
FNV-1a	32/64 位	实现简单、雪崩效应好、碰撞率低	哈希表、编译时哈希
DJB2	32/64 位	极简实现、速度快	简单字符串哈希
MurmurHash3	32/128 位	速度快、分布均匀、可自定义种子	高性能哈希表、Bloom Filter
XXH32	32 位	极速、适合短数据	32 位哈希表、嵌入式系统
XXH64	64 位	极速、适合中等长度数据	64 位哈希表、数据校验
XXH3	64 位	XXH 系列最快、大数据量优化、SIMD 加速	大数据哈希、流式处理
wyhash	64 位	SMHasher 全通、现代设计、128 位乘法	通用哈希表、键值存储
CityHash64	64 位	字符串哈希优化、多级分治	字符串哈希、缓存键
low_level_hash	size_t	单值位混合、零值安全	基本类型 hash 特化的内部基础
hash_combine	size_t	组合多个哈希值	自定义结构体哈希

哈希函数要求

根据 ISO/IEC 14882:2020 §16.4.4，C++ 标准库哈希函数应满足：

• 可调用类型：接受 Key 类型参数，返回 size_t
• 相等性：若 k1 == k2，则 hash(k1) == hash(k2)
• 不抛出异常（推荐）：哈希计算不抛出异常

安全注意事项

警告

重要安全提示**：

• 本文件中的所有算法均为**非加密哈希算法

• 这些算法不应用于安全敏感场景，如密码存储、数字签名、消息认证码
• 非加密哈希算法容易受到哈希碰撞攻击和长度扩展攻击
• 对于安全场景，请使用密码学安全的哈希函数（如 SHA-256、SHA-3、BLAKE2）

参见

https://datatracker.ietf.org/doc/html/draft-eastlake-fnv-17

https://github.com/aappleby/smhasher

https://github.com/Cyan4973/xxHash

https://github.com/google/cityhash

https://en.wikipedia.org/wiki/Hash_function

函数说明

city_hash64()

size_t neforce::city_hash64 ( const void * key, size_t len )

noexcept

CityHash64 哈希算法

参数

key	输入数据指针
len	数据长度

返回

64 位哈希值

Google CityHash 是一种非加密哈希算法，专为字符串哈希优化。 适用于哈希表、字符串匹配等场景。

引用了 city_hash64().

被这些函数引用 city_hash64().

DJB2_hash()

size_t neforce::DJB2_hash ( const char * str, const size_t len )

constexprnoexcept

DJB2哈希算法

参数

str	字符串指针
len	字符串长度

返回

计算出的哈希值

DJB2是一种非加密哈希算法，具有以下特点：

1. 实现简单
2. 速度快
3. 分布均匀

但在某些特殊情况下仍可能出现哈希冲突。

在文件 hash.hpp 第 345 行定义.

引用了 DJB2_hash().

被这些函数引用 DJB2_hash().

FNV_hash()

size_t neforce::FNV_hash ( const byte_t * first, const size_t count )

constexprnoexcept

FNV-1a哈希算法

参数

first	数据的起始字节指针
count	数据的字节数

返回

计算出的哈希值

FNV（Fowler-Noll-Vo）是一种非加密哈希算法，具有：

1. 良好的雪崩效应（avalanche effect）
2. 较低的碰撞率
3. 实现简单高效

FNV_hash函数使用FNV-1a版本算法，先异或再乘法的顺序。

在文件 hash.hpp 第 163 行定义.

引用了 count(), FNV_hash(), neforce::constants::FNV_OFFSET_BASIS , 以及 neforce::constants::FNV_PRIME.

被这些函数引用 FNV_hash(), neforce::thread::id::to_hash() , 以及 neforce::uuid::v7().

FNV_hash_integer()

template<typename T>

size_t neforce::FNV_hash_integer ( const T value )

constexprnoexcept

整数类型的FNV哈希

模板参数

T

整数类型

参数

value

要哈希的整数值

返回

整数的哈希值

在文件 hash.hpp 第 179 行定义.

引用了 FNV_hash_integer(), neforce::constants::FNV_OFFSET_BASIS, neforce::constants::FNV_PRIME , 以及 neforce::integral_constant< bool, Value >::value.

被这些函数引用 FNV_hash_integer().

FNV_hash_string()

template<typename CharT>

size_t neforce::FNV_hash_string ( const CharT * str, const size_t len )

constexprnoexcept

字符串类型的FNV哈希

模板参数

CharT

字符类型

参数

str	字符串指针
len	字符串长度

返回

字符串的哈希值

在文件 hash.hpp 第 199 行定义.

引用了 FNV_hash_string(), neforce::constants::FNV_OFFSET_BASIS, neforce::constants::FNV_PRIME , 以及 neforce::integral_constant< bool, Value >::value.

被这些函数引用 FNV_hash_string() , 以及 neforce::reflect::type_id_for().

low_level_hash()

size_t neforce::low_level_hash ( size_t x )

constexprnoexcept

快速位混合哈希函数

参数

x

输入值

返回

混合后的哈希值

将一个 size_t 值通过位混合操作扩散到整个输出空间。

注解

64 位平台使用 MurmurHash3 fmix64 风格混合器，32 位平台使用 fmix32 风格混合器

在文件 hash.hpp 第 219 行定义.

引用了 low_level_hash().

被这些函数引用 low_level_hash().

murmur_hash32()

uint32_t neforce::murmur_hash32 ( const void * key, size_t len, uint32_t seed )

noexcept

MurmurHash3_x86_32算法

参数

key	要哈希的数据
len	数据长度
seed	哈希种子

返回

32位哈希结果

MurmurHash3的32位版本，产生32位哈希值。 适用于32位系统或需要32位哈希的场景。

引用了 murmur_hash32().

被这些函数引用 murmur_hash32().

murmur_hash64()

murmur_hash neforce::murmur_hash64 ( const void * key, size_t len, uint32_t seed )

noexcept

MurmurHash3_x64_128算法

参数

key	要哈希的数据
len	数据长度
seed	哈希种子

返回

128位哈希结果

MurmurHash是一种非加密哈希算法，具有：

1. 速度快
2. 碰撞率低
3. 可自定义种子

MurmurHash_x64是MurmurHash3的64位版本，产生128位哈希值。

注解

仅64位系统可用

引用了 murmur_hash64().

被这些函数引用 murmur_hash64().

wyhash()

uint64_t neforce::wyhash ( const void * key, size_t len, uint64_t seed )

noexcept

wyhash 哈希算法

参数

key	输入数据指针
len	数据长度
seed	种子值

返回

64 位哈希值

wyhash（Wang Yi's hash）是一种现代非加密哈希算法， 在 SMHasher 测试套件中表现优异，适合哈希表等场景。

引用了 wyhash().

被这些函数引用 wyhash().

XXH32()

uint32_t neforce::XXH32 ( const void * input, size_t len, uint32_t seed = 0 )

constexprnoexcept

XXH32 哈希算法

参数

input	输入数据指针
len	数据长度
seed	种子值，默认为 0

返回

32 位哈希值

xxHash 是一种极速非加密哈希算法，XXH32 是其 32 位版本。 适用于哈希表、数据校验等非安全场景。

在文件 hash.hpp 第 428 行定义.

引用了 end(), neforce::endian::read_le32(), rotate_l32() , 以及 XXH32().

被这些函数引用 neforce::basic_string< char >::to_hash(), neforce::basic_string_view< typename Traits::char_type, Traits >::to_hash() , 以及 XXH32().

XXH3_64()

uint64_t neforce::XXH3_64 ( const void * data, size_t len )

noexcept

XXH3_64bits 哈希算法

参数

data	输入数据指针
len	数据长度

返回

64 位哈希值

XXH3 是 xxHash 系列的最新版本，在 64 位平台上速度极快。 使用内部 192 字节秘密表进行数据混合，适合大数据量哈希。

引用了 data() , 以及 XXH3_64().

被这些函数引用 XXH3_64().

XXH64()

uint64_t neforce::XXH64 ( const void * input, size_t len, uint64_t seed = 0 )

constexprnoexcept

XXH64 哈希算法

参数

input	输入数据指针
len	数据长度
seed	种子值，默认为 0

返回

64 位哈希值

xxHash 的 64 位版本，适合中等到大型数据的哈希。 在 64 位平台上速度极快。

在文件 hash.hpp 第 499 行定义.

引用了 end(), neforce::endian::read_le32(), neforce::endian::read_le64(), rotate_l64() , 以及 XXH64().

被这些函数引用 neforce::basic_string< char >::to_hash(), neforce::basic_string_view< typename Traits::char_type, Traits >::to_hash() , 以及 XXH64().

变量说明

FNV_OFFSET_BASIS

size_t neforce::constants::FNV_OFFSET_BASIS

inlineconstexpr

初始值:

                                 =
 
14695981039346656037ULL

FNV哈希算法的偏移基础值

注解

根据平台位数使用不同的值，文档以64位为例。

在文件 hash.hpp 第 122 行定义.

被这些函数引用 neforce::FNV_hash(), neforce::FNV_hash_integer(), neforce::FNV_hash_string(), neforce::none_t::to_hash(), neforce::optional< T >::to_hash(), neforce::optional< T & >::to_hash() , 以及 neforce::tuple<>::to_hash().

FNV_PRIME

size_t neforce::constants::FNV_PRIME = 1099511628211ULL

inlineconstexpr

FNV哈希算法的质数乘数

注解

根据平台位数使用不同的值，文档以64位为例。

在文件 hash.hpp 第 134 行定义.

被这些函数引用 neforce::FNV_hash(), neforce::FNV_hash_integer() , 以及 neforce::FNV_hash_string().