C99中的HashTable和Vector-like數據結構

Question

我想創建一個依賴於C99中的獨立矢量數據結構的哈希表。我可以在OO的幫助下用C++來做到這一點，但我不確定如何使用結構和聯合來解決這個問題。

我寧願任何鏈接的例子都不包括具有高度複雜的散列函數的散列表實現。我不特別關心存儲的衝突或效率。我只想要關於如何進行的建議或者一個簡單的例子來說明相應數據結構的形式而不是功能。

Answer 1

如果我正確推斷您想以完全通用的方式實現增長的哈希表，那麼您將需要很多void指針。向量是不是太硬，它只是需要大量的輸入：

typedef struct { 
    size_t capacity, nelems; 
    void **contents; 
} Vector; 

enum { INITIAL_CAPACITY = 256 }; 

Vector *make_vector() 
{ 
    Vector *v = malloc(sizeof(Vector)); 
    if (v == NULL) 
     return NULL; 
    v->capacity = INITIAL_CAPACITY; 
    v->contents = malloc(sizeof(void *) * v->capacity); 
    if (v->contents == NULL) { 
     free(v); 
     return NULL; 
    } 
    v->nelems = 0; 
    return v; 
} 

// exercise for the reader 
int vector_append(Vector *, void *); 
void *vector_at(Vector const *); 

請記住，一個通用的哈希函數將有原型size_t hash(void const *, size_t)，即你需要的大小來傳遞。 （注意：你不會錯過C++的OOP特性;它是模板，他們購買的類型安全性，以及語法糖，比如操作符重載）。更多示例請參見OpenBSD的ohash庫。 ）

Answer 2

下面的書有可能使用C中的結構既鏈表的最好的說明和哈希表：

http://en.wikipedia.org/wiki/The_C_Programming_Language_(book）

它實現了一個簡單的散列算法爲好。

另一種簡單的，但均勻分佈的散列算法是如在此定義的CDB算法：

http://cr.yp.to/cdb/cdb.txt