使用二次探測實現哈希表的原因

最近我一直在學習哈希表。有幾個碰撞解決方案的例子，其中一個是二次探測。爲什麼有人會使用二次探測？他知道散列表總是少於一半嗎？如果是的話，他爲什麼要用這麼大的桌子開始呢？使用二次探測實現哈希表的原因

你似乎是要求兩種完全不同的。，正交問題 –

我明白你的意思了，我把這個問題改寫得更清楚 – user2278279

爲什麼有人會使用二次探測？

假設我們需要一些衝突分解算法，

二次探測可以在一個封閉的哈希表更有效的算法，因爲它更好地避免了可與線性探測發生聚類問題，儘管它不是免疫的。

的二次鏈接（或其他形式的）的優點是

簡單邏輯存儲管理（沒有動態分配）

更快的插入（由於si mpler存儲）

一般

減少存儲需求，他是否知道哈希表總是會比全少了一半？

不一定;它取決於所使用的調整策略，如果有的話。

考慮你對QP的學習主要是教育。根據我的經驗，實際的哈希表實現不經常使用open addressing,。

2013-04-13 20:47:32

噢，好吧，你可以從任何大小開始，每當它滿足調整大小時，就可以調整大小。浪費空間嗎？改變散列函數不是更好嗎？ – user2278279

@ user2278279-這不會浪費太多空間。通常，你的空間不會超過你需要的4倍，因爲任何時候你有2x空間你的桌子大小加倍。這是一個相當標準的實現。 – templatetypedef

現在我明白了。這取決於你如何實現散列表，如果你使用了一個指針數組，那麼相比於散列函數的簡單性，指針的兩倍並不是那麼糟糕，但是如果你使用一個大對象數組，那麼你將會浪費空間。 – user2278279

二次方rehash是避免線性散列聚類問題的一種非常簡單快速的方法。它通常只在表格大小爲素數時使用（這可能也適用於其他原因）。

爲了避免擔心「表格半滿」，在某些點切換到線性探頭是最簡單的。（你可以把閾值測試用於這種切換內部通常如果（指數> =大小）{索引 - =大小;}塊，以避免任何性能損失

2013-04-14 01:47:53

回答