哈希表或BST？

目前我有一个问题，我想弄清楚，但不知道我的答案是否正确。哈希表或BST？

您有100万条记录。在这些记录中，您经常需要通过两个标准进行搜索：员工ID和薪水（但不能同时进行）。您有以下限制：

每个记录是非常大的，因为你只能保持这个数据的一个副本。

您的程序需要相当快。只需扫描每个搜索的所有项目就会太慢。

你会用什么数据结构？

我的回答是？

我会使用Hash表，因为最坏的情况下，时间是O（1000000）= O（1）

你将如何检索记录，当你通过ID搜索？

当您按工资搜索时，您如何检索记录？

来源

2016-12-14 Bassam Metwally

你会不会需要按薪水范围搜索？（例如，“向我显示所有薪水介于$ 20,000和$ 25,000之间”或类似的内容？）如果是这样，您需要扫描整个哈希表（O（N））才能执行此操作，因为仅哈希表的O（1）查找如果您知道您正在寻找的确切关键值，请致电... –

“使用散列表”只是答案的开始。你将如何在只有一个数据副本的情况下搜索两个密钥？我认为这就是要探究你的知识的问题。树和散列表之间的选择是次要的，你可以同时使用两者。想想失去的细节。您是否需要通过一系列薪酬进行搜索 - 这是现实的 - 还是一个特定的美元价值 - 不是很有用？差异很重要。 – Gene

@JeremyFriesner很好的ID我知道确切的位置是我先排序的ID然后使用哈希？但对于薪水你有一个点.... –

我期望很多基于工资的哈希表的碰撞问题，但是一个ID可以使用一点密码理论很容易地工作，没有碰撞。这似乎很奇怪，想搜索工资，而不是排序或得到一些范围，这可能会更容易地执行BST。

但它的缺点是，如果你想通过两个独立的属性搜索，你将不得不维护两个结构。幸运的是指针存在，所以你不必保留多个副本。个人而言，我会保持ID的哈希表来引用，那么薪金引用的BST，但如果我限制在一个数据类型我不得不做了BST像这样的节点：

Node { 
     int id; 
     Node idLessThan; 
     Node idGreaterThan; 

     int salary; 
     Node salaryLessThan; 
     Node salaryGreaterThan; 

     Data fileInfo; 
    }

在相同的节点集上创建基本上两个BST。

来源

2016-12-14 05:51:16 kcazllerraf

我在评论思考同样的事情。但是，如果工资是独一无二的呢？散列表会更好吗？ –

如果你只想按薪水搜索，而不按薪水排序，那么在内存和访问时间上都会更高效。我可以想到的任何情况下，你只能通过确切的薪水搜索是非常有意思的。 – kcazllerraf

所以，如果我只搜索它将是有效的使用BST。我明白，但我是一个考验我们理解概念的问题。 –

哈希表或BST？

回答

相关问题