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