C語言哈希表詳解

一、什麼是哈希表

哈希表是一種根據關鍵碼值(Key Value)直接進行訪問的數據結構。通俗的說，哈希表就是把一個關鍵碼值(Key Value)通過哈希函數轉換為一個索引，該索引指向在表中對應的記錄。哈希函數可以將任意長度的輸入映射為較小的固定長度的輸出。一般情況下，哈希表的查詢和插入操作的時間複雜度為 O(1)，在某些特殊情況下，時間複雜度為 O(n)。

二、哈希表的實現

哈希表的實現主要包括哈希函數和哈希衝突處理兩部分。

1. 哈希函數

哈希函數是將關鍵碼值映射到哈希表中的位置的函數。

int hash_func(char *key)
{
    unsigned long hash = 5381;
    int c;
    while ((c = *key++))
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    return hash % HASH_SIZE;
}

hash_func() 函數採用了比較常用的「乘法散列法」，可以將字元串轉換為哈希表中的位置。

2. 哈希衝突處理

哈希衝突指的是兩個關鍵字經過哈希函數映射到了同一個位置的情況。

常見的哈希衝突處理方法有「鏈式解決法」和「開放定址法」。

鏈式解決法

鏈式解決法通過鏈表將哈希表中相同位置的多個元素串連在一起。

typedef struct NODE
{
    char *key;
    char *val;
    struct NODE *next;
} NODE;

NODE *hash_table[HASH_SIZE];

void put(char *key, char *val)
{
    int pos = hash_func(key);
    NODE *head = hash_table[pos];
    NODE *p = head;

    while (p)
    {
        if (strcmp(p->key, key) == 0)
        {
            p->val = val;
            return;
        }
        p = p->next;
    }

    NODE *new_node = (NODE*)malloc(sizeof(NODE));
    new_node->key = key;
    new_node->val = val;
    new_node->next = NULL;

    if (head == NULL)
        hash_table[pos] = new_node;
    else
    {
        p = head;
        while (p->next)
            p = p->next;
        p->next = new_node;
    }
}

char *get(char *key)
{
    int pos = hash_func(key);
    NODE *p = hash_table[pos];
    while (p)
    {
        if (strcmp(p->key, key) == 0)
            return p->val;
        p = p->next;
    }
    return NULL;
}

開放定址法

開放定址法是指當哈希衝突發生時，通過向前/後尋找空閑位置來解決衝突的方法。

char *hash_table[HASH_SIZE];

void put(char *key, char *val)
{
    int pos = hash_func(key);
    
    while (hash_table[pos] != NULL && strcmp(hash_table[pos], key) != 0)
    {
        pos = (pos + 1) % HASH_SIZE;
    }

    hash_table[pos] = val;
}

char *get(char *key)
{
    int pos = hash_func(key);
    
    while (hash_table[pos] != NULL && strcmp(hash_table[pos], key) != 0)
    {
        pos = (pos + 1) % HASH_SIZE;
    }

    return hash_table[pos];
}

三、哈希表的應用

哈希表廣泛應用於數據存儲、索引，如：資料庫中的索引、編譯器中的符號表、DNS解析中的緩存等。

四、總結

哈希表是一種基於哈希函數實現的數據結構，主要包括哈希函數和哈希衝突處理兩部分，通過鏈式解決法和開放定址法來處理哈希衝突。哈希表具有查詢和插入操作的時間複雜度為 O(1) 的優點，廣泛應用於數據存儲、索引等方面。