Pointer如何实现哈希表

在计算机科学中，哈希表（Hash Table）是一种通过哈希函数将键映射到值的数据结构。它提供了快速的插入、删除和查找操作。指针可以在实现哈希表时发挥重要作用，特别是在处理动态内存分配和链式哈希（Separate Chaining）时。

以下是使用指针实现哈希表的基本步骤：

1. 定义哈希表的结构：

   • 哈希表通常是一个数组，数组的每个元素是一个指向链表头节点的指针。这个链表用于处理哈希冲突（即多个键映射到同一个索引）。

2. 定义链表节点的结构：

   • 每个链表节点包含一个键值对和一个指向下一个节点的指针。

3. 初始化哈希表：

   • 分配内存给哈希表的数组，并将每个元素初始化为NULL。

4. 哈希函数：

   • 实现一个哈希函数，将键转换为数组索引。哈希函数应该尽量均匀地分布键，以减少冲突。

5. 插入操作：

   • 使用哈希函数计算键的索引。
   • 遍历对应索引的链表，检查是否已经存在相同的键。
   • 如果存在，更新值；如果不存在，在链表头部插入新的节点。

6. 查找操作：

   • 使用哈希函数计算键的索引。
   • 遍历对应索引的链表，查找匹配的键并返回其值。

7. 删除操作：

   • 使用哈希函数计算键的索引。
   • 遍历对应索引的链表，找到匹配的键并删除对应的节点。

以下是一个简单的C语言示例，展示了如何使用指针实现一个基本的哈希表：

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

#define TABLE_SIZE 10

// 定义链表节点结构
typedef struct Node {
    char *key;
    int value;
    struct Node *next;
} Node;

// 定义哈希表结构
typedef struct HashTable {
    Node **table;
} HashTable;

// 哈希函数
unsigned int hash(const char *key) {
    unsigned int hash = 0;
    while (*key) {
        hash = (hash * 31) + *key++;
    }
    return hash % TABLE_SIZE;
}

// 初始化哈希表
HashTable *create_table() {
    HashTable *ht = (HashTable *)malloc(sizeof(HashTable));
    ht->table = (Node **)malloc(sizeof(Node *) * TABLE_SIZE);
    for (int i = 0; i < TABLE_SIZE; i++) {
        ht->table[i] = NULL;
    }
    return ht;
}

// 插入操作
void insert(HashTable *ht, const char *key, int value) {
    unsigned int index = hash(key);
    Node *new_node = (Node *)malloc(sizeof(Node));
    new_node->key = strdup(key);
    new_node->value = value;
    new_node->next = ht->table[index];
    ht->table[index] = new_node;
}

// 查找操作
int lookup(HashTable *ht, const char *key) {
    unsigned int index = hash(key);
    Node *current = ht->table[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value;
        }
        current = current->next;
    }
    return -1; // 未找到
}

// 删除操作
void delete(HashTable *ht, const char *key) {
    unsigned int index = hash(key);
    Node *current = ht->table[index];
    Node *prev = NULL;
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            if (prev == NULL) {
                ht->table[index] = current->next;
            } else {
                prev->next = current->next;
            }
            free(current->key);
            free(current);
            return;
        }
        prev = current;
        current = current->next;
    }
}

// 释放哈希表内存
void free_table(HashTable *ht) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        Node *current = ht->table[i];
        while (current != NULL) {
            Node *temp = current;
            current = current->next;
            free(temp->key);
            free(temp);
        }
    }
    free(ht->table);
    free(ht);
}

int main() {
    HashTable *ht = create_table();
    insert(ht, "apple", 10);
    insert(ht, "banana", 20);
    printf("apple: %d\n", lookup(ht, "apple"));
    printf("banana: %d\n", lookup(ht, "banana"));
    delete(ht, "apple");
    printf("apple after delete: %d\n", lookup(ht, "apple"));
    free_table(ht);
    return 0;
}

这个示例展示了如何使用指针和链表来实现一个简单的哈希表。实际应用中可能需要更多的功能和优化，例如动态调整哈希表大小、更好的哈希函数等。