平坦哈希表

基于开放寻址法的平坦哈希表实现 更多...

类
class	neforce::flat_hashtable< Value, Key, HashFcn, ExtractKey, EqualKey, Alloc >
	平坦哈希表容器 更多...
struct	neforce::flat_hashtable_iterator< IsConst, FlatHT >
	平坦哈希表迭代器 更多...

详细描述

基于开放寻址法的平坦哈希表实现

平坦哈希表采用开放寻址法（Open Addressing）处理冲突， 使用元数据控制块实现 H2 预过滤，大幅减少对数据数组的内存访问。

元数据控制块

每个 slot 对应 1 字节元数据，独立于数据数组存储：

状态	值	含义
EMPTY	0x80	从未使用
DELETED (tombstone)	0xFE	已删除，可复用
H2 tag	[0,127]	7-bit 哈希标签

探测策略

使用线性探测：idx = (idx + 1) & (capacity - 1)。 通过元数据字节的 H2 标签预过滤，仅当 H2 匹配时才访问数据数组进行完整键比较。 支持 SSE2 批量探测：一次加载 16 字节元数据，单指令比较 16 个 slot。

时间复杂度

操作	平均情况	最坏情况
insert	O(1)	O(n)
erase	O(1)	O(n)
find	O(1)	O(n)
rehash	O(n)	O(n)

迭代器失效规则

操作	失效范围
insert	rehash 时全部失效
erase	仅失效指向被删除元素的迭代器
rehash	全部迭代器失效
clear	全部迭代器失效