如果我有一个m键数组和一个n目标数组,在搜索它之前,如何验证m[i]存在于n中?

你可能在想 Bloom filters ,它正好用于这个案例。它们可能会给你带来误报,在这种情况下,你必须在真正的表中搜索,但在大多数情况下,如果你没有存储项目,就会从一开始就告诉你。

哈希表通常是存储的最佳选择;但是如果您的密钥空间远远大于目标的数量,则会有大量的哈希冲突,您必须检查存储的目标是否确实存在您正在查找的密钥。如果关键比较很昂贵,它很快就会成为一个因素。

可以使用n值作为键构建哈希表。

然后尝试访问hash[m[i]],如果它返回一个值,那么它就存在,即o(1)(忽略冲突)。

因为n是静态的,所以可以考虑创建一个 Perfect Hash N的函数。这将使您的搜索 放心 O(1)时间。

clr的算法书籍有一章介绍这个,上面的wiki页面有一些链接,您可能会发现这些链接很有用。不过,这可能太复杂了 您可能很难找到一个有用的实现。 . 看 Gperf 用于实现。

但是,您可以始终使用一个通常可用的哈希表,其值应为O(1)。

我想你是在存储一些额外的信息,你想在知道它存在的情况下检索这些信息吗?你怎么储存这些?

你可能会发现 B-Tree 在这种情况下很有用(行业标准数据库通常使用其中的一些变体),甚至可以用作索引!所以,你搜索,如果你找到了它,你就有了指向它的数据/指针。您将在Web上找到这些的许多实现。