linux hash表使用

Linux中的哈希表（Hash Table）是一种高效的数据结构，用于存储键值对，并支持快速的查找、插入和删除操作。以下是关于Linux哈希表的基础概念、优势、类型、应用场景以及常见问题及解决方法：

基础概念

哈希函数：将键转换为哈希表索引的函数。
哈希冲突：不同的键通过哈希函数计算出相同的索引。
开放寻址法：当发生冲突时，通过某种探测方法寻找下一个空闲位置。
链地址法：每个哈希表槽位存储一个链表，冲突的元素添加到链表中。

优势

快速查找：平均时间复杂度为O(1)。
高效的插入和删除：不需要移动大量数据。

类型

开放寻址哈希表：如线性探测、二次探测等。
链地址哈希表：每个槽位维护一个链表。

应用场景

内核数据结构：如Linux内核中的路由表、文件系统缓存等。
用户空间应用：如数据库索引、缓存系统等。

示例代码（链地址法）

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

typedef struct Node {
    int key;
    int value;
    struct Node* next;
} Node;

typedef struct HashTable {
    int size;
    Node** table;
} HashTable;

HashTable* createHashTable(int size) {
    HashTable* ht = (HashTable*)malloc(sizeof(HashTable));
    ht->size = size;
    ht->table = (Node**)malloc(sizeof(Node*) * size);
    for (int i = 0; i < size; i++) {
        ht->table[i] = NULL;
    }
    return ht;
}

int hashFunction(int key, int size) {
    return key % size;
}

void insert(HashTable* ht, int key, int value) {
    int index = hashFunction(key, ht->size);
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = NULL;

    if (ht->table[index] == NULL) {
        ht->table[index] = newNode;
    } else {
        Node* current = ht->table[index];
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
}

int search(HashTable* ht, int key) {
    int index = hashFunction(key, ht->size);
    Node* current = ht->table[index];
    while (current != NULL) {
        if (current->key == key) {
            return current->value;
        }
        current = current->next;
    }
    return -1; // Not found
}

void delete(HashTable* ht, int key) {
    int index = hashFunction(key, ht->size);
    Node* current = ht->table[index];
    Node* prev = NULL;
    while (current != NULL) {
        if (current->key == key) {
            if (prev == NULL) {
                ht->table[index] = current->next;
            } else {
                prev->next = current->next;
            }
            free(current);
            return;
        }
        prev = current;
        current = current->next;
    }
}

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

int main() {
    HashTable* ht = createHashTable(10);
    insert(ht, 1, 100);
    insert(ht, 11, 200);
    printf("Value for key 11: %d\n", search(ht, 11));
    delete(ht, 11);
    printf("Value for key 11 after deletion: %d\n", search(ht, 11));
    freeHashTable(ht);
    return 0;
}