C 中的哈希表分离链接
Hashtable separate chaining in C
我正在使用 C 语言构建哈希table，使用开放式哈希（单独链接）来存储单词。我不关心存储具有相同哈希键的单词的顺序。
目前，我有一个指向结构 (struct dict * d) 的指针和我的哈希table (struct item * arr).更具体地说，这个 table 是一个项目数组 (struct item)，包含一个单词 (char * word) 和一个指针 ( 结构项 * 下一个).
有两方面不清楚:
1. 碰撞后将单词链接在一起（插入新项目）时，我应该插入
元素在链表的开头还是结尾？
两种方式我都见过，但后者似乎更受欢迎。但是，前者对我来说似乎更快，因为我只需要将第一个项目的指针设置为我的新项目，并将其指针设置为 null。我不需要做任何指针追逐（即遍历我的链表直到找到空指针）。
2. 我的散列table应该是指向项目（结构项目）的指针数组，或者
就像我所做的那样，只是一个项目数组（结构项目）？
换句话说，特定哈希键的第一项是否应该插入到第一个单元格（一个空单元格）中，还是应该在该单元格中已经有一个我们将指向这个新项目的指针？
对于 1. 是否在列表前添加或附加并不重要。如果你保持小负载，链很短，你应该看不到访问性能有任何明显差异。如果您保持 table 较小并且负载变高，您可能需要研究不同的策略。那么访问模式可能很重要。例如，如果您更有可能查找最近插入的值，您希望它们位于列表的早期，因此最好在前面添加。但是有了散列table，如果可以的话最好保持小负载，然后就没关系了。
对于 2. 两者都可以。如果您的 table 是一个指针数组，空链为 NULL，那么一个简单的递归链表实现就可以很好地工作。使您的列表函数将列表作为参数，并使插入和删除 return 成为一个新列表。参数或 return 值可以为 NULL。然后做类似 tbl[bin] = insert(tbl[bin], val) 或 tbl[bin] = delete(tbl[bin], val) 的事情。如果链很短，你不必太担心递归开销。在任何情况下，您都不需要递归来查找值或插入，如果它只是前置，所以它只是在您无论如何都没有尾递归的地方删除。拥有链接数组的好处是要么在列表的前面得到一个虚拟元素，这通过避免空列表的特殊情况简化了非递归列表的实现，要么避免跟随指针访问第一个查找容器后链中的元素。不过，对于后者，您需要一种方法来区分空链和具有一个元素的链。这几乎不值得，如果你想避免沿着链表跳跃，开放寻址或其他一些冲突策略可能会更好。
我正在使用 C 语言构建哈希table，使用开放式哈希（单独链接）来存储单词。我不关心存储具有相同哈希键的单词的顺序。
目前，我有一个指向结构 (struct dict * d) 的指针和我的哈希table (struct item * arr).更具体地说，这个 table 是一个项目数组 (struct item)，包含一个单词 (char * word) 和一个指针 ( 结构项 * 下一个).
有两方面不清楚:
1. 碰撞后将单词链接在一起（插入新项目）时，我应该插入 元素在链表的开头还是结尾？
两种方式我都见过，但后者似乎更受欢迎。但是，前者对我来说似乎更快，因为我只需要将第一个项目的指针设置为我的新项目，并将其指针设置为 null。我不需要做任何指针追逐（即遍历我的链表直到找到空指针）。
2. 我的散列table应该是指向项目（结构项目）的指针数组，或者 就像我所做的那样，只是一个项目数组（结构项目）？
换句话说，特定哈希键的第一项是否应该插入到第一个单元格（一个空单元格）中，还是应该在该单元格中已经有一个我们将指向这个新项目的指针？
对于 1. 是否在列表前添加或附加并不重要。如果你保持小负载，链很短，你应该看不到访问性能有任何明显差异。如果您保持 table 较小并且负载变高，您可能需要研究不同的策略。那么访问模式可能很重要。例如，如果您更有可能查找最近插入的值，您希望它们位于列表的早期，因此最好在前面添加。但是有了散列table，如果可以的话最好保持小负载，然后就没关系了。
对于 2. 两者都可以。如果您的 table 是一个指针数组，空链为 NULL，那么一个简单的递归链表实现就可以很好地工作。使您的列表函数将列表作为参数，并使插入和删除 return 成为一个新列表。参数或 return 值可以为 NULL。然后做类似 tbl[bin] = insert(tbl[bin], val) 或 tbl[bin] = delete(tbl[bin], val) 的事情。如果链很短，你不必太担心递归开销。在任何情况下，您都不需要递归来查找值或插入，如果它只是前置，所以它只是在您无论如何都没有尾递归的地方删除。拥有链接数组的好处是要么在列表的前面得到一个虚拟元素，这通过避免空列表的特殊情况简化了非递归列表的实现，要么避免跟随指针访问第一个查找容器后链中的元素。不过，对于后者，您需要一种方法来区分空链和具有一个元素的链。这几乎不值得，如果你想避免沿着链表跳跃，开放寻址或其他一些冲突策略可能会更好。