使用低輸入數的散列表有什麼問題？

使用低輸入數的散列表有什麼問題？在ADT中使用類似的屬性有更好的選擇嗎？使用低輸入數的散列表有什麼問題？

2013-12-14 Riptyde4

如果你給了我們關於你想要完成的事情的一些想法，回答這個問題可能會更容易。 –

什麼都不是，這是一個練習考試的問題，我不知道如何回答 – Riptyde4

浪費的空間也許？ – Mehrdad

即使散列表中的每個操作都是O（1），它在構造（例如構建存儲桶）方面仍將具有相當高的恆定成本。只有少數元素，許多其他ADT（例如LinkedList）在實踐中表現更好（即使使用那些數據結構具有O（n log n）或甚至O（複雜度））。

2013-12-14 01:26:02

在創建對象本身的空間複雜性或開銷方面？ – Riptyde4

從最廣泛的意義上講，在攤銷的恆定時間操作中，如果元素的數量很小，那麼分攤的時間就不能「回報」。也就是說，存在持續的運行時間開銷（例如，在構建存儲桶時）。 –

我不確定你正在談論哪些數據結構需要O（n log n）或O（n^2）。聽起來很像排序，但是這是怎麼回事？ – Dukeling

對於少量條目，vector傾向於工作得很好 - 關鍵的是，對象連續存儲，這往往與內存緩存效果最好 - 在現代系統中可以是非常有益的，它克服了蠻力搜索的成本，以及在擦除/排序等時移動物體。

如果您需要最小化對象的移動/複製，則（智能）指針或鏈接list的vector可能適合。

哈希表必須散列元素鍵，而std::map和std::find在vector等元素比較。例如，整數的高質量散列比僅比較值更昂貴，但是與大矩陣比較相比，大數值矩陣的一次性散列比其他矩陣的速度快得多 - 特別是如果它們僅僅不同在數據很好地進入比較。

2013-12-14 02:27:11

回答