搜索性能调优

Question

我对DS和算法相当陌生，最近在一次工作面试中，我被问到一个关于性能调优和代码的问题。我们有一个包含数十亿个条目的数据结构，我们需要在该数据结构中搜索特定的单词。那么，我们可以使用哪种Java特性/库在尽可能快的时间内进行搜索呢？

当时我想不出确切的答案，所以我写道：

1. 我们可以将值存储在地图中，并在地图中搜索单词（但在如何确定地图中的键值对方面遇到了困难）

我如何才能理解这个问题的确切答案，以及什么是最佳解决方案？

Answer 1

您没有提到条目是单词还是文档（多个单词）。在这两种情况下，搜索索引都是合适的。

搜索索引从十亿个文档条目中提取单词，并管理这些单词到它们所用文档的映射。Lucene等框架（例如作为SOLR或ElasticSearch的一部分）为您管理内存和持久性。

如果只有数千个条目，那么一个简单的HashMap就足够了，因为那时不需要内存管理。如果十亿个条目都是单个单词，那么数据库可能是一个更好的选择。

Answer 2

假设内存需求不是问题，并且数据结构已经填充，那么有两种数据结构允许高效搜索。

关于时间复杂度，Set#contains和Map#containsKey都是O（1），假设哈希函数并不昂贵，也没有太多冲突。

因为数据结构存储单词（假设您指的是字符串s），所以使用trie（基数树、前缀树等）也可能相对有效，这将允许您按字符进行搜索（我认为是O（logn））。如果哈希函数很昂贵或者有很多冲突，这可能是一个很好的选择！

你给面试官的答案应该足够了，因为哈希是一种有效的搜索方法，即使是对于数十亿条条目。

Answer 3

在阅读了这个问题并在评论中得到了澄清之后，我认为对我来说显而易见的是：你需要提出后续问题。

我会尝试将其分解，并提供我希望会有所帮助的评论，因为我也知道“当下”是什么感觉，以及在你最不需要的时候，神经会如何刺伤你的背部。

我们有一个包含数十亿个条目的数据结构，我们需要在该数据结构中搜索特定的单词。

我认为一个很好的后续问题是：

问：用于包含所有这些数据的具体数据结构是什么？

我会一直按，直到他们给我一个实际的名字，并解释为什么不能命名Java算法/库。据你所知，数据结构可能是String[]，一个集合

措辞还暗示他们实现了这个结构，并且它已经在一个系统中填充了，大概有足够的内存来容纳所有的内容。要求确认这是真的可能会给你有用的信息。

例如：“根据措辞，这个神秘的数据结构似乎已经在一个有足够内存的系统中实现并完全填充在内存中。你能确认我在这里的理解是正确的吗？如果不能，你能进一步澄清吗？”

考虑到建议的措辞，以及我们没有其他澄清的事实，为了回答这个问题，我将假设我的假设确实是正确的。

请注意，如果您被要求设计数据结构来保存所有这些信息，您将不得不提出非常不同的问题，考虑内存限制，甚至可能需要询问字符集/编码（例如ASCII与多字节Unicode）。

此外，如果你被要求设计搜索算法，那么知道DS是一个先决条件，而不知道这一点可能会使任务变得不可能。例如，如果你在处理一个数组和一个二进制搜索树，二进制搜索算法的实现看起来会非常不同，尽管两者都会提供O（lgn）的时间复杂度。

那么，我们可以使用哪个java功能/库来尽可能快地进行搜索呢？

与第一部分一致，这个问题只询问您将选择哪些预先存在/内置的Java代码来执行搜索。这里的“尽可能快的时间”应该让你想到O（1）中的解决方案，即恒定时间。然而，数据结构可能会为您打开/关闭大门。

Java中的一些搜索算法用于泛型，另一些用于其他类型，如数组。一些算法用于Maps，而另一些算法用于Lists，Sets，等等。第一部分的后续问题可能有助于回答这个问题。

也就是说，即使你知道DS，但当时想不出具体的方法名称，我也认为提到接口或至少一个相关的包并说可以在如果你被要求更具体，Java留档，因为这是它的首要目的。

我们可以将值存储在地图中，并在地图中搜索单词（但在如何确定地图中的键值对方面遇到了困难）。

鉴于措辞，我对他们问题的解释不是“你会使用哪种数据结构？”，而是“你会选择哪种预先存在的搜索算法？”在我看来，似乎是他们需要回答关于DS的问题。

也就是说，如果确实有人问你“你会使用哪种数据结构？”，然后一个映射仍然会对您不利，因为您实际上不需要将一个键映射到一个值。您只需要存储一个值（即单词）。因此，一个集合，特别是一个哈希集合，将是一个更好的选择，因为它也避免了重复，并且在这个过程中应该消耗更少的内存，因为它存储的是奇异值，而不是键/值对。

当然，这仍然是在我之前的假设下。如果说内存限制是一个问题，那么水平扩展到多个服务器等可能是必要的。

我如何理解这个问题的确切答案，以及最佳解决方案是什么？

鉴于缺乏他们给你的信息，他们可能想看看你是否会跟进问题。