哈希算法

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

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

函数
NEFORCE_CONSTEXPR14 size_t	FNV_hash (const byte_t *first, const size_t count) noexcept
	FNV-1a哈希算法
template<typename T>
NEFORCE_CONSTEXPR14 size_t	FNV_hash_integer (const T value) noexcept
	整数类型的FNV哈希
template<typename CharT>
NEFORCE_CONSTEXPR14 size_t	FNV_hash_string (const CharT *str, const size_t len) noexcept
	字符串类型的FNV哈希
NEFORCE_CONSTEXPR14 size_t	DJB2_hash (const char *str, const size_t len) noexcept
	DJB2哈希算法
murmur_hash NEFORCE_API	MurmurHash_x64 (const void *key, size_t len, uint32_t seed) noexcept
	MurmurHash3_x64_128算法
uint32_t NEFORCE_API	MurmurHash_x32 (const void *key, size_t len, uint32_t seed) noexcept
	MurmurHash3_x86_32算法

变量
NEFORCE_INLINE17 constexpr size_t	FNV_OFFSET_BASIS
	FNV哈希算法的偏移基础值
NEFORCE_INLINE17 constexpr size_t	FNV_PRIME = 16777619U
	FNV哈希算法的质数乘数
template<typename Key>
NEFORCE_INLINE17 constexpr bool	is_nothrow_hashable_v = is_nothrow_hashable<Key>::value
	is_nothrow_hashable的便捷变量模板
template<typename Func, typename Arg>
constexpr bool	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

哈希函数安全标准：

• **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

哈希函数要求

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

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

安全注意事项

警告

重要安全提示**：

• FNV-1a、DJB2 和 MurmurHash3 均为**非加密哈希算法

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

注解

本文件中的哈希函数实现主要用于哈希表、Bloom Filter、数据分片等 性能敏感的非安全场景。对于需要密码学强度的应用，请使用 NeForce/core/encrypt/ 目录下的 SHA-256 等算法。

参见

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

https://github.com/aappleby/smhasher

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

函数说明

DJB2_hash()

NEFORCE_CONSTEXPR14 size_t DJB2_hash ( const char * str, const size_t len )

noexcept

DJB2哈希算法

参数

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

返回

计算出的哈希值

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

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

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

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

FNV_hash()

NEFORCE_CONSTEXPR14 size_t FNV_hash ( const byte_t * first, const size_t count )

noexcept

FNV-1a哈希算法

参数

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

返回

计算出的哈希值

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

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

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

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

引用了 count().

被这些函数引用 thread::id::to_hash().

FNV_hash_integer()

template<typename T>

NEFORCE_CONSTEXPR14 size_t FNV_hash_integer ( const T value )

noexcept

整数类型的FNV哈希

模板参数

T

整数类型

参数

value

要哈希的整数值

返回

整数的哈希值

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

引用了 integral_constant< bool, Value >::value.

FNV_hash_string()

template<typename CharT>

NEFORCE_CONSTEXPR14 size_t FNV_hash_string ( const CharT * str, const size_t len )

noexcept

字符串类型的FNV哈希

模板参数

CharT

字符类型

参数

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

返回

字符串的哈希值

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

引用了 integral_constant< bool, Value >::value.

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

MurmurHash_x32()

uint32_t NEFORCE_API MurmurHash_x32 ( const void * key, size_t len, uint32_t seed )

noexcept

MurmurHash3_x86_32算法

参数

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

返回

32位哈希结果

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

MurmurHash_x64()

murmur_hash NEFORCE_API MurmurHash_x64 ( 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位系统可用

变量说明

FNV_OFFSET_BASIS

NEFORCE_INLINE17 constexpr size_t FNV_OFFSET_BASIS

constexpr

初始值:

                                           =
 
 
 
2166136261U

FNV哈希算法的偏移基础值

注解

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

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

FNV_PRIME

NEFORCE_INLINE17 constexpr size_t FNV_PRIME = 16777619U

constexpr

FNV哈希算法的质数乘数

注解

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

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