17. C 语言中链表的哈希表应用详解

# 1. 哈希表基础概念

## 1.1 哈希表的定义
哈希表（Hash Table）是根据关键码值（Key value）而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。哈希表的实现一般是通过数组来实现的，这个数组的每个元素就是一个哈希表的“桶”，可以存放多个数据。

## 1.2 哈希函数的作用
哈希函数是哈希表实现的核心。它能将不定长的输入数据转换为固定长度的输出，其作用是尽可能均匀地将数据分散到不同的桶中，减少哈希碰撞的发生。

## 1.3 哈希碰撞及解决方法
哈希碰撞指不同的关键字经过哈希函数处理后映射到了同一个桶中。解决哈希碰撞的方法一般有开放定址法、链地址法等，其中链地址法是常用的方法之一，即使用链表来解决碰撞问题，将哈希表中的每个桶设置为一个链表结构，将同一个桶中哈希值相同的元素存储在同一个链表中。

| 解决哈希碰撞的方法 | 优点 | 缺点 |
| --------------------- | ------- | ------- |
| 开放定址法 | 内存利用率高，简单易实现 | 当哈希表数据量大时，性能下降明显 |
| 链地址法 | 操作简单，适用性广泛 | 内存占用较大，查找速度取决于链表的长度 |

综上所述，哈希表是一种十分重要且高效的数据结构，在实际应用中需要选择合适的哈希函数和解决碰撞的方法来提高效率和性能。

# 2. 链表在C语言中的实现与应用

本章将深入探讨链表在C语言中的实现与应用，包括链表的基本概念、创建与节点插入、遍历和删除操作等内容。

### 2.1 C 语言中链表的基本概念
在C语言中，链表是一种常见的数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针。

### 2.2 链表的创建与节点插入
下面是C语言中创建链表并插入节点的示例代码：

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

// 定义链表节点结构
struct Node {
    int data;
    struct Node *next;
};

// 创建新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 在链表头部插入节点
void insertNode(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

int main() {
    struct Node* head = NULL;

    // 插入节点：5 -> 10 -> 15
    insertNode(&head, 15);
    insertNode(&head, 10);
    insertNode(&head, 5);

    // 遍历链表
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");

    return 0;
}

### 2.3 链表的遍历和删除操作
链表的遍历和删除操作是常见的操作，遍历通过指针不断向下移动，删除操作可以通过调整指针完成节点的删除。以下是遍历和删除节点的示例代码。

// 遍历链表
void traverseList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// 删除节点
void deleteNode(struct Node** head, int key) {
    struct Node* temp = *head, *prev;

    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return;

    prev->next = temp->next;
    free(temp);
}

以上是链表在C语言中的基本实现与应用，通过C语言中的指针操作，可以实现链表的各种功能。

# 3. 哈希表和链表结合的优势

### 3.1 哈希表和链表相结合的原理
哈希表和链表的结合可以充分发挥二者各自的优势，哈希表通过哈希函数将数据映射到索引位置，解决了直接寻址表可能出现的空间浪费问题；链表则解决了哈希冲突时如何处理碰撞的问题。将哈希表和链表结合使用，可以提高数据的查找效率和解决哈希碰撞的问题。

### 3.2 如何在C语言中实现哈希表和链表的结合

在C语言中实现哈希表和链表的结合，可以首先设计一个哈希表的结构体，其中包含一个链表的头指针数组，用于存储哈希冲突时的链表。然后设计哈希函数将数据映射到对应的索引位置，当哈希冲突发生时，将数据插入到对应索引位置的链表中。以下是一个简单的示例代码：

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

#define TABLE_SIZE 10

// 链表节点
struct Node {
    int data;
    struct Node* next;
};

// 哈希表结构体
struct HashTable {
    struct Node* head[TABLE_SIZE];
};

// 初始化哈希表
void initHashTable(struct HashTable* ht) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        ht->head[i] = NULL;
    }
}

// 哈希函数
int hashFunction(int key) {
    return key % TABLE_SIZE;
}

// 插入数据到哈希表
void insert(struct HashTable* ht, int key) {
    int index = hashFunction(key);
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = key;
    newNode->next = NULL;
    if (ht->head[index] == NULL) {
        ht->head[index] = newNode;
    } else {
        struct Node* c