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

Question

大家好，过去几天我一直在阅读 C 语言中的指针、结构和数据结构。现在我正尝试按照本教程在 C 中实现哈希 Table：https://www.tutorialspoint.com/data_structures_algorithms/hash_table_program_in_c.htm

然而 tutorialspoint 假设只有 1 个散列 table 并且它正在使其成为全球性的。此外，tutorialspoint 不考虑碰撞。

我想创建一个不限于单个散列的结构 table 并且我计划将链接（以处理冲突）与 linked 列表结合起来。我有以下内容：

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;

我需要说明的一些事情：

节点结构作为一对key/data，它有一个指向具有相同哈希码的下一对的指针。具有相同哈希码的所有节点将在相同的 linked 列表中。
linkedList 结构表示一个 linked 列表，最终将成为散列 table 中的一行。所有 linked 列表都将是散列 table.
散列Table 结构包含所有 linkedList。

如何在我的 hashTable 结构中创建一个 linkedList 结构的数组？在我的 3 个结构中是否还有其他成员被我忽视了？

感谢任何帮助！

P.S。我打算使用我在链表程序中编写的方法。这是它的早期版本的 link：https://codereview.stackexchange.com/questions/176904/my-linked-list-implementation-in-c

Answer 1

您可以使用您的节点和列表结构。散列 table 将只是一个包含列表数组的结构。散列的大小 table 可以是动态的，但我们使用常量大小：

enum {
    hashSize = 32
};

typedef struct hashTable {
    linkedList list[hashSize];
    size_t size;                     // How many elelents overall?
} hashTable;

您的哈希函数必须 return 一个小于 hashSize 的无符号哈希值。

但是你并不是真的需要链表结构。这种结构便于在前端和末端轻松插入，并且还保留了其元素的数量。列表的元素是无序的，所以你总是可以在前面插入，而且你真的不需要大小，所以你可以通过指向它们头部的指针来定义链表，最初都是 NULL：

typedef struct hashTable {
    node *head[hashSize];
    size_t size;
} hashTable;

（但如果你已经有了链表的代码，链表的数组可能是可行的方法。）

关于您链接的 tutorialspoint 代码的注释：它确实解决了冲突问题，但它使用了另一种方法：每个哈希码只有一个槽。如果哈希码的插槽已被使用，它将使用下一个可用的哈希码。

这种方法意味着您不能简单地删除元素。假设您插入一个哈希值为 5 的项目，但该槽位已被另一个具有不同键但具有相同哈希码的项目占用。假设 6 和 7 也被占用，所以您将该项目插入插槽 8。如果您搜索该项目，搜索首先查看插槽 5，但那里的项目不匹配。增加 has 代码，最终在插槽 8 中找到该项目。如果我们首先找到一个空插槽，则搜索将被取消但没有成功。移除插槽 5 中的项目会使插槽 8 中的项目无法访问。因此，必须在该插槽中放置一个虚拟元件。您的链表方法不需要这样的虚拟元素。

（tutorialspoint 方法还意味着如果散列 table 已满，您将搜索所有元素，这并不比搜索未排序的数组好多少。链表散列 table永远不会满，但是当 table 中的项目数远大于散列 table 大小时，性能会下降。）

Answer 2

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

我认为您不需要size_t size。实际散列 table 结构是什么，你可以这样做：

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 - 1).

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

Necessary Structs to implement a HashTable (that uses a Linked List to avoid collisions) in C?

c

hashtable

linked-list