Hash魔法:哈希表的原理與實現

用C實現一個Hash表
服務器君一共花費了169.869 ms進行了6次數據庫查詢,努力地為您提供了這個頁面。
試試閱讀模式?希望聽取您的建議

一列鍵值對數據,存儲在一個table中,如何通過數據的關鍵字快速查找相應值呢?不要告訴我一個個拿出來比較key啊,呵呵。?

大家都知道,在所有的線性數據結構中,數組的定位速度最快,因為它可通過數組下標直接定位到相應的數組空間,就不需要一個個查找。而哈希表就是利用數組這個能夠快速定位數據的結構解決以上的問題的。?

具體如何做呢?大家是否有注意到前面說的話:“數組可以通過下標直接定位到相應的空間”,對就是這句,哈希表的做法其實很簡單,就是把Key通過一個固定的算法函數,既所謂的哈希函數轉換成一個整型數字,然后就將該數字對數組長度進行取余,取余結果就當作數組的下標,將value存儲在以該數字為下標的數組空間里,而當使用哈希表進行查詢的時候,就是再次使用哈希函數將key轉換為對應的數組下標,并定位到該空間獲取value,如此一來,就可以充分利用到數組的定位性能進行數據定位。

不知道說到這里,一些不了解的朋友是否大概了解了哈希表的原理,其實就是通過空間換取時間的做法。到這里,可能有的朋友就會問,哈希函數對key進行轉換,取余的值一定是唯一的嗎?這個當然不能保證,主要是由于hashcode會對數組長度進行取余,因此其結果由于數組長度的限制必然會出現重復,所以就會有“沖突”這一問題,至于解決沖突的辦法其實有很多種,比如重復散列的方式,大概就是定位的空間已經存在value且key不同的話就重新進行哈希加一并求模數組元素個數,既 (h(k)+i) mod S , i=1,2,3…… ,直到找到空間為止。還有其他的方式大家如果有興趣的話可以自己找找資料看看。?

Hash表這種數據結構在java中是原生的一個集合對象,在實際中用途極廣,主要有這么幾個特點:

  1. 訪問速度快
  2. 大小不受限制
  3. 按鍵進行索引,沒有重復對象
  4. 用字符串(id:string)檢索對象(object)

今天整理以前寫的一些算法,翻出來一個hash表的實現,就貼出來,自己也溫習溫習。先看看頭文件,也就是數據結構的定義,相當于java中的接口的概念:

#include <stdio.h>

#define    HASHSIZE 256

//定義hash表中的節點的類型
struct    nlist{
    struct    nlist    *next;
    char    *name;
    char    *defn;
};

//定義接口中的函數,也就是對外來說,這個程序可以做什么
unsigned    hash(char *s);//計算一個串的hash值
struct    nlist    *lookup(char *s);//查找一個value,根據key
struct    nlist    *install(char *name,char *defn);//插入一個key=value的對象

然后是具體實現:

#include <string.h>
#include "list.h"

static struct nlist *hashtab[HASHSIZE];

unsigned    hash(char *s)	//取得hash值
{
    unsigned    hashval;

    for(hashval = 0; *s != '\0';s++)
            hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

struct    nlist    *lookup(char *s)
{
    struct    nlist    *np;

    for(np = hashtab[hash(s)]; np != NULL; np = np->next)
        if(strcmp(s,np->name) == 0)
            return np;
    return NULL;
}

struct    nlist    *install(char *name,char *defn)
{
    struct    nlist    *np;
    unsigned    hashval;

    if((np = lookup(name)) == NULL){
        np = (struct nlist *)malloc(sizeof(struct nlist));
        if(np == NULL || (np->name = strdup(name)) == NULL)
                return NULL;
        hashval = hash(name);
        np->next= hashtab[hashval];
        hashtab[hashval] = np;
    }else
        free((void *)np->defn);
    if((np->defn = strdup(defn)) == NULL)
            return NULL;
    return np;
}

很簡單,只有兩個外部接口,

  1. install(key, value),用來插入一個新的節點
  2. lookup(key),根據一個鍵來進行搜索,并返回節點

代碼很簡單,主要用到的hash算法跟java中的String的hashcode()方法中用到的算法一樣,使用:

unsigned hash(char *s)
{
    unsigned    hashval;

    for(hashval = 0; *s != '\0';s++)
            hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}

這里的31并非隨意,乃是一個經驗值,選取它的目的在于減少沖突,當然,hash沖突這個問題是不能根本避免的。這里只是一個人們在測試中發現的可以相對減少hash沖突的一個數字,可能以后會發現更好的數值來。

延伸閱讀

此文章所在專題列表如下:

  1. Hash魔法:哈希表的原理與實現
  2. Hash魔法:一致性 hash 算法
  3. Hash魔法:分布式哈希算法
  4. Hash魔法:哈希表的工作原理與常用操作

本文地址:http://www.zqhthc.tw/librarys/veda/detail/1335,歡迎訪問原出處。

不打個分嗎?

轉載隨意,但請帶上本文地址:

http://www.zqhthc.tw/librarys/veda/detail/1335

如果你認為這篇文章值得更多人閱讀,歡迎使用下面的分享功能。
小提示:您可以按快捷鍵 Ctrl + D,或點此 加入收藏

閱讀一百本計算機著作吧,少年

很多人覺得自己技術進步很慢,學習效率低,我覺得一個重要原因是看的書少了。多少是多呢?起碼得看3、4、5、6米吧。給個具體的數量,那就100本書吧。很多人知識結構不好而且不系統,因為在特定領域有一個足夠量的知識量+足夠良好的知識結構,系統化以后就足以應對大量未曾遇到過的問題。

奉勸自學者:構建特定領域的知識結構體系的路徑中再也沒有比學習該專業的專業課程更好的了。如果我的知識結構體系足以囊括面試官的大部分甚至吞并他的知識結構體系的話,讀到他言語中的一個詞我們就已經知道他要表達什么,我們可以讓他坐“上位”畢竟他是面試官,但是在知識結構體系以及心理上我們就居高臨下。

所以,閱讀一百本計算機著作吧,少年!

《編程之美:微軟技術面試心得》 《編程之美》小組 (作者)

《編程之美:微軟技術面試心得》是一本讓人著迷的書!閱讀起來。有些題目的內容會引起強烈的共鳴,尤其是那些自己非常熟悉并且又深知解答的題目;也有一些題目讓我異常驚詫,原來除了我所知道的解答思路之外,還有更好的解答以及更深層次的原因。還有一些題目是從來沒想到過的。閱讀過程是一次愉快的享受,也是腦細胞持續活躍的過程。

更多計算機寶庫...

英超直播吻球网