您好,登錄后才能下訂單哦!
這篇“怎么使用C語言實(shí)現(xiàn)Hash表”文章的知識(shí)點(diǎn)大部分人都不太理解,所以小編給大家總結(jié)了以下內(nèi)容,內(nèi)容詳細(xì),步驟清晰,具有一定的借鑒價(jià)值,希望大家閱讀完這篇文章能有所收獲,下面我們一起來看看這篇“怎么使用C語言實(shí)現(xiàn)Hash表”文章吧。
散列表用的是數(shù)組支持按照下標(biāo)隨機(jī)訪問數(shù)據(jù)的特性,所以散列表其實(shí)就是數(shù)組的一種擴(kuò)展,由數(shù)組演化而來。可以說,如果沒有數(shù)組,就沒有散列表。
散列函數(shù)是將我們想插入的節(jié)點(diǎn)散列成一個(gè)數(shù)值的函數(shù)。它是一個(gè)函數(shù)。我們可以把它定義成 hash(key),要想找到一個(gè)不同的 key 對(duì)應(yīng)的散列值都不一樣的散列函數(shù),幾乎是不可能的。即便像業(yè)界著名的MD5、SHA、CRC等哈希算法,也無法完全避免這種散列沖突。而且,因?yàn)閿?shù)組的存儲(chǔ)空間有限,也會(huì)加大散列沖突的概率。
所以我們幾乎無法找到一個(gè)完美的無沖突的散列函數(shù),即便能找到,付出的時(shí)間成本、計(jì)算成本也是很大的,所以針對(duì)散列沖突問題,我們需要通過其他途徑來解決。
開放尋址法的核心思想是,如果出現(xiàn)了散列沖突,我們就重新探測一個(gè)空閑位置,將其插入。那如何重新探測新的位置呢?我先講一個(gè)比較簡單的探測方法,線性探測(Linear Probing)。當(dāng)我們往散列表中插入數(shù)據(jù)時(shí),如果某個(gè)數(shù)據(jù)經(jīng)過散列函數(shù)散列之后,存儲(chǔ)位置已經(jīng)被占用了,我們就從當(dāng)前位置開始,依次往后查找,看是否有空閑位置,直到找到為止。
鏈表法是一種更加常用的散列沖突解決辦法,相比開放尋址法,它要簡單很多。我們來看這個(gè)圖,在散列表中,每個(gè)“桶(bucket)”或者“槽(slot)”會(huì)對(duì)應(yīng)一條鏈表,所有散列值相同的元素我們都放到相同槽位對(duì)應(yīng)的鏈表中。
HashMap 底層采用鏈表法來解決沖突。即使負(fù)載因子和散列函數(shù)設(shè)計(jì)得再合理,也免不了會(huì)出現(xiàn)拉鏈過長的情況,一旦出現(xiàn)拉鏈過長,則會(huì)嚴(yán)重影響 HashMap 的性能。
于是,在 JDK1.8 版本中,為了對(duì) HashMap 做進(jìn)一步優(yōu)化,我們引入了紅黑樹。而當(dāng)鏈表長度太長(默認(rèn)超過 8)時(shí),鏈表就轉(zhuǎn)換為紅黑樹。我們可以利用紅黑樹快速增刪改查的特點(diǎn),提高 HashMap 的性能。當(dāng)紅黑樹結(jié)點(diǎn)個(gè)數(shù)少于 8 個(gè)的時(shí)候,又會(huì)將紅黑樹轉(zhuǎn)化為鏈表。因?yàn)樵跀?shù)據(jù)量較小的情況下,紅黑樹要維護(hù)平衡,比起鏈表來,性能上的優(yōu)勢(shì)并不明顯。
裝載因子越大,說明散列表中的元素越多,空閑位置越少,散列沖突的概率就越大。不僅插入數(shù)據(jù)的過程要多次尋址或者拉很長的鏈,查找的過程也會(huì)因此變得很慢。
最大裝載因子默認(rèn)是 0.75,當(dāng) HashMap 中元素個(gè)數(shù)超過 0.75*capacity(capacity 表示散列表的容量)的時(shí)候,就會(huì)啟動(dòng)擴(kuò)容,每次擴(kuò)容都會(huì)擴(kuò)容為原來的兩倍大小。
這里我們給出C語言的HashTable代碼,我們使用的是鏈表法,而且也沒有在鏈表過長的時(shí)候?qū)⑵滢D(zhuǎn)化為紅黑樹,只是單純的鏈表。
#include <stdlib.h> #include <stdio.h> #include <stdbool.h> typedef struct Node { int key; int val; struct Node *next; } Node; typedef struct HashMap { int size; int count; struct Node **hashmap; } HashMap; // 定義哈希函數(shù) unsigned int hash(int n) { return (unsigned int) n; } // 創(chuàng)建一個(gè)節(jié)點(diǎn) Node *creatNode(int key, int val) { Node *node = (Node *) malloc(sizeof(Node)); node->key = key; node->val = val; node->next = NULL; return node; } // 創(chuàng)建一個(gè)hash表 HashMap *createHashMap() { HashMap *H = (HashMap *) malloc(sizeof(HashMap)); H->size = 8; H->count = 0; H->hashmap = (Node **) calloc(H->size, sizeof(Node *)); return H; } // 擴(kuò)容,以2倍的形式擴(kuò)容 static void extend(HashMap *map) { int newsize = map->size * 2; Node **newhashmap = (Node **) calloc(newsize, sizeof(Node *)); for (int i = 0; i < map->size; i++) { Node *node = map->hashmap[i]; Node *head1 = (Node *) malloc(sizeof(Node)); Node *head2 = (Node *) malloc(sizeof(Node)); Node *temp1 = head1; Node *temp2 = head2; while (node) { if (hash(node->key) % newsize != i) { temp2->next = node; temp2 = temp2->next; } else { temp1->next = node; temp1 = temp1->next; } node = node->next; } temp1->next = NULL; temp2->next = NULL; newhashmap[i] = head1->next; newhashmap[i + map->size] = head2->next; free(head1); free(head2); } map->size = newsize; free(map->hashmap); map->hashmap = newhashmap; } // 插入某個(gè)結(jié)點(diǎn) bool insert(HashMap *map, int key, int val) { int hash_key = hash(key) % map->size; // 要插入的哈希值未產(chǎn)生碰撞 if (map->hashmap[hash_key] == NULL) { map->count++; map->hashmap[hash_key] = creatNode(key, val); } else { Node *head = map->hashmap[hash_key]; if (head->key == key) return false; while (head->next && head->next->key != key) head = head->next; if (head->next == NULL) { map->count++; head->next = creatNode(key, val); } else if (head->next->key == key) return false; } // 裝載因子過高就開始擴(kuò)容 if (map->count / map->size > 0.75) extend(map); return true; } // 尋找某個(gè)結(jié)點(diǎn) bool find(HashMap *map, int key, int *v) { int hash_key = hash(key) % map->size; if (map->hashmap[hash_key] == NULL) { return false; } else { Node *head = map->hashmap[hash_key]; if (head->key == key) { *v = head->val; return true; } while (head->next && head->next->key != key) head = head->next; if (head->next == NULL) return false; if (head->next->key == key) { *v = head->next->val; return true; } } return false; } // 刪除某個(gè)結(jié)點(diǎn) void delete(HashMap *map, int key) { int hash_key = hash(key) % map->size; if (map->hashmap[hash_key] == NULL) return; Node *head = map->hashmap[hash_key]; if (head->key == key) { map->hashmap[hash_key] = head->next; map->count--; free(head); return; } while (head->next && head->next->key != key) head = head->next; if (head->next == NULL) return; if (head->next->key == key) { Node *temp = head->next; head->next = head->next->next; map->count--; free(temp); } return; } int main() { HashMap *H = createHashMap(); for (int i = 0; i < 1024; i++) { insert(H, i, i); } printf("H size is %d\n",H->size); printf("H count is %d\n",H->count); delete(H, 0); int v = 0; if (find(H, 0, &v)) printf("%d\n", v); else printf("not find \n"); if (find(H, 4, &v)) printf("%d\n", v); else printf("not find \n"); return 0; }
以上就是關(guān)于“怎么使用C語言實(shí)現(xiàn)Hash表”這篇文章的內(nèi)容,相信大家都有了一定的了解,希望小編分享的內(nèi)容對(duì)大家有幫助,若想了解更多相關(guān)的知識(shí)內(nèi)容,請(qǐng)關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。