数据结构18-哈希表

哈希表（Hash Table）是一种非常高效的数据结构，主要用于快速查找、插入和删除操作。它通过哈希函数将键映射到表中的特定位置，从而加快数据访问速度。下面是一个详细且系统的哈希表实现指南，包括基本概念、哈希函数、冲突解决方法以及在C语言中的具体实现。

1. 基本概念

• 哈希函数 (Hash Function): 将输入（键）映射到哈希表中一个索引位置的函数。
• 哈希表 (Hash Table): 一个数组，用于存储键值对。
• 冲突 (Collision): 不同的键通过哈希函数映射到同一个索引位置。
• 装载因子 (Load Factor): 哈希表中元素数量与哈希表大小的比值，用于衡量哈希表的装满程度。

2. 哈希函数

哈希函数的选择对哈希表的性能有很大影响。一个好的哈希函数应该均匀地分布键，减少冲突。常见的哈希函数有：

unsigned int hash_function(const char *key) {
    unsigned int hash = 0;
    while (*key) {
        hash = (hash << 5) + *key++;
    }
    return hash;
}

3. 冲突解决方法

常见的冲突解决方法有两种：

• 链地址法 (Chaining): 每个哈希表的索引位置存储一个链表，当冲突发生时，将新元素添加到链表中。
• 开放地址法 (Open Addressing): 当冲突发生时，寻找下一个空闲位置存储元素。

4. 在C语言中的具体实现

4.1 定义结构

首先，定义哈希表的结构，包括链表节点和哈希表本身。

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

#define TABLE_SIZE 100

typedef struct HashNode {
    char *key;
    int value;
    struct HashNode *next;
} HashNode;

typedef struct HashTable {
    HashNode **table;
} HashTable;

4.2 初始化哈希表

HashTable* create_table() {
    HashTable *hashTable = (HashTable*) malloc(sizeof(HashTable));
    hashTable->table = (HashNode**) malloc(TABLE_SIZE * sizeof(HashNode*));
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable->table[i] = NULL;
    }
    return hashTable;
}

4.3 插入元素

void insert(HashTable *hashTable, const char *key, int value) {
    unsigned int index = hash_function(key) % TABLE_SIZE;
    HashNode *newNode = (HashNode*) malloc(sizeof(HashNode));
    newNode->key = strdup(key);
    newNode->value = value;
    newNode->next = hashTable->table[index];
    hashTable->table[index] = newNode;
}

4.4 查找元素

int search(HashTable *hashTable, const char *key) {
    unsigned int index = hash_function(key) % TABLE_SIZE;
    HashNode *node = hashTable->table[index];
    while (node != NULL) {
        if (strcmp(node->key, key) == 0) {
            return node->value;
        }
        node = node->next;
    }
    return -1; // Not found
}

4.5 删除元素

void delete(HashTable *hashTable, const char *key) {
    unsigned int index = hash_function(key) % TABLE_SIZE;
    HashNode *node = hashTable->table[index];
    HashNode *prev = NULL;
    while (node != NULL && strcmp(node->key, key) != 0) {
        prev = node;
        node = node->next;
    }
    if (node == NULL) {
        return; // Key not found
    }
    if (prev == NULL) {
        hashTable->table[index] = node->next;
    } else {
        prev->next = node->next;
    }
    free(node->key);
    free(node);
}

4.6 释放哈希表

void free_table(HashTable *hashTable) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        HashNode *node = hashTable->table[i];
        while (node != NULL) {
            HashNode *temp = node;
            node = node->next;
            free(temp->key);
            free(temp);
        }
    }
    free(hashTable->table);
    free(hashTable);
}

5. 示例代码

int main() {
    HashTable *hashTable = create_table();

    insert(hashTable, "key1", 1);
    insert(hashTable, "key2", 2);
    insert(hashTable, "key3", 3);

    printf("Value for 'key1': %d\n", search(hashTable, "key1"));
    printf("Value for 'key2': %d\n", search(hashTable, "key2"));
    printf("Value for 'key3': %d\n", search(hashTable, "key3"));

    delete(hashTable, "key2");
    printf("Value for 'key2' after deletion: %d\n", search(hashTable, "key2"));

    free_table(hashTable);

    return 0;
}

闵帆老师写的

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define TABLE_SIZE 100 // 哈希表的大小
#define KEY_SIZE 50  // 键的最大长度
#define VALUE_SIZE 100 // 值的最大长度
 
typedef struct KeyValuePair {
    char key[KEY_SIZE];
    char value[VALUE_SIZE];
    struct KeyValuePair *next; // 指向下一个节点，处理冲突
} KeyValuePair;
 
typedef struct {
    KeyValuePair *table[TABLE_SIZE]; // 哈希表数组
} HashTable;
 
// 初始化哈希表
void initHashTable(HashTable *hashTable) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable->table[i] = NULL;
    }
}

运行结果

Collision, move forward for key 57.
Collision, move forward for key 95.
Collision, move forward for key 95.
Search result of 95 is: r
Search result of 38 is: l
Search result of 57 is: w
Search result of 4 is: x
Press any key to continue