iOS標準庫中常用資料結構和演算法之雜湊表
系統提供一個全域性的key為字串的雜湊表。並提供雜湊表的建立、元素新增、元素查詢、雜湊表的銷燬的能力。儲存在雜湊表中的元素是一個如下的標準結構：
//雜湊表元素實體結構定義
typedefstruct entry {
char *key;//雜湊表中的key，必須是字串
void*data;//雜湊表中的值，是一個指標型別，其內容可以任意。
} ENTRY;
複製程式碼
一、雜湊表的建立和銷燬
功能：用於全域性雜湊表的建立和銷燬操作。
標頭檔案：#include <search.h>
平臺：BSD Unix
函式簽名：
//建立一個雜湊表 int hcreate(size_t nel); //銷燬一個雜湊表 void hdestroy(void); 複製程式碼
引數：
nel: [in]指定雜湊表的初始容量尺寸，這個引數主要用於記憶體儲存上的優化處理。
return:[out] 如果雜湊表建立成功則返回0，否則返回非0。
描述：
系統提供了一個全域性的雜湊表，因此這也是一個非常重要的缺點，因為我們無法知道其他函式是否也正在使用這個雜湊表。因此在特定時刻只有一個雜湊表是有效的。個人的感覺是這就是一個非常不合理的雜湊表實現。
二、雜湊表元素的新增和查詢。
功能：用於雜湊表元素的新增和查詢。
標頭檔案：#include <search.h>
平臺：BSD Unix
函式簽名：
ENTRY * hsearch(ENTRY item, ACTION action); 複製程式碼
引數：
item:[in] 要進行查詢或者新增的條目，這是一個ENTRY型別的資料。如果我們只是查詢則只需要設定ENTRY中的key部分的值，而如果是新增則需要設定完整的key和data的值。
action:[in]指定要對雜湊表執行的動作，這個型別是一個ACTION型別的列舉值，其定義如下：
typedefenum {
FIND, ENTER
} ACTION;
複製程式碼
當值設定為FIND時則只進行查詢處理。 當值設定為ENTER是就先進行查詢，如果不存在時就進行新增處理。
return:[out] 返回查詢或者新增時在雜湊表中的實體元素的指標。如果沒有查詢到或者新增失敗則返回NULL。我們不需要對返回的ENTRY指標進行記憶體釋放處理，而是由系統來完成。
描述：
對雜湊表執行ENTER動作時，如果找到了則直接返回以前曾經插入到雜湊表中的條目，如果沒有找到則會在雜湊表中建立一個新的條目，並返回新條目的指標。**這裡需要注意的是在執行插入時要求ENTRY結構體中的key部分的記憶體必須要用malloc進行分配，因為雜湊表在銷燬時會對所有雜湊表中的元素的key部分呼叫free處理。**也就是說對於雜湊表的插入來說key的記憶體我們負責分配，而由系統負責銷燬。這裡也存在一個BUG就是當我們對一個在雜湊表中已經存在的key再次呼叫hsearch時會返回對應的ENTRY指標。但是我們無法得知這個返回值到底是新建立的還是已經存在的。而我們的key又是通過malloc分配出來的記憶體資料，因此就無法確定我們是否需要去釋放這部分已經分配出來的key的記憶體。
示例程式碼：
void main()
{
//建立
if (hcreate(10) != 0)
{
//插入
ENTRY ent;
ent.key = malloc(4);//對於插入處理必須用malloc進行記憶體分配，而且我們不需要去釋放它。
ent.data = (int*)10;//這裡值儲存著整數型別。
strcpy(ent.key, "Bob");
ENTRY *p1 = hsearch(ent, ENTER);
NSAssert(strcmp(p1->key, "Bob")==0, @"oops!");
ent.key = malloc(6);
ent.data = (int*)20;
strcpy(ent.key, "Alice");
ENTRY *p2 = hsearch(ent, ENTER);
//查詢
ENTRY *p3 = hsearch(ent, FIND);
NSAssert(p3 == p2);
//銷燬
hdestroy();
}
}
複製程式碼
由於這個雜湊表的實現對插入重複元素時存在著BUG，以及又是全域性唯一的，所以不建議使用它。