C語言-雜湊表(Hash table,也叫哈希表)-沒有資料庫又要快速搜尋的資料結構演算法

C語言-雜湊表(Hash table,也叫哈希表)-沒有資料庫又要快速搜尋的資料結構演算法

C語言-雜湊表(Hash table,也叫哈希表)-沒有資料庫又要快速搜尋的資料結構演算法


雜湊表(Hash table,也叫哈希表),是根據鍵(Key)而直接查詢在內存存儲位置的資料結構。也就是說,它通過計算一個關於鍵值的函數,將所需查詢的數據映射到表中一個位置來查詢記錄,這加快了查找速度。這個映射函數稱做雜湊函數,存放記錄的數組稱做雜湊表。


一個通俗的例子是,為了查找電話簿中某人的號碼,可以創建一個按照人名首字母順序排列的表(即建立人名 {\displaystyle x} x到首字母 {\displaystyle F(x)} F(x)的一個函數關係),在首字母為W的表中查找「王」姓的電話號碼,顯然比直接查找就要快得多。這裡使用人名作為關鍵字,「取首字母」是這個例子中雜湊函數的函數法則 {\displaystyle F()} F(),存放首字母的表對應雜湊表。關鍵字和函數法則理論上可以任意確定。


資料來源:https://zh.wikipedia.org/wiki/%E5%93%88%E5%B8%8C%E8%A1%A8

https://blog.csdn.net/smstong/article/details/51145786
https://mp.weixin.qq.com/s?__biz=MzI2NjA3NTc4Ng==&mid=2652081098&idx=1&sn=fbf7d3021ed17bedc8eb62bc997bedc3&chksm=f174802fc6030939686549d596d27a1d90fec683afdcf0fb59934f5ee3131f3cba92e39d12e1&scene=0&xtrack=1&key=a6e428af7bc20b4ec1d88814f483cd8573327a2a636d2d8ee0db8f4b4881aaba847e7f578053a0136c95477a6428492b832966015bcff77cd33b5b339c7fc803dbcebc8f549e536facfa6f80c55e7822&ascene=1&uin=MjIwODk2NDgxNw%3D%3D&devicetype=Windows+10&version=62060833&lang=zh_TW&pass_ticket=n%2BryKuocjshj%2FviC%2FQR8cPIy2PXfuyFlk35RNGNb3ZSMIZrIoRZKr7lcuiC9DOlK


GITHUB: https://github.com/jash-git/C_HashTable


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

#include "HashTable.h"

// 出處 https://blog.csdn.net/smstong/article/details/51145786
// 要放入哈希表中的结构体
struct Student
{
    int age;
    float score;
    char name[32];
    char data[1024 * 1024* 10];
};

// 结构体内存释放函数
static void free_student(void* stu)
{
    free(stu);
}

// 显示学生信息的函数
static void show_student(struct Student* p)
{
    printf("name:%s, age:%d, credit:%.2f\n", p->name, p->age, p->score);
}

void pause()
{
    printf("Press Enter key to continue…");
    fgetc(stdin);
}

int main()
{
    // 新建一个HashTable实例
    HashTable* ht = hash_table_new();
    if (NULL == ht) {
        return -1;
    }

    // 向哈希表中加入多个学生结构体
    int i=0;
    for (i = 0; i < 100; i++)
    {
        struct Student * stu = (struct Student*)malloc(sizeof(struct Student));
        stu->age = 18 + rand()%5;
        stu->score = 50.0f + rand() % 100;
        sprintf(stu->name, "Classmate%d", i);
        hash_table_put2(ht, stu->name, stu, free_student);
    }

    // 根据学生姓名查找学生结构
    for (i = 0; i < 100; i++)
    {
        char name[32];
        sprintf(name, "Classmate%d", i);
        struct Student * stu = (struct Student*)hash_table_get(ht, name);
        show_student(stu);
    }

    // 销毁哈希表实例
    hash_table_delete(ht);
    pause();
    return 0;
}

5 thoughts on “C語言-雜湊表(Hash table,也叫哈希表)-沒有資料庫又要快速搜尋的資料結構演算法

  1. 雜湊表 ( Hash Table )

    https://medium.com/change-or-die/%E6%BC%94%E7%AE%97%E6%B3%95%E5%9C%96%E9%91%91-%E7%AC%AC%E4%B8%80%E7%AB%A0-%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B-10d5a6337be5

    ▲雜湊表 ( Hash Table ) 的資料結構,是由「雜湊函數 ( Hash Function)」有效率地進行數據搜尋。

    ▲儲存的資料為成對的鍵 ( Key ) 和值 ( Value )。

    ▲使用雜湊函數計算出資料的鍵所對應的雜湊值,並透過餘數運算取得餘數值,並將該數值作為索引位址,最後將資料存入該位置中。

    ▲當兩筆或兩筆以上不同的資料,經過雜湊函數和餘數運算後得到相同的值,也就是資料的儲存位置重複時,稱為「碰撞 ( Collision ) 」。

    ▲發生碰撞時,可以藉由列表將資料接續在先前已存入的資料之後,這種方法稱為「額外鏈結法 ( Separate Chaining )」。

    ▲發生碰撞時,最廣為應用的為「開放定址法 ( Open Addresssing )」。發生碰撞會求出第二候補位址並儲存,若位址已滿則會繼續找下一個候補位址,直至找到空的位址。

    ▲雜湊表主要可以分作兩大類:「額外鏈結法 ( Separate Chaining )」 以及「開放定址法 ( Open Addresssing )」。

    ▲其中「開放定址法 ( Open Addresssing )」根據資料存放的邏輯又分成兩種方法:「線性探測法 ( Linear Probing) 」及 「二次探查 ( Quadratic Probing) 」。[ 參考資料: http://alrightchiu.github.io/SecondRound/hash-tableopen-addressing.html ]

    ▲雜湊表能夠彈性儲存數據,又可以快速讀取數據,常用於程式語言的關聯陣列 ( Associative Array )。

    雜湊表需要多少執行時間?
    平均情況:搜尋、插入、刪除,皆為 O(1)
    最壞情況:搜尋、插入、刪除,皆為 O(n)

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *