C 从列表中查找字符串的子集

Question

我有一个 1M 条目的列表，我想排除其中 20,000 个条目的子集(这两个列表的顺序不同，因为它们具有相同的键(字符串))。谁能建议一个用 C 语言实现的快速搜索算法来做到这一点？

我不想每次都读取 20K 个 ID 并查看 1M 的列表。任何建议都会非常有帮助。

谢谢。

Answer 1

您要使用的是哈希集。哈希集是哈希表的一种特殊情况，它基本上在恒定时间内记录集合中是否存在元素。因此，您要做的就是将 20k ID 插入到哈希集中，然后运行 ​​100 万个字符串，看看它们是否存在于哈希集中。

以下是 C: https://github.com/avsej/hashset.c 中哈希集的实现，供您引用。

您的运行时间将为 O(n)，因为对于 1M 字符串的每次检查，它将是常数时间。