table教學 在C中尋找一個好的哈希表實現




simple hash function (12)

從未使用它,但Google Sparsehash可能有效

我主要對字符串鍵感興趣。 有人能指點我去圖書館嗎?






http://www.cl.cam.ac.uk/~cwc22/hashtable/

定義的功能

* create_hashtable
* hashtable_insert
* hashtable_search
* hashtable_remove
* hashtable_count
* hashtable_destroy

使用示例

  struct hashtable  *h;
  struct some_key   *k;
  struct some_value *v;

  static unsigned int         hash_from_key_fn( void *k );
  static int                  keys_equal_fn ( void *key1, void *key2 );

  h = create_hashtable(16, hash_from_key_fn, keys_equal_fn);

  insert_key   = (struct some_key *) malloc(sizeof(struct some_key));
  retrieve_key = (struct some_key *) malloc(sizeof(struct some_key));

  v = (struct some_value *) malloc(sizeof(struct some_value));

  (You should initialise insert_key, retrieve_key and v here)

  if (! hashtable_insert(h,insert_key,v) )
  {     exit(-1);               }

  if (NULL == (found = hashtable_search(h,retrieve_key) ))
  {    printf("not found!");                  }

  if (NULL == (found = hashtable_remove(h,retrieve_key) ))
  {    printf("Not found\n");                 }

  hashtable_destroy(h,1); /* second arg indicates "free(value)" */

我有同樣的需求並進行了一些研究,最終使用了libcfu

它簡單易讀,如果我需要修改,我可以不花太多時間去理解。 它也是BSD許可證。 無需更改我的結構(嵌入說下一個指針)

由於以下原因(我的個人原因,YMMV),我不得不拒絕其他選項:

  • sglib - >這是一個宏迷宮,我不習慣只使用宏在這樣的代碼庫上調試/進行更改
  • cbfalconer - >許多許可紅旗,網站關閉以及關於支持/作者的網上太多不利討論; 不想承擔風險
  • google sparce-hash - >如前所述,它適用於C ++,而不是C語言
  • glib(gnome hash) - >看起來非常有前途; 但我找不到任何簡單的方法來安裝開發人員工具包; 我只需要C例程/文件 - 而不是完整的開發環境
  • Judy - >看起來太複雜而不能簡單使用..如果我不得不遇到任何問題,也不准備調試自己
  • npsml(這裡提到) - >找不到源碼
  • strmap發現非常簡單和有用 - 它太簡單了,鍵和值都必須是字符串; 值是字符串似乎限制太多(應該接受void *)
  • uthash - >似乎很好(已在維基百科上提到哈希表); 發現它需要修改結構 - 不想這樣做,因為性能不是我真正關心的問題 - 更多的是開發速度。

總結為非常簡單的使用strmap是好的; uthash如果你擔心額外的內存使用。 如果只是開發速度或易用性是主要目標,libcfu獲勝[注意libcfu內部進行內存分配以維護節點/哈希表]。 令人驚訝的是,沒有很多簡單的C哈希實現可用。


下載tcl並使用他們經過時間驗證的tcl哈希函數。 這很容易。 TCL API已有詳細記錄。


對於字符串, Judy數組可能很好。

Judy數組是一種複雜但非常快速的關聯數組數據結構,用於使用整數或字符串鍵存儲和查找值。 與普通數組不同,Judy數組可能稀疏; 也就是說,它們可能具有大範圍的未分配索引。

這是C中Judy庫

AC庫,提供最先進的核心技術,實現稀疏動態數組。 簡單地使用空指針聲明Judy數組。 Judy數組僅在填充時才佔用內存,但如果需要,可以增長以利用所有可用內存。

其他參考,
這個Wikipedia哈希實現參考有一些C開源鏈接。
此外, cmph - C中的Minimal Perfect Hashing Library支持多種算法。




Dave Hanson的C接口和實現包括一個精細的哈希表和其他幾個精心設計的數據結構。 還有一個很好的字符串處理接口。 如果你能負擔得起,這本書很棒,但即便沒有,我發現這個軟件設計得非常好,小到足以完全學習,並且易於在幾個不同的項目中重複使用。





hash