哈希表或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？

回答

相關問題