在C中实现哈希表（使用链表避免冲突）的必要结构？

Question

嘿，伙计们，过去几天我一直在读关于C语言中的指针、结构和数据结构的文章。现在，我尝试通过以下教程来实现一个C语言的哈希表:https://www.tutorialspoint.com/data_structures_algorithms/hash_table_program_in_c.htm

然而，tutorialspoint假设只有1个哈希表，并使其全局化。此外，tutorialspoint没有考虑冲突。

我想做一个结构，不局限于单个哈希表，我计划将链接（以处理冲突）与链表结合起来。我有以下内容：

typedef struct node {
    int key;
    int data;
    struct node* next;
} node;

typedef struct linkedList{
    node* head;
    node* tail;
    size_t size;
} linkedList;

typedef struct hashTable{
    //perhaps an array of linked list? This member is what I need help with
    //And other potential members I am overlooking
    size_t size
} hashTable;

有些事情我需要解释一下：

>

节点结构用作一对键/数据，它有一个指向下一对具有相同哈希代码的指针。具有相同哈希代码的所有节点将位于相同的链表中。

linkedList结构表示最终将成为哈希表中一行的链表。所有链表都将是哈希表中的一行。

哈希表结构包含所有LinkedLists。

如何在哈希表结构中创建linkedList结构的数组？在我的3个结构中是否有其他成员被我忽略了？

感谢任何帮助！

附注。我计划使用我在我的链表程序中写的方法。这里是它的早期版本的链接:https://codereview.stackExchange.com/questions/176904/my-linked-list-implementation-in-c

Answer 1

typedef struct linkedList{
    node* head;
    node* tail;
    size_t size;
} linkedList;

我不认为您真的需要size_tsize。对于实际的哈希表结构，您可以执行以下操作：

typedef struct has_map {
    linkedList** table; // stores the actual collision chains.
    size_t table_capacity; // the current capacity of table.
    size_t size; // number of mappings in this hash map.
} hash_map;

另外，我建议您将table的长度保持为2的次方：2,4,8,16,...这样您就可以使用位操作hash_code%hash_map->table_capacity更改hash_code&(Hash_map->table_capacity-1)。