C語言實現哈希搜索算法及原理詳解

更新時間：2023年06月28日 15:08:53 作者：WangLanguager

本文主要介紹了C語言實現哈希搜索算法及原理詳解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧

一、哈希搜索算法原理

哈希搜索，也叫散列查找，是一種通過哈希表（散列表）實現快速查找目標元素的算法。哈希搜索算法通常適用于需要快速查找一組數據中是否存在某個元素的場景，其時間復雜度最高為 O(1)，而平均情況下的時間復雜度通常相當接近 O(1)，因此在實際應用中具有很高的效率和性能。

哈希搜索的核心思想是使用哈希函數將數據映射到一個哈希表中的某個位置，以便在需要查找時快速定位數據的位置，并進行數據訪問。在理想情況下，不同的元素可以被映射到哈希表的不同位置，從而實現快速查找；但是在實際應用中，由于哈希函數的不完美或者數據的特殊分布等原因，不同的元素可能會被映射到相同的位置，這就會導致哈希碰撞（Hash Collision）的問題。

解決哈希碰撞問題的方法有很多，最常見的兩種是拉鏈法和線性探測法：

拉鏈法（Chaining）：使用一個數組存儲整個哈希表，每個數組元素都是一個鏈表的頭指針，具有相同哈希值的元素會被鏈接到同一個鏈表上。當需要查找某個元素時，首先計算出該元素的哈希值，并定位到對應的鏈表上，然后遍歷該鏈表尋找目標元素。
線性探測法（Linear Probing）：使用一個數組存儲整個哈希表，在發(fā)生哈希碰撞時，從當前位置開始向后依次查找第一個空閑的位置，并將元素插入到該位置中，當需要查找某個元素時，首先計算出該元素的哈希值，并定位到對應的位置，如果該位置為空，則說明目標元素不存在于哈希表中；否則，如果該位置存儲的元素與目標元素相同，則直接返回；否則，就繼續(xù)向后查找直到找到目標元素或者遇到空位為止。

總的來說，哈希搜索是一種簡單而高效的查找算法，但是它的實現涉及到許多細節(jié)問題，需要根據不同的應用場景和數據特征來選擇最適合的哈希函數和哈希表結構，以保證其正常運行和高效性能。

二、哈希查找算法的C語言實現

下面是哈希查找算法的C語言實現示例：

#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 100 // 哈希表的大小
// 定義哈希表節(jié)點結構體
typedef struct Node {
    int key; // 節(jié)點鍵值
    int value; // 節(jié)點存儲的值
    struct Node* next; // 指向下一個節(jié)點的指針
} Node;
// 創(chuàng)建一個哈希表并返回指針
Node** createHashTable() {
    Node** hashTable = (Node**) malloc(sizeof(Node*) * TABLE_SIZE);
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable[i] = NULL;
    }
    return hashTable;
}
// 計算節(jié)點在哈希表中的下標
int getHashIndex(int key) {
    return key % TABLE_SIZE;
}
// 在哈希表中查找指定鍵值的節(jié)點，并返回該節(jié)點的指針
Node* findNode(Node** hashTable, int key) {
    int index = getHashIndex(key);
    Node* node = hashTable[index];
    while (node != NULL) {
        if (node->key == key) {
            return node;
        }
        node = node->next;
    }
    return NULL; // 沒有找到節(jié)點，返回NULL
}
// 插入一個節(jié)點到哈希表中
void insertNode(Node** hashTable, int key, int value) {
    int index = getHashIndex(key);
    Node* node = hashTable[index];
    while (node != NULL) {
        if (node->key == key) {
            node->value = value;
            return;
        }
        node = node->next;
    }
    Node* new_node = (Node*) malloc(sizeof(Node));
    new_node->key = key;
    new_node->value = value;
    new_node->next = hashTable[index];
    hashTable[index] = new_node;
}
// 從哈希表中刪除指定鍵值的節(jié)點
void deleteNode(Node** hashTable, int key) {
    int index = getHashIndex(key);
    Node* node = hashTable[index];
    Node* prev = NULL;
    while (node != NULL) {
        if (node->key == key) {
            if (prev == NULL) {
                hashTable[index] = node->next;
            } else {
                prev->next = node->next;
            }
            free(node);
            return;
        }
        prev = node;
        node = node->next;
    }
}
int main() {
    // 創(chuàng)建哈希表
    Node** hashTable = createHashTable();
    // 向哈希表中插入若干個節(jié)點
    insertNode(hashTable, 1, 2);
    insertNode(hashTable, 2, 4);
    insertNode(hashTable, 3, 6);
    // 查找節(jié)點并輸出結果
    Node* node = findNode(hashTable, 2);
    if (node != NULL) {
        printf("鍵值為 %d 的節(jié)點的值為 %d\n", node->key, node->value);
    } else {
        printf("沒有找到鍵值為 2 的節(jié)點\n");
    }
    // 刪除節(jié)點并輸出結果
    deleteNode(hashTable, 1);
    node = findNode(hashTable, 1);
    if (node != NULL) {
        printf("鍵值為 %d 的節(jié)點的值為 %d\n", node->key, node->value);
    } else {
        printf("沒有找到鍵值為 1 的節(jié)點\n");
    }
    return 0;
}

上述代碼中，我們定義了 Node 結構體表示哈希表的節(jié)點，包含了鍵值 key、存儲值 value 和指向下一個節(jié)點的指針 next。其中 createHashTable 函數用來創(chuàng)建一個新的哈希表，getHashIndex 函數用來計算節(jié)點在哈希表中的下標，findNode 函數用來在哈希表中查找指定鍵值的節(jié)點，insertNode 函數用來將新節(jié)點插入到哈希表中，deleteNode 函數用來刪除哈希表中指定鍵值的節(jié)點。

在主函數中，我們首先創(chuàng)建了一個新的哈希表，然后向哈希表中插入若干個節(jié)點，接著查找鍵值為2的節(jié)點并輸出結果，最后刪除鍵值為1的節(jié)點并輸出結果。

需要注意的是，哈希表的實現涉及到很多細節(jié)問題，比如哈希函數、沖突解決方法等，如果沒有特殊需求，可以使用已經實現好的哈希表庫，例如C++ STL庫中的 unordered_map 類。

到此這篇關于C語言實現哈希搜索算法及原理詳解的文章就介紹到這了,更多相關C語言哈希搜索內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: