多重選擇雜湊
- 多重選擇雜湊之所以得名,是因為它採用了多個雜湊函式的實現。
- 從高層次來看,當有多個雜湊函式時,每個專案都會對映到多個桶,因此演算法設計者可以自由選擇專案駐留在其中的桶。
- 事實證明,這種自由允許演算法獲得比使用單個雜湊函式獲得的分配更平衡的分配。
- 我們將介紹主要的演算法思想和用於證明這些演算法產生的分配界限的主要數學工具。
- 我們將看到,該分析足夠強大,可以承受基本模型的變化,在我們看來,這解釋了這些演算法在實際應用中的有效性。
多重選擇雜湊演算法透過引用球盒模型的例子來解釋。
- 一個關於負載均衡過程推理的常用框架是“球”和“盒”框架,其中需求(鍵、程序、檔案等)由“球”表示,資源的供應(表槽、伺服器、儲存單元等)由“盒”表示。
- 在這種情況下,m 個球透過實現某些分配規則依次扔進 n 個盒中。
- 目標是瞭解在過程完成後球到盒的分配情況,通常是對負載(=球的數量)在負載最大的盒中進行約束。
- 根據此模型,球的分配是透過應用一個或多個雜湊函式來執行的。
- 這些雜湊函式負責將球的唯一 ID(通常在模型中是隱式的)對映到盒的集合,通常編號為 1...n。
- 實現一個將盒對映到球的雜湊函式,而不是簡單地隨機抽取一個盒,在常見情況下很有用,在該常見情況下,在以後的某個時間需要從其 ID 恢復球的位置。
廣告