java - 搜索性能调整

Question

我是DS和Algorithms的新手，最近在一次工作面试中，有人问我一个关于性能调整和代码的问题。我们有一个包含数十亿个条目的数据结构，我们需要在该数据结构中搜索一个特定的单词。那么，我们可以使用哪个Java功能/库在最快的时间内进行搜索？

当场，我想不出确切的答案，于是我写道：


我们可以将值存储在地图中并在地图中搜索单词（但是在如何确定地图中的键/值对时遇到了麻烦）。


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

Answer 1

阅读问题并在注释中得到澄清后，我认为对我来说显而易见的是：您需要提出后续问题。

我将尝试分解它并提供希望对您有帮助的评论，因为我也知道“当下”会是什么样子，以及在您最不需要它们时神经会如何刺伤您。


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


我认为这里有一个很好的后续问题：

问：正在使用什么特定的数据结构来包含所有这些数据？

我会一直等到他们给我一个真实的名字，然后解释为什么无法命名Java算法/库。就您所知，数据结构可能是磁盘上文件的String[]，Set<String>甚至是奇特的名称（如果它们试图让您失望的话）。他们还可以澄清并说DS与您无关，您可以选择自己认为最佳的DS。

该用语还暗示他们实现了该结构，并且该结构已经填充在系统中，该系统可能具有足够的内存来容纳所有结构。要求确认确实如此，可以为您提供有用的信息。

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

鉴于建议的措辞以及我们没有其他澄清的事实，出于回答的目的，我将假设我的假设确实是正确的。

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

另外，如果您被要求设计搜索算法，那么了解DS是先决条件，而不知道这样做可能使这项任务变得不可能。例如，即使您要处理数组还是二进制搜索树，二进制搜索算法的实现看起来都会有很大不同，即使两者都提供O（lg n）时间复杂度。


  那么，我们可以使用哪个Java功能/库在最快的时间内进行搜索？


与第1部分一致，此问题仅询问您选择要为您执行搜索的现有/内置Java代码。这里的“可能的最快时间”应该使您考虑O（1）中的解决方案，即恒定时间。但是，数据结构可能会为您打开/关闭门。

Java中的某些搜索算法适用于泛型，而其他算法则适用于其他类型，例如数组。一些算法在Map上运行，而其他算法在List，Set上运行，依此类推。第一部分中的后续问题可以帮助回答这个问题。

就是说，即使您知道DS，但当时却无法想到一个特定的方法名称，我也认为提及该接口或至少一个相关的软件包并说进一步的细节可以合理地认为是合理的。如果您被迫寻求更多的细节，请在Java文档中进行检查，因为这首先就是要解决的。


  我们可以将值存储在地图中并在地图中搜索单词（但是在如何确定地图中的键/值对时遇到了麻烦）。


给定措词，我对他们的问题的解释不是“您将使用哪种数据结构？”，而是“您将选择哪种预先存在的搜索算法？”。在我看来，正是他们需要回答有关DS的问题。

也就是说，如果确实询问您“您将使用哪种数据结构？”，那么Map仍然会对您不利，因为您实际上不需要将键映射到值。您只需要存储一个值（即单词）。因此，Set，尤其是HashSet，将是一个更好的选择，因为它还避免重复，并且由于它存储的是奇异值而不是键/值对，因此在该过程中应该消耗更少的内存。

当然，这仍然是我之前所做的假设。如果说内存限制是一个问题，则可能有必要将其水平扩展到多个服务器等等。


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


考虑到他们给您的信息不足，他们很可能想看看您是否会跟进问题。