2015年3月

在 C 语言中，构建哈希表（Hash Table）是一种常见的实现高效查找、插入和删除操作的方法。哈希表的核心思想是通过哈希函数将键（key）映射到一个索引，然后将值（value）存储在该索引对应的位置。

以下是构建哈希表的详细步骤和示例代码：

1. 哈希表的基本结构

哈希表通常由以下部分组成：

  1. 哈希函数：将键映射到索引。
  2. 数组：存储键值对。
  3. 冲突解决机制：处理哈希冲突（如链地址法或开放地址法）。

2. 哈希函数

哈希函数的设计直接影响哈希表的性能。一个好的哈希函数应该：

  • 均匀分布键。
  • 计算速度快。

以下是一个简单的哈希函数示例（假设键是字符串）：

unsigned int hash(const char *key, int tableSize) {
    unsigned int hashValue = 0;
    while (*key) {
        hashValue = (hashValue << 5) + *key++; // 使用移位和加法
    }
    return hashValue % tableSize; // 取模确保索引在数组范围内
}

3. 链地址法解决冲突

链地址法是一种常见的冲突解决机制。它的基本思想是将哈希表中每个索引位置存储为一个链表，所有哈希到同一索引的键值对都存储在该链表中。

数据结构定义：

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

#define TABLE_SIZE 100 // 哈希表大小

// 键值对结构
typedef struct Entry {
    char *key;
    int value;
    struct Entry *next; // 指向下一个键值对
} Entry;

// 哈希表结构
typedef struct HashTable {
    Entry *table[TABLE_SIZE]; // 存储链表的数组
} HashTable;

4. 哈希表操作

(1) 初始化哈希表

HashTable *createHashTable() {
    HashTable *ht = (HashTable *)malloc(sizeof(HashTable));
    for (int i = 0; i < TABLE_SIZE; i++) {
        ht->table[i] = NULL; // 初始化每个链表为空
    }
    return ht;
}

(2) 插入键值对

void insert(HashTable *ht, const char *key, int value) {
    unsigned int index = hash(key, TABLE_SIZE);

    // 创建新节点
    Entry *newEntry = (Entry *)malloc(sizeof(Entry));
    newEntry->key = strdup(key); // 复制键
    newEntry->value = value;
    newEntry->next = NULL;

    // 插入到链表头部
    if (ht->table[index] == NULL) {
        ht->table[index] = newEntry;
    } else {
        newEntry->next = ht->table[index];
        ht->table[index] = newEntry;
    }
}

(3) 查找键值对

int search(HashTable *ht, const char *key) {
    unsigned int index = hash(key, TABLE_SIZE);
    Entry *current = ht->table[index];

    // 遍历链表
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value; // 找到键，返回值
        }
        current = current->next;
    }

    return -1; // 未找到键
}

(4) 删除键值对

void delete(HashTable *ht, const char *key) {
    unsigned int index = hash(key, TABLE_SIZE);
    Entry *current = ht->table[index];
    Entry *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;
    }
}

(5) 释放哈希表

void freeHashTable(HashTable *ht) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        Entry *current = ht->table[i];
        while (current != NULL) {
            Entry *temp = current;
            current = current->next;
            free(temp->key);
            free(temp);
        }
    }
    free(ht);
}

5. 完整示例代码

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

#define TABLE_SIZE 100

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

typedef struct HashTable {
    Entry *table[TABLE_SIZE];
} HashTable;

// 哈希函数
unsigned int hash(const char *key, int tableSize) {
    unsigned int hashValue = 0;
    while (*key) {
        hashValue = (hashValue << 5) + *key++;
    }
    return hashValue % tableSize;
}

// 创建哈希表
HashTable *createHashTable() {
    HashTable *ht = (HashTable *)malloc(sizeof(HashTable));
    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, TABLE_SIZE);

    Entry *newEntry = (Entry *)malloc(sizeof(Entry));
    newEntry->key = strdup(key);
    newEntry->value = value;
    newEntry->next = NULL;

    if (ht->table[index] == NULL) {
        ht->table[index] = newEntry;
    } else {
        newEntry->next = ht->table[index];
        ht->table[index] = newEntry;
    }
}

// 查找键值对
int search(HashTable *ht, const char *key) {
    unsigned int index = hash(key, TABLE_SIZE);
    Entry *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, TABLE_SIZE);
    Entry *current = ht->table[index];
    Entry *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 freeHashTable(HashTable *ht) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        Entry *current = ht->table[i];
        while (current != NULL) {
            Entry *temp = current;
            current = current->next;
            free(temp->key);
            free(temp);
        }
    }
    free(ht);
}

