c - 在 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;

需要说明的几点:

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

2. linkedList 结构代表一个链表，最终将成为哈希表中的一行。所有链表在哈希表中都是一行。

3. 哈希表结构包含所有链表。

如何在我的 hashTable 结构中创建一个 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_t size。对于实际的哈希表结构，您可以这样做:

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)。