C語言實現(xiàn)哈希搜索算法及原理詳解

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

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

一、哈希搜索算法原理

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

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

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

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

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

二、哈希查找算法的C語言實現(xiàn)

下面是哈希查找算法的C語言實現(xiàn)示例：

#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 100 // 哈希表的大小
// 定義哈希表節(jié)點結(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é)點并輸出結(jié)果
    Node* node = findNode(hashTable, 2);
    if (node != NULL) {
        printf("鍵值為 %d 的節(jié)點的值為 %d\n", node->key, node->value);
    } else {
        printf("沒有找到鍵值為 2 的節(jié)點\n");
    }
    // 刪除節(jié)點并輸出結(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é)構體表示哈希表的節(jié)點，包含了鍵值 key、存儲值 value 和指向下一個節(jié)點的指針 next。其中 createHashTable 函數(shù)用來創(chuàng)建一個新的哈希表，getHashIndex 函數(shù)用來計算節(jié)點在哈希表中的下標，findNode 函數(shù)用來在哈希表中查找指定鍵值的節(jié)點，insertNode 函數(shù)用來將新節(jié)點插入到哈希表中，deleteNode 函數(shù)用來刪除哈希表中指定鍵值的節(jié)點。

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

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

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

您可能感興趣的文章: