6、开放地址法实现（上）：线性探测原理、插入操作实现、查找操作实现

好，咱们今天来聊聊开放地址法。这是哈希表解决冲突的另一种经典思路。跟链地址法那种「挂链表」的方式不同，开放地址法的核心思想是——既然这个位置被人占了，那我就往后找个空位住下来。

说白了，整个哈希表就是一个大数组，每个元素只能占一个坑。冲突了？没关系，按某种规则继续找下一个坑，直到找到空的为止。我刚开始学的时候觉得这方法挺「倔」的，明明冲突了还要硬塞进去。但用久了你会发现，在某些场景下它比链地址法更省内存，缓存也更友好。

6.1 线性探测原理

线性探测是最简单的开放地址法。它的探测公式长这样：

index = (hash(key) + i) % table_size    // i = 0, 1, 2, 3, ...

什么意思呢？就是先算一个哈希值，如果那个位置被占了，就往后挪一个位置；再被占，再挪……直到找到空位或者遍历完整个表。

我画了一张图，帮你理解这个过程：

你看，key=25 本来应该去索引5的位置，但那里已经被占了。于是它往后找索引6，发现是空的，就住进去了。就这么简单。

6.2 插入操作实现

好，咱们直接上代码。我习惯用结构体来封装哈希表，这样管理起来清晰。

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

#define TABLE_SIZE 10
#define EMPTY -1      // 表示空位
#define DELETED -2    // 表示已删除（后面会用到）

typedef struct {
    int *data;        // 存储键值
    int size;         // 表大小
    int count;        // 当前元素个数
} HashTable;

// 初始化哈希表
HashTable* create_table() {
    HashTable *ht = (HashTable*)malloc(sizeof(HashTable));
    ht->data = (int*)malloc(sizeof(int) * TABLE_SIZE);
    ht->size = TABLE_SIZE;
    ht->count = 0;
    
    for (int i = 0; i < ht->size; i++) {
        ht->data[i] = EMPTY;  // 全部标记为空
    }
    return ht;
}

// 哈希函数（简单取模）
int hash(int key) {
    return key % TABLE_SIZE;
}

// 线性探测插入
int insert(HashTable *ht, int key) {
    int index = hash(key);
    int start = index;
    
    // 线性探测：找到空位或已删除的位置
    while (ht->data[index] != EMPTY && ht->data[index] != DELETED) {
        // 如果键已存在，不插入（避免重复）
        if (ht->data[index] == key) {
            printf("键 %d 已存在，插入失败\n", key);
            return 0;
        }
        index = (index + 1) % ht->size;
        
        // 如果绕了一圈回到起点，说明表满了
        if (index == start) {
            printf("哈希表已满，插入失败\n");
            return 0;
        }
    }
    
    // 找到空位，插入
    ht->data[index] = key;
    ht->count++;
    printf("键 %d 插入到位置 %d\n", key, index);
    return 1;
}

这段代码有几个地方我想特别说一下：

• EMPTY 和 DELETED 标记：我用 -1 表示空位，-2 表示已删除。为什么要区分？后面讲删除操作时你就明白了。
• 绕圈检测：如果 index 绕了一圈回到起点，说明表满了。这个判断很重要，不然会死循环。
• 重复键检查：插入前先看看这个键是不是已经存在。我遇到过有人忘了这一步，结果哈希表里出现重复数据，查了半天 bug。

6.3 查找操作实现

查找的逻辑跟插入很像。也是先算哈希值，然后线性探测，直到找到目标键或者遇到空位。

// 线性探测查找
int search(HashTable *ht, int key) {
    int index = hash(key);
    int start = index;
    
    // 线性探测
    while (ht->data[index] != EMPTY) {
        if (ht->data[index] == key) {
            printf("找到键 %d，位于位置 %d\n", key, index);
            return index;  // 返回位置
        }
        index = (index + 1) % ht->size;
        
        // 绕了一圈，没找到
        if (index == start) {
            break;
        }
    }
    
    printf("键 %d 未找到\n", key);
    return -1;  // 没找到
}

这里有个细节：查找时遇到 DELETED 标记不能停，要继续往后找。因为 DELETED 表示这个位置曾经有数据，后来被删了，但后面的数据可能是绕过它插入的。如果遇到 DELETED 就停，可能会漏掉目标。

举个例子：

假设 hash(12) = 2，但索引2被占了，所以它绕到了索引3？不对，你看表里索引2是空的？哦，我写错了，重新来：

假设 hash(10) = 0，hash(12) = 2。但索引2被占了？不对，索引2是12本身。嗯，这个例子不太好，我换个说法。

假设 hash(10)=0，hash(11)=1，hash(12)=2。但索引1被删了，变成 DELETED。现在查找 key=12：

• 先算 hash(12)=2，直接命中，返回。
• 如果查找 key=11：hash(11)=1，发现是 DELETED，不能停！继续往后找索引2，发现是12，不是11。再找索引3，是 EMPTY，停。没找到。

你看，如果遇到 DELETED 就停，那 key=11 就会误判为「存在」，但实际上它已经被删了。所以查找时一定要越过 DELETED。

6.4 完整测试代码

最后，咱们跑个完整的例子看看效果：

int main() {
    HashTable *ht = create_table();
    
    insert(ht, 10);  // hash=0，插入位置0
    insert(ht, 20);  // hash=0，冲突！探测到位置1
    insert(ht, 30);  // hash=0，冲突！探测到位置2
    insert(ht, 11);  // hash=1，冲突！探测到位置3
    
    search(ht, 20);  // 应该找到，位置1
    search(ht, 99);  // 没找到
    
    return 0;
}

输出结果：

键 10 插入到位置 0
键 20 插入到位置 1
键 30 插入到位置 2
键 11 插入到位置 3
找到键 20，位于位置 1
键 99 未找到

你看，10、20、30 的哈希值都是0，但通过线性探测，它们依次占到了0、1、2三个位置。这就是线性探测的「聚集」效应——冲突的键会挤在一起。

我个人建议，在实际项目中如果要用开放地址法，装载因子最好控制在0.5到0.7之间。超过0.7就该扩容了，不然性能会很难看。嗯，关于扩容和删除操作，咱们下节课再聊。

公众号:蓝海资料掘金营，微信deep3321