开放地址法

哈希表 - 开放地址法 (Open Addressing)

所有元素存储在数组内，冲突时通过探测序列寻找下一个空槽位。无指针开销，缓存友好。

---

结构定义

typedef struct {
    char *key;
    int value;
    int occupied;      /* 0=空, 1=占用, 2=已删除（墓碑） */
} Slot;
 
typedef struct {
    Slot *slots;
    size_t capacity;
    size_t size;
} OHashMap;

---

探测策略

策略	公式	说明
线性探测	h(k, i) = (h(k) + i) % m	最简单，但易产生集群
二次探测	h(k, i) = (h(k) + c1*i + c2*i²) % m	减少一次集群
双重哈希	h(k, i) = (h1(k) + i * h2(k)) % m	最佳分散，需要两个哈希函数

---

函数签名

函数	复杂度	说明
void oh_init(OHashMap *h, size_t cap)	O(cap)	初始化
void oh_put(OHashMap *h, const char *key, int val)	均摊 O(1)	插入
int oh_get(OHashMap *h, const char *key, int *out)	均摊 O(1)	查找
int oh_remove(OHashMap *h, const char *key)	均摊 O(1)	标记为墓碑
void oh_rehash(OHashMap *h)	O(n)	扩容并丢弃墓碑
void oh_free(OHashMap *h)	O(cap)	释放

---

墓碑机制

删除元素时不设为空，而标记为”已删除”（墓碑）。查找时遇到墓碑继续探测，插入时可复用墓碑槽位。当墓碑过多时触发 rehash 清理。

#define SLOT_EMPTY   0
#define SLOT_OCCUPIED 1
#define SLOT_TOMBSTONE 2

---

链地址法 vs 开放地址法

特性	链地址法	开放地址法
内存开销	每节点一个指针	0
负载因子阈值	可 > 1	必须 < 1（通常 < 0.7）
缓存性能	差（链表跳跃）	好（连续内存）
删除	简单	需墓碑
扩容	所有节点 rehash	所有槽 rehash

---

跨语言参考

• C语言数据结构：哈希表