c - 使用可能重复的键调整单独链接的哈希表的大小

Question

在用 C 语言编写的哈希表的单独链接实现中，我允许以 LIFO 顺序插入和删除重复的键。

调整表格大小（使其大小翻倍）的条件是每个列表平均包含 10 个项目。代码看起来像这样：

void maybeExpand(Hashtable* table)
{
    if (table->items < table->lists * 10)
        return;

    /* resize */
}

请注意，我比较的是项目数与列表数之间的比率，而不是哈希表的整个容量。

问题是当表只包含重复键并且每个列表的平均项目数大于 10 时。调整大小不会改变列表数和项目数，因此哈希表只会不断调整大小。

我想知道在哈希表中允许重复键是否是一个好的决定，如果是这样，在上述情况下该怎么办？

Answer 1

您是否需要一个允许每个键有多个值的哈希表或一个简单地覆盖的哈希表取决于具体情况，如果对如何使用哈希表有疑问，请使用某种开关来提供两者。

很难预测所有条目都散列到同一个hashbucket的情况。在任何情况下，选择一个好的哈希函数都是一项不错的投资；但总的来说，您应该只针对平均情况进行优化，而不是最坏的情况。