*NIX programming : 系統提供的 HASH實作
各位如果不愛看我的說明,可以自行 man 取得外國人寫的文件.
--------------------------------------------
首先來看這三個介面的原型定義
int hcreate(size_t nel);
ENTRY *hsearch(ENTRY item, ACTION action);
void hdestroy(void);
首先hcreate 是通知系統先配置好一個記憶體空間. hsearch 則是負責hash元素的加入與搜尋(別被函式名稱騙了),hdestroy就是把hcreate配置的空間釋放掉
基本的使用方式就是找一個你喜歡的地方先呼叫hcreate分配空間,hcreate必定在任何hash操作前呼叫.然後用hsearch 加入你的鍵值跟資料.當然要搜尋也是呼叫hsearch.
看一下這三個介面原型,發現他們不會傳回一個hash的實體物件對不對? 是的,他只能管理一個HASH table.
好拉,現在讓我們插的更深入一點(咳咳....),講一下這三個函式的詳細用法
int hcreate(size_t nel);通知OS先分配記憶體開始實作HASH . nel 參數是要通知系統你"預估"HASH最大的量是多少.但是,每個作業系統提供的演算法實作都所有不同,系統不一定會真的分配nel數量的空間出來,
int hcreate(size_t nel);通知OS先分配記憶體開始實作HASH . nel 參數是要通知系統你"預估"HASH最大的量是多少.但是,每個作業系統提供的演算法實作都所有不同,系統不一定會真的分配nel數量的空間出來,
ENTRY *hsearch(ENTRY item, ACTION action);
hsearch 實際上負責元素的加入與元素的搜尋.其中 ENTRY資料型別如下
typedef struct entry {
typedef struct entry {
char *key;
void *data;
} ENTRY;
key 成員就是HASH的"鍵值",data 就是我們準備要存放的資料,key的資料必須是一個符合C語言合法的字串資料,也就是說必須由0結尾拉.data的型別則是void * ,表示他不管你的型別,他也不會幫你把data的資料內容copy一份到額外的記憶體,他只是幫你紀錄data的記憶體指標...
hsearch要怎麼分辨你是要加入還是要搜尋呢? action 參數就是了.action 參數有兩個選擇,ENTER 和FIND 兩個,看字面就知道了吧...
要如何加入呢? 首先先分配一個 ENTRY 物件.然後把鍵值指向key 成員,把你要的資料指向data 成員 ,接著呼叫hsearch,action 參數用 ENTER . example :
ENTRY obj;
DATA * data_obj;
obj.key="elemet 1";
obj.data=(void*)data_obj;
hsearch(obj,ENTER);
會不會覺得奇怪,第一個參數不是用傳址而試用傳值,把整個ENTRY物件傳入stack 給hsearch用.這是第一個陷阱,第二個陷阱,有些作業系統的實作並沒有明確說明當實際插入的元素大於你預估值的時候會發生什麼事.沒錯拉,POSIX是有規定一個錯誤值MNOMEM表示資料沒地方放了.可是並沒有明確規定插入元素大於預估值就要丟出這個錯誤吧.看每個作業系統的實作.當然我希望他能聰明的自動增加,永遠不要回傳錯誤,因為誰能保證,資料量永遠在預期內?
第三個陷阱,data的資料是一個指標,表示作業系統只是幫你把data的位置記錄下來,但是data得資料內容則不負責.例如,你呼叫了hsearch加入一個data的指標,然後你不小心哪邊把data指標指向的記憶體釋放了,程式就會爆炸了...
知道怎麼插入後,接下來就是學會怎麼抽出囉(噗...).一樣用hsearch,只是action 換成 FIND . example :
ENTRY obj;
ENTRY * ret;
obj.key="elemet 1";
ret = hsearch(obj,FIND);
if(ret == NULL) {
printf("沒找到,key值不在hash表裡\n");
} else {
printf("key = %s,data = %p\n",ret->key,ret->data);
}
void hdestroy(void);
把hcreate 配置的記憶體還給系統.這個你還要我多說什麼嗎....
-------------------------------------------
以上就是*NIX 遵照 POSIX 規範提供的hash功能實作.如果我的說明還不夠你用,可以求助 google code search 或是 man 指令.至於windows API,我還沒有找到這三個介面的函式定義,可能windows API有提供更好的吧
留言