Google Sparse Hash 簡介

fmms 12年前發布 | 62K 次閱讀 C/C++開發 C/C++

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，對訪問節點的計數和時間統計，在無法繼續插入新的節點時候觸發淘汰操作。