Google Sparsehash 包
實(shí)現(xiàn)背景：
該包由2種類型和HashTable實(shí)現(xiàn)組成。
Sparse 設(shè)計(jì)的實(shí)現(xiàn)過(guò)程中考慮的是空間優(yōu)先；dense 設(shè)計(jì)上考慮的是時(shí)間優(yōu)先。設(shè)計(jì)的注重點(diǎn)不一樣，所以實(shí)現(xiàn)也不一樣。為了和通用的STL相適應(yīng)，每一種實(shí)現(xiàn)提供了hash-map和Hash-set2種封裝方式。
在使用Hash_map和Hash_set的過(guò)程中是不需要安裝STL庫(kù)的，google提供了整個(gè)的實(shí)現(xiàn)過(guò)程。Google在實(shí)現(xiàn)的過(guò)程中大量使用了模板和泛型編程。
實(shí)現(xiàn)特點(diǎn)：
1。這個(gè)庫(kù)提供了內(nèi)存中Hash tables的一種實(shí)現(xiàn)，同時(shí)提供了持久化存儲(chǔ)的能力。實(shí)現(xiàn)上盡可能快，可移植和小。 實(shí)現(xiàn)這些目標(biāo)使用了Knuth在<<計(jì)算機(jī)程序設(shè)計(jì)藝術(shù) 第三卷>>中提到的 內(nèi)部探測(cè)散列算法（具體Hash函數(shù)的實(shí)現(xiàn)可以參考http://burtleburtle.net/bob/hash/evahash 和 http://burtleburtle.net/bob/c/lookup2.c）。與開(kāi)放鏈Hash算法不同，它不需要指向每個(gè)元素的指針項(xiàng)，在實(shí)踐中仍然達(dá)到了常數(shù)級(jí)的查找時(shí)間。
2.為了節(jié)省空間，在插入Hash table的過(guò)程中，無(wú)論是Key還是data使用Union方式：如果Key或data很小，就直接存儲(chǔ)，否則就存取一個(gè)指針。
為了便于存取Key和data,可以使用2個(gè)宏 KEY_PTR和PTR_KEY在參數(shù)和指針實(shí)際所指的數(shù)據(jù)之間轉(zhuǎn)換比如：
char key[] = "ab", *key2;
HTItem *bck; HashTable *ht;
HashInsert(ht, PTR_KEY(ht, key), 0);
bck = HashFind(ht, PTR_KEY(ht, "ab"));
key2 = KEY_PTR(ht, bck->key);
主要接口：
這個(gè)Hash table的實(shí)現(xiàn)支持的主要接口如下：
1. HashTable *AllocateHashTable(int cchKey, int fSaveKeys)
功能：分配一個(gè)Hashtable的結(jié)構(gòu)并且返回它
參數(shù)： cchKey: 為正數(shù)時(shí)候，表明每個(gè)Key是固定長(zhǎng)度的；為0表明Key是一個(gè)以\0結(jié)束的固定長(zhǎng)度的字符串。
fSaveKey: 通過(guò)是需要調(diào)用者分配Key的空間，如果設(shè)置為1，會(huì)Copy一個(gè)Key。
2. ClearHashTable(HashTable *ht)
功能：移除 hashtable的所有元素；
3. void FreeHashTable(HashTable *ht)
功能： 釋放 hashtable使用的內(nèi)存
4. HTItem *HashFind(HashTable *ht, ulong key)
功能：查詢Hashtable,找到返回該元素，否則為空；
5. HTItem *HashFindLast(HashTable *ht)
功能：返回最后查找過(guò)的的元素
6 HTItem *HashFindOrInsert(HashTable *ht, ulong key, ulong dataInsert)
功能：查找指定的Key的元素，不在就插入。
7. HTItem *HashFindOrInsertItem(HashTable *ht, HTItem *pItem)
功能：插入一個(gè)Key/data對(duì)，是否覆蓋已經(jīng)存在的元素由 SAMEKEY_OVERWRITE標(biāo)記設(shè)定。
9 HTItem *HashInsert(HashTable *ht, ulong key, ulong data)
功能： -- 插入 key/data as an HTItem.
10 int HashDelete(HashTable *ht, ulong key)
功能： -- 移除一個(gè)制定Key的元素，成功返回1，否則不存在返回0
11 int HashDeleteLast(HashTable *ht)
功能： -- 刪除最近查詢過(guò)的元素.
12 HTItem *HashFirstBucket(HashTable *ht)
功能-- 用來(lái)遍歷hashtable的桶， 遍歷過(guò)程中不要做插入和刪除操作；
13 HTItem *HashNextBucket(HashTable *ht)
-- RETURNS NULL at the end of iterating.
14 int HashSetDeltaGoalSize(HashTable *ht, int delta)
功能：一次性批量插入數(shù)據(jù)；
15 void HashSave(FILE *fp, HashTable *ht, int (*dataWrite)(FILE *, char *))
功能:將整個(gè)Hash表的內(nèi)容保存在文件中。如果數(shù)據(jù)域是一個(gè)指針或者復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，需要傳遞一個(gè)函數(shù)指針將文件指針作為參數(shù)，此時(shí)可以寫入你想寫入的東西，函數(shù)返回寫入的字節(jié)數(shù)。如果數(shù)據(jù)域是整數(shù)，不需要傳函數(shù)指針。
16 static HashTable *HashDoLoad(FILE *fp, char * (*dataRead)(FILE *, int),
HashTable *ht)
功能： --裝入Hash表. 他需要一個(gè)函數(shù)來(lái)讀取一個(gè)文件的結(jié)構(gòu)和結(jié)構(gòu)的大小。功能與 HashSave對(duì)應(yīng)。
17 HashTable *HashLoadKeys(FILE *fp, char * (*dataRead)(FILE *, int))
功能： -- 與 HashLoad(),不同 只有必要的時(shí)候才從磁盤Load相應(yīng)的數(shù)據(jù).這種方法可以節(jié)省內(nèi)存 。
注意：在裝入數(shù)據(jù)的時(shí)候不應(yīng)該插入和刪除數(shù)據(jù)。
功能擴(kuò)展：
這個(gè)HashTable實(shí)現(xiàn)沒(méi)有使用共享內(nèi)存的方式，我們可以對(duì)AllocateHashTable進(jìn)行簡(jiǎn)單改寫使用共享內(nèi)存的方式；另外這個(gè)Hashtable沒(méi)有提供自動(dòng)淘汰節(jié)點(diǎn)的功能，可以增加LRU，對(duì)訪問(wèn)節(jié)點(diǎn)的計(jì)數(shù)和時(shí)間統(tǒng)計(jì)，在無(wú)法繼續(xù)插入新的節(jié)點(diǎn)時(shí)候觸發(fā)淘汰操作。
|