1. 首頁
  2. 問答
  3. 在C中尋找一個好的散列表實現

在C中尋找一個好的散列表實現

2009-07-16 46 views

回答

8

對於字符串，Judy Array可能是好的。

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

這裏是一個Judy library in C。

提供實現稀疏動態數組的最先進核心技術的C庫。 Judy數組被聲明爲一個空指針。 Judy數組只有在填充時纔會消耗內存，但如果需要，它可以增長以充分利用所有可用內存。

其他參考資料，
這Wikipedia hash implementation reference有一些C開放源代碼的鏈接。
另外，cmph - 在C最小完美散列庫，支持幾種算法。

來源

2009-07-16 16:27:46 nik

2

從未使用過它，但Google Sparsehash可能工作

來源

2009-07-16 16:29:06 Nick

+2

我認爲sparsehase用C++編寫。 – 2009-07-16 16:37:16

+0

我認爲你是對的 – Nick 2009-07-16 17:14:41

+1

事實上，在這種情況下C是感興趣的語言 - 而不是C++。 – SetJmp 2009-07-17 00:37:34

0

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)" */

來源

2009-07-16 16:31:05

+5

404錯誤。你會更新鏈接嗎？ – 2013-01-04 21:12:19

0

下載tcl和使用他們的時間證明TCL散列函數。這很容易。 TCL API是有據可查的。

來源

2009-07-16 16:45:54 xcramps

16

GLib是一個偉大的圖書館，作爲您的C項目的基礎。他們有一些不錯的數據結構產品，包括哈希表：http://developer.gnome.org/glib/2.28/glib-Hash-Tables.html（鏈接更新2011年4月6日）

來源

2009-07-16 16:56:29

+0

+1：Glib確實是一個很棒的圖書館。 – 2009-07-17 01:24:51

+1

我是否正確地認爲你通常動態鏈接到glib庫以使用這些數據結構，如果從linux移到windows，可能會創建移植問題？ – bph 2012-01-23 10:35:05

+0

Glib只支持32位。如果你使用大量數據，glib不會是一個好選擇 – Thorn 2013-02-25 19:10:32

5

戴夫·漢森的C Interfaces and Implementations包括罰款哈希表和幾個其他精心設計的數據結構。還有一個不錯的字符串處理界面。如果你負擔得起，這本書是非常棒的，但即使沒有，我也發現這個軟件設計得非常好，足夠小，可以完整地學習，並且可以輕鬆地在幾個不同的項目中重複使用。

來源

2009-07-17 01:16:42

55

我有同樣的需求，做了一些研究，並最終使用libcfu

它簡單易讀，所以如果我需要修改，我可以做到這一點，而無需花費太多時間來理解。它也是BSD許可證。無需改變我的結構（以嵌入說下一個指針）

我不得不拒絕理由如下（我個人的原因，情況因人而異）其它選項：

  • sglib - >這是宏迷宮我很不習慣使用宏來調試/製作 這樣一個代碼庫的變化
  • cbfalconer - >很多許可redflags，並且該網站被關閉並且在網上關於支持/作者的討論太多;不想承擔風險
  • google sparce-hash - >如前所述，這是針對C++的，而不是C
  • glib（gnome hash） - >看起來非常有前途;但我找不到安裝開發工具包的簡單方法;我只需要在C例程/文件 - 而不是完全成熟的研究與開發環境
  • 朱迪 - >似乎是一個簡單的使用太複雜..還沒有準備調試自己，如果我不得不遇到任何問題
  • npsml（在這裏提到） - >找不到源
  • strmap發現非常簡單和有用 - 它太簡單了，鍵和值都必須是字符串;價值是字符串似乎太限制（應接受無效*）
  • uthash - >似乎很好（已在維基百科上提到散列表）;發現它需要對結構進行修改 - 不想這樣做，因爲性能並不是我使用的關注點 - 它更多的是開發速度。

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

來源

2011-12-12 06:39:15

相關問題

 相關問題