如何在静态数组中存储哈希映射？以C语言及伪代码演示

嘿，我来给你捋捋怎么用静态数组实现这种固定大小的哈希映射——毕竟你要的是条目数量有上限的场景，用两个平行数组keys[N]和values[N]完全可行，甚至还挺直观的。下面我用C语言（适配你提到的int类型Key）和伪代码一步步演示，也会给通用版本的思路。

本质上就是用两个长度相同的静态数组分别存键和对应的值，再额外加一个状态数组标记每个位置的状态（空闲/已占用/已删除）——这一步很关键，不然处理哈希冲突或者删除操作时会出问题。整个结构对应的隐式字典就是你说的{keys[i]: values[i]...}，但我们要通过哈希函数和冲突处理逻辑来维护这个映射关系。

先从最贴合你场景的int Key版本开始：

1. 定义基础数据结构 #

我们先把类型和常量定下来，状态数组用来追踪每个位置的可用性：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int Key;          // 你的Key类型是int
typedef int Value;        // Value可以换成任意类型，这里先用int演示
#define MAX_CAPACITY 100 // 固定的条目上限，根据你的需求调整

// 标记每个数组位置的状态
typedef enum {
    EMPTY,    // 从未被使用过
    OCCUPIED, // 当前存着有效键值对
    DELETED   // 曾经存过但已删除
} EntryState;

// 静态哈希映射的结构体，把三个数组打包在一起
typedef struct {
    Key keys[MAX_CAPACITY];
    Value values[MAX_CAPACITY];
    EntryState states[MAX_CAPACITY];
} StaticHashMap;

2. 初始化哈希映射 #

初始化时要把所有位置的状态设为EMPTY，确保一开始是干净的：

void static_hash_map_init(StaticHashMap* map) {
    if (!map) return; // 防止传入空指针
    for (int i = 0; i < MAX_CAPACITY; i++) {
        map->states[i] = EMPTY;
    }
}

3. 哈希函数（核心中的核心） #

哈希函数负责把Key转换成数组的索引，对于int类型，简单的取模就够用了：

static int hash_function(Key key) {
    // 用abs处理负Key，保证结果在0到MAX_CAPACITY-1之间
    return abs(key) % MAX_CAPACITY;
}

要是你以后换其他类型的Key（比如字符串），只要换对应的哈希函数就行——比如字符串可以用经典的djb2哈希算法。

4. 插入键值对（处理哈希冲突） #

静态数组避免不了哈希冲突（两个不同的Key算出同一个索引），这里用线性探测解决：如果目标位置被占了，就依次往后找下一个空闲/已删除的位置。代码如下：

int static_hash_map_insert(StaticHashMap* map, Key key, Value value) {
    if (!map) return -1; // 非法输入

    int index = hash_function(key);
    int start_index = index;

    // 循环探测，直到找到可用位置或绕回起点（说明满了）
    do {
        if (map->states[index] == EMPTY || map->states[index] == DELETED) {
            // 找到可用位置，存入键值对
            map->keys[index] = key;
            map->values[index] = value;
            map->states[index] = OCCUPIED;
            return 0; // 插入成功
        } else if (map->keys[index] == key) {
            // 键已经存在，直接更新对应的值
            map->values[index] = value;
            return 0;
        }

        // 往后挪一个位置，超出数组就绕回开头
        index = (index + 1) % MAX_CAPACITY;
    } while (index != start_index);

    return -2; // 整个数组都满了，插入失败
}

5. 查找对应的值 #

查找逻辑和插入对应，同样用线性探测找目标Key：

int static_hash_map_get(StaticHashMap* map, Key key, Value* out_value) {
    if (!map || !out_value) return -1;

    int index = hash_function(key);
    int start_index = index;

    do {
        if (map->states[index] == EMPTY) {
            return -2; // 走到空闲位置，说明Key不存在
        } else if (map->states[index] == OCCUPIED && map->keys[index] == key) {
            *out_value = map->values[index];
            return 0; // 找到目标值
        }

        index = (index + 1) % MAX_CAPACITY;
    } while (index != start_index);

    return -2; // 遍历完整个数组都没找到
}

6. 删除键值对 #

注意：不能直接把状态设为EMPTY，否则会打断线性探测的链（后面的元素可能找不到），所以我们设为DELETED标记这个位置可以复用：

