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