我在最近的一次采访中被问到这个问题

Question

我被要求远离HashMap或任何类型的Hashing.

问题是这样的 -

假设您有最多20位小数的PRODUCT ID以及产品描述.如果不使用地图或任何类型的散列函数,那么存储/检索这些产品ID及其描述的最佳/最有效方法是什么？

为什么在这种情况下使用Maps是一个坏主意？

您将解决方案出售给亚马逊会有什么变化？

Answer 1

插入/删除/查找操作交错时,可以使用映射.每个操作都在O(log n)中摊销.

在你的例子中,你只是在做搜索操作.您可能会认为任何数据库更新(插入/删除产品)都不会发生这么多时间.因此,面试官可能希望您获得查找操作的最佳数据结构.

在这种情况下,我只能看到其他答案中已提出的一些内容:

• 排序数组(进行二进制搜索)
• Hasmap
• 特里

使用trie,如果产品ID不共享公共前缀,则很有可能仅查看前缀的第一个字符(或仅显示第一个字符)来查找产品描述.例如,让我们拿出125个产品的产品ID列表:

• "1"
• "2"
• "3"
  ......
• "123"
• "124"
• "1234567"

假设您正在寻找在您的trie中标题为"1234567"的产品ID,只查看第一个字母:"1"然后"2"然后"3"然后"4"将导致良好的产品描述.因为没有其他可能性,所以无需阅读剩余的产品ID.将产品ID长度视为n,您的查找将在O(n)中.但正如上面解释的那样,可以更快地检索产品描述.由于产品ID的大小有限(20个字符),因此特里高度将限制在20个等级.这实际上意味着你可以认为查找操作永远不会超过一个恒定的时间,因为你的搜索永远不会超过trie height => O(1).虽然任何BST查找最好分摊O(log N),但N是树中的项目数.

虽然散列图可能会导致查找速度变慢,因为您需要使用散列函数计算索引,该散列函数可能实现读取整个产品ID长度.加上在与其他产品ID发生碰撞时浏览列表.

对已排序的数组执行二进制搜索,并且查找操作中的性能取决于数据库中的项目数.

Answer 2

一个B树在我看来.这仍然算作地图吗？

主要是因为您可以在内存中同时加载许多项目.在内存中搜索这些项目非常快.