int static_hash_map_delete(StaticHashMap* map, Key key) {
    if (!map) return -1;

    int index = hash_function(key);
    int start_index = index;

    do {
        if (map->states[index] == EMPTY) {
            return -2; // Key不存在
        } else if (map->states[index] == OCCUPIED && map->keys[index] == key) {
            map->states[index] = DELETED;
            return 0; // 删除成功
        }

        index = (index + 1) % MAX_CAPACITY;
    } while (index != start_index);

    return -2; // 没找到要删除的Key
}

如果要支持其他类型的Key或Value，C语言可以用宏来封装模板化的结构，或者用void指针（注意类型安全）。这里给个宏封装的例子：

// 先把EntryState枚举定义好（前面已经有了）
typedef enum { EMPTY, OCCUPIED, DELETED } EntryState;

// 宏定义：生成指定类型的静态哈希映射结构体和初始化函数
#define DEFINE_STATIC_HASH_MAP(MapName, KeyType, ValueType, Capacity) \
typedef struct { \
    KeyType keys[Capacity]; \
    ValueType values[Capacity]; \
    EntryState states[Capacity]; \
} MapName; \
\
void MapName##_init(MapName* map) { \
    if (!map) return; \
    for (int i = 0; i < Capacity; i++) { \
        map->states[i] = EMPTY; \
    } \
}

比如要生成一个字符串Key、int Value的哈希表：

// 生成名为StringIntHashMap的结构体和初始化函数
DEFINE_STATIC_HASH_MAP(StringIntHashMap, char*, int, 100)

这时候需要单独实现字符串的哈希函数，比如：

static int string_hash(const char* str) {
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c; /* 等价于 hash * 33 + c */
    }
    return hash % 100; // 对应Capacity=100
}

插入、查找函数可以参照前面的int版本，把哈希函数换成这个字符串哈希函数就行。

如果不想纠结C语言的语法，用伪代码看逻辑更清楚：

# 定义常量
MAX_CAPACITY = 100
EMPTY = 0
OCCUPIED = 1
DELETED = 2

# 初始化静态哈希映射，返回三个平行数组
def init_static_hash_map():
    keys = [None] * MAX_CAPACITY
    values = [None] * MAX_CAPACITY
    states = [EMPTY] * MAX_CAPACITY
    return (keys, values, states)

# 针对int Key的哈希函数
def hash_key(key):
    return abs(key) % MAX_CAPACITY

# 插入键值对，成功返回True，失败返回False（数组满了）
def insert(map, key, value):
    keys, values, states = map
    index = hash_key(key)
    start_index = index
    
    while True:
        if states[index] == EMPTY or states[index] == DELETED:
            keys[index] = key
            values[index] = value
            states[index] = OCCUPIED
            return True
        elif keys[index] == key:
            values[index] = value  # 已有Key，更新值
            return True
        
        index = (index + 1) % MAX_CAPACITY
        if index == start_index:
            return False  # 数组已满

# 查找值，找到返回对应值，没找到返回None
def get(map, key):
    keys, values, states = map
    index = hash_key(key)
    start_index = index
    
    while True:
        if states[index] == EMPTY:
            return None
        elif states[index] == OCCUPIED and keys[index] == key:
            return values[index]
        
        index = (index + 1) % MAX_CAPACITY
        if index == start_index:
            return None

# 删除键值对，成功返回True，失败返回False
def delete(map, key):
    keys, values, states = map
    index = hash_key(key)
    start_index = index
    
    while True:
        if states[index] == EMPTY:
            return False
        elif states[index] == OCCUPIED and keys[index] == key:
            states[index] = DELETED
            return True
        
        index = (index + 1) % MAX_CAPACITY
        if index == start_index:
            return False

• 哈希函数选择：如果你的int Key分布不均匀（比如大多是偶数），可以试试(key * 31) % MAX_CAPACITY这样的哈希函数，减少冲突率；字符串Key推荐用djb2或者MurmurHash这类成熟的算法。
• 冲突处理：线性探测简单但容易出现“聚集”（连续一片被占用），可以换成二次探测或者双哈希来缓解，但实现会复杂一点。
• 容量预估：静态数组容量固定，一定要提前算好最大需要存多少条目，避免插入失败；如果需要动态扩容，那就要换成动态数组了，但你要的是静态方案，所以这一点要注意。
• 复杂Value类型：如果Value是结构体，C语言里插入时要注意深拷贝（如果结构体里有指针的话），或者直接存指针（但要管理内存）。

内容的提问来源于stack exchange，提问作者Albert