c - C：在字典中搜索字符串

Question

我有一个算法，我创建了一个巨大的字符串集（字典）。现在我有另一个巨大的字符串流连续到达，需要查找字典中是否存在。到目前为止，我能够实现这个场景。现在我希望如果任何字符串到达​​两次或多次，我需要将其标记为“现有”而无需再次搜索。我们怎样才能做到这一点？如果不以某种方式存储已经解析的字符串，我想不出任何方法。如果我们存储已经解析的字符串，然后检查每个字符串是否更早出现，那将是一种开销，会扼杀优化的意图。有任何想法吗？

Answer 1

你不需要检查每一个字符串来判断你以前是否见过一个。这种问题通常用哈希表来解决，它会让你知道一个元素是否在表中（嗯，它可以，但这取决于实现）。

或者您可以使用布隆过滤器，它能够快速告诉您是否尚未看到某个项目，尽管它有误报的缺点。即它可靠地告诉你是否有东西不在集合中，但告诉你“可能”，否则你必须执行进一步的检查。

Answer 2

哈希表的使用是这里最好的解决方案。它具有优化的功能，以便快速处理这项工作。简单地将每个字符串添加到 hhashtable 将隐含地为您提供检查。

Answer 3

让你的字符串数组排序。搜索将是 O(log N) 而不是 O(N)，这会带来巨大的性能提升。