int main() {
    HashTable *ht = createHashTable();

    insert(ht, "apple", 10);
    insert(ht, "banana", 20);
    insert(ht, "orange", 30);

    printf("apple: %d\n", search(ht, "apple"));   // 输出 10
    printf("banana: %d\n", search(ht, "banana")); // 输出 20
    printf("grape: %d\n", search(ht, "grape"));  // 输出 -1

    delete(ht, "banana");
    printf("banana after delete: %d\n", search(ht, "banana")); // 输出 -1

    freeHashTable(ht);
    return 0;
}

6. 总结

  • 哈希表是一种高效的数据结构，适用于快速查找、插入和删除操作。
  • 链地址法是解决哈希冲突的常见方法。
  • 在实际应用中，可以根据需求调整哈希函数、哈希表大小和冲突解决机制。

通过以上代码，你可以在 C 语言中实现一个简单的哈希表，并用于解决实际问题。

在 C 语言中，创建结构体并不一定每次都要用 malloc。是否使用动态内存分配（malloc）取决于结构体的使用场景和生命周期需求。以下是两种主要方式及其适用场景：

1. 静态分配（无需 malloc）

直接在栈上创建结构体变量，无需手动分配或释放内存。
适用场景：结构体生命周期仅限于当前作用域（如函数内部临时使用）。

示例代码：

#include <stdio.h>

typedef struct {
    int id;
    char name[20];
} Student;

void printStudent(Student s) {
    printf("ID: %d, Name: %s\n", s.id, s.name);
}

int main() {
    // 静态分配结构体
    Student s1 = {1, "Alice"}; // 直接初始化
    Student s2;
    s2.id = 2;                // 逐个赋值
    strcpy(s2.name, "Bob");

    printStudent(s1); // 输出: ID: 1, Name: Alice
    printStudent(s2); // 输出: ID: 2, Name: Bob

    return 0;
}

特点：

  • 内存自动分配和释放（函数结束时栈内存自动回收）。
  • 无需手动管理内存，但作用域有限。

2. 动态分配（使用 malloc）

通过 malloc 在堆上分配内存，需手动释放（free）。
适用场景：

  • 结构体需要跨函数长期存在。
  • 结构体大小动态变化（如链表节点）。
  • 需要灵活控制生命周期。

示例代码：

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

typedef struct {
    int id;
    char *name; // 动态分配的字符串
} Student;

Student* createStudent(int id, const char *name) {
    Student *s = (Student*)malloc(sizeof(Student));
    if (s == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    s->id = id;
    s->name = (char*)malloc(strlen(name) + 1); // 为name分配内存
    strcpy(s->name, name);
    return s;
}

void freeStudent(Student *s) {
    free(s->name); // 先释放内部指针
    free(s);       // 再释放结构体
}

int main() {
    // 动态分配结构体
    Student *s = createStudent(3, "Charlie");
    printf("ID: %d, Name: %s\n", s->id, s->name); // 输出: ID: 3, Name: Charlie
    freeStudent(s); // 必须手动释放！

    return 0;
}

特点：

  • 内存生命周期由程序员控制（需显式调用 free）。
  • 适合复杂或长期存在的数据结构。

3. 如何选择？

方式静态分配动态分配
内存位置栈（自动管理）堆（手动管理）
生命周期当前作用域结束自动释放需显式调用 free
灵活性固定大小可动态调整（如链表、动态数组）
典型场景临时变量、小型结构体跨函数传递、动态数据结构

4. 常见问题

Q1：什么时候必须用 malloc？

  • 需要结构体在函数返回后仍然有效时（如返回结构体指针）。
  • 结构体包含动态分配的成员（如字符串、指针数组）。

Q2：忘记 free 会怎样？

导致内存泄漏，程序长时间运行可能耗尽内存。

Q3：静态分配的结构体可以返回吗？

不可以！函数返回后栈内存会被回收，返回指向局部结构体的指针是未定义行为：

// 错误示例！
Student* createStudent() {
    Student s = {1, "Alice"};
    return &s; // 返回后s的内存已失效！
}

5. 总结

  • 不需要 malloc：结构体仅在局部使用且无需动态扩展时。
  • 需要 malloc：结构体需长期存在、动态调整或包含动态成员时。
  • 始终记得配对使用 malloc 和 free 以避免内存泄漏！