数据结构：哈希表原理与 C 语言实现

数据结构：哈希表原理与 C 语言实现 | 极客日志

typedef struct HashNode { KeyType key; DataType value; struct HashNode *next; } HashNode;
typedef struct { HashNode **table; // 指针数组 int size; // 表长 int count; // 元素个数 } HashTable;

typedef int DATATYPE;
typedef struct {
    DATATYPE* head; // 数据数组
    int tlen;       // 表长度
    int count;      // 元素个数
    int* status;    // 状态数组：0-空，1-占用，2-删除
} HS_TABLE;

HS_TABLE* CreateHsTable(int len) {
    HS_TABLE* hs = (HS_TABLE*)malloc(sizeof(HS_TABLE));
    if (hs == NULL) return NULL;
    hs->head = (DATATYPE*)malloc(sizeof(DATATYPE) * len);
    hs->status = (int*)malloc(sizeof(int) * len);
    hs->tlen = len;
    hs->count = 0;
    if (hs->head == NULL || hs->status == NULL) {
        free(hs->head);
        free(hs->status);
        free(hs);
        return NULL;
    }
    // 初始化状态为 0（空）
    for (int i = 0; i < len; i++) {
        hs->status[i] = 0;
    }
    return hs;
}

int HashFunc(DATATYPE key, int size) {
    return key % size;
}

int InsertHsTable(HS_TABLE* hs, DATATYPE data) {
    if (hs == NULL || hs->count >= hs->tlen) {
        return -1; // 表满或无效
    }
    int index = HashFunc(data, hs->tlen);
    int i = 0;
    // 线性探测
    while (i < hs->tlen) {
        int pos = (index + i) % hs->tlen;
        // 找到空位置或删除位置
        if (hs->status[pos] == 0 || hs->status[pos] == 2) {
            hs->head[pos] = data;
            hs->status[pos] = 1; // 标记为占用
            hs->count++;
            return pos; // 返回插入位置
        }
        // 如果已存在相同元素
        else if (hs->status[pos] == 1 && hs->head[pos] == data) {
            return -2; // 元素已存在
        }
        i++;
    }
    return -1; // 未找到插入位置
}

int SearchHsTable(HS_TABLE* hs, DATATYPE data) {
    if (hs == NULL) return -1;
    int index = HashFunc(data, hs->tlen);
    int i = 0;
    while (i < hs->tlen) {
        int pos = (index + i) % hs->tlen;
        // 遇到空位置，说明元素不存在
        if (hs->status[pos] == 0) {
            return -1;
        }
        // 找到元素
        if (hs->status[pos] == 1 && hs->head[pos] == data) {
            return pos;
        }
        i++;
    }
    return -1; // 未找到
}

int DeleteHsTable(HS_TABLE* hs, DATATYPE data) {
    if (hs == NULL) return -1;
    int pos = SearchHsTable(hs, data);
    if (pos == -1) {
        return -1; // 元素不存在
    }
    // 标记为删除状态（惰性删除）
    hs->status[pos] = 2;
    hs->count--;
    return pos;
}

int DestroyHsTable(HS_TABLE* hs) {
    if (hs == NULL) return -1;
    free(hs->head);
    free(hs->status);
    free(hs);
    return 0;
}

void DisplayHsTable(HS_TABLE* hs) {
    if (hs == NULL) return;
    printf("哈希表（长度=%d，元素数=%d）:\n", hs->tlen, hs->count);
    printf("索引\t状态\t数据\n");
    printf("-------------------\n");
    for (int i = 0; i < hs->tlen; i++) {
        printf("%d\t", i);
        switch (hs->status[i]) {
            case 0: printf("空\t-\n"); break;
            case 1: printf("占用\t%d\n", hs->head[i]); break;
            case 2: printf("删除\t-\n"); break;
        }
    }
}

冲突解决方法	ASL 成功（平均）	ASL 失败（平均）
线性探测法	(1 + 1/(1-α)²)/2	(1 + 1/(1-α))/2
二次探测法	-ln(1-α)/α	1/(1-α)
链地址法	1 + α/2	α + e⁻α

#include <stdio.h>
#include <stdlib.h>
#define EMPTY 0
#define OCCUPIED 1
#define DELETED 2

// 哈希表 ADT 实现
typedef int DATATYPE;
typedef struct {
    DATATYPE* data; // 数据数组
    int* status;    // 状态数组
    int size;       // 表大小
    int count;      // 元素个数
} HashTable;

// 创建哈希表
HashTable* CreateHashTable(int size) {
    HashTable* ht = (HashTable*)malloc(sizeof(HashTable));
    if (!ht) return NULL;
    ht->data = (DATATYPE*)malloc(sizeof(DATATYPE) * size);
    ht->status = (int*)calloc(size, sizeof(int)); // 初始化为 0
    ht->size = size;
    ht->count = 0;
    if (!ht->data || !ht->status) {
        free(ht->data);
        free(ht->status);
        free(ht);
        return NULL;
    }
    return ht;
}

// 哈希函数（除留余数法）
int HashFunction(DATATYPE key, int size) {
    return abs(key) % size; // 取绝对值避免负数
}

// 插入元素（线性探测）
int HashInsert(HashTable* ht, DATATYPE key) {
    if (!ht || ht->count >= ht->size) return -1;
    int index = HashFunction(key, ht->size);
    int i = 0;
    while (i < ht->size) {
        int pos = (index + i) % ht->size;
        // 空位置或删除位置
        if (ht->status[pos] == EMPTY || ht->status[pos] == DELETED) {
            ht->data[pos] = key;
            ht->status[pos] = OCCUPIED;
            ht->count++;
            return pos;
        }
        // 已存在相同元素
        else if (ht->status[pos] == OCCUPIED && ht->data[pos] == key) {
            return -2; // 元素已存在
        }
        i++;
    }
    return -1; // 表满
}

// 查找元素
int HashSearch(HashTable* ht, DATATYPE key) {
    if (!ht) return -1;
    int index = HashFunction(key, ht->size);
    int i = 0;
    while (i < ht->size) {
        int pos = (index + i) % ht->size;
        // 遇到空位置，停止搜索
        if (ht->status[pos] == EMPTY) {
            return -1;
        }
        // 找到元素
        if (ht->status[pos] == OCCUPIED && ht->data[pos] == key) {
            return pos;
        }
        i++;
    }
    return -1; // 未找到
}

// 删除元素
int HashDelete(HashTable* ht, DATATYPE key) {
    if (!ht) return -1;
    int pos = HashSearch(ht, key);
    if (pos == -1) return -1; // 元素不存在
    ht->status[pos] = DELETED; // 惰性删除
    ht->count--;
    return pos;
}

// 销毁哈希表
void DestroyHashTable(HashTable* ht) {
    if (!ht) return;
    free(ht->data);
    free(ht->status);
    free(ht);
}

// 显示哈希表
void DisplayHashTable(HashTable* ht) {
    if (!ht) return;
    printf("\n哈希表状态（大小=%d，元素=%d）:\n", ht->size, ht->count);
    printf("索引\t状态\t数据\n");
    printf("--------------------\n");
    for (int i = 0; i < ht->size; i++) {
        printf("%d\t", i);
        switch (ht->status[i]) {
            case EMPTY: printf("空\t-\n"); break;
            case OCCUPIED: printf("占用\t%d\n", ht->data[i]); break;
            case DELETED: printf("删除\t-\n"); break;
        }
    }
}

// 测试函数
int main() {
    // 创建哈希表
    HashTable* ht = CreateHashTable(10);
    if (!ht) {
        printf("创建哈希表失败！\n");
        return 1;
    }
    printf("=== 哈希表测试 ===\n");
    
    // 插入测试
    int keys[] = {19, 29, 39, 49, 59, 69, 79, 89, 99, 109};
    for (int i = 0; i < 10; i++) {
        int result = HashInsert(ht, keys[i]);
        if (result >= 0) {
            printf("插入 %d 成功，位置：%d\n", keys[i], result);
        } else if (result == -2) {
            printf("插入 %d 失败，元素已存在\n", keys[i]);
        } else {
            printf("插入 %d 失败，表满\n", keys[i]);
        }
    }
    DisplayHashTable(ht);
    
    // 查找测试
    printf("\n查找测试:\n");
    int search_keys[] = {39, 50, 89};
    for (int i = 0; i < 3; i++) {
        int pos = HashSearch(ht, search_keys[i]);
        if (pos >= 0) {
            printf("查找 %d 成功，位置：%d\n", search_keys[i], pos);
        } else {
            printf("查找 %d 失败，元素不存在\n", search_keys[i]);
        }
    }
    
    // 删除测试
    printf("\n删除测试:\n");
    int delete_key = 49;
    int del_pos = HashDelete(ht, delete_key);
    if (del_pos >= 0) {
        printf("删除 %d 成功，位置：%d\n", delete_key, del_pos);
    } else {
        printf("删除 %d 失败\n", delete_key);
    }
    DisplayHashTable(ht);
    
    // 再次插入测试删除位置
    printf("\n在删除位置插入新元素:\n");
    int new_key = 119;
    int ins_pos = HashInsert(ht, new_key);
    if (ins_pos >= 0) {
        printf("插入 %d 成功，位置：%d\n", new_key, ins_pos);
    }
    DisplayHashTable(ht);
    
    // 销毁哈希表
    DestroyHashTable(ht);
    return 0;
}

特性	哈希表
查找速度	O(1) 平均，O(n) 最坏
插入速度	O(1) 平均
删除速度	O(1) 平均
空间复杂度	O(n)
是否有序	无序
最佳适用	快速查找，无需排序

数据结构：哈希表原理与 C 语言实现

一、哈希表（Hash Table）

1. 哈希表概念

1.1 定义

1.2 核心思想

1.3 特点

2. 哈希函数设计

2.1 设计要点

2.2 常见哈希函数

2.2.1 直接定址法

2.2.2 除留余数法（最常用）

2.2.3 平方取中法

2.2.4 折叠法

2.2.5 数字分析法

3. 哈希冲突

3.1 冲突定义

3.2 冲突解决方法

3.2.1 开放定址法

3.2.2 链地址法

3.2.3 公共溢出区法

4. 哈希表 ADT 实现

4.1 数据结构定义

4.2 基本操作实现

4.2.1 创建哈希表

4.2.2 哈希函数（除留余数法）

4.2.3 插入元素（线性探测）

4.2.4 查找元素

4.2.5 删除元素

4.2.6 销毁哈希表

4.2.7 显示哈希表

5. 哈希表性能分析

5.1 装载因子

5.2 平均查找长度（ASL）

5.2.1 查找成功

5.2.2 查找失败

5.3 不同方法的 ASL

6. 完整示例代码

7. 应用场景

7.1 适合使用哈希表的场景

7.2 不适合使用哈希表的场景

8. 总结

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具