作者|weixin_43146543|CSDN
如何使用java實現Open Addressing你好! 我們這裡總共向您提供三種open addression的方法,分別為linear probing、quadratic probing和double hashing。
Linear ProbingLinear probing是計算機程式解決散列表衝突時所採取的一種策略。散列表這種資料結構用於儲存鍵值對,並且能透過給出的鍵來查詢表中對應的值。Linear probing這種策略是在1954年由Gene Amdahl, Elaine M. McGraw,和 Arthur Samuel 所發明,並且最早於1963年由Donald Knuth對其進行分析。
假設A是雜湊表的一個容量N為15的陣列;將Keys(5、9、12、24、31、40、47、53、62、71)使用linear probing按照順序依次插入到陣列中。public static void main(String[] args) { int N = 15; int[] A = new int [N]; int[] Keys = {5, 9, 12, 24, 31, 40, 47, 53, 62, 71}; for (int i = 0; i < Keys.length; i++) { int j = 0; int Position = Keys[i] % N; while (A[Position] != 0) { j = j + 1; Position = Keys[i] % N + j; } A[Position] = Keys[i]; } for (int i = 0; i < A.length; i++) { System.out.println(A[i]); } }
Quadratic Probing
Quadratic probing是計算機程式解決散列表衝突時所採取的另一種策略,用於解決散列表中的衝突。Quadratic probing透過獲取原始雜湊索引並將任意二次多項式的連續值相加,直到找到一個空槽來進行操作。
假設A是雜湊表的一個容量N為15的陣列;將Keys(5、9、12、24、31、40、47、53、62、71)使用quadratic probing按照順序依次插入到陣列中。public static void main(String[] args) { int N = 15; int[] A = new int [N]; int[] Keys = {5, 9, 12, 24, 31, 40, 47, 53, 62, 71}; for (int i = 0; i < Keys.length; i++) { int j = 0; int Position = Keys[i] % N; while (A[Position] != 0) { j = j + 1; Position = (Keys[i] % N + j*j) % N; } A[Position] = Keys[i]; } for (int i = 0; i < A.length; i++) { System.out.println(A[i]); } }
Double HashingDouble hashing是計算機程式解決散列表衝突時所採取的另一種策略,與散列表中的開放定址結合使用,透過使用金鑰的輔助雜湊作為衝突發生時的偏移來解決雜湊衝突。具有open addressing的double hashing是表上的經典資料結構。
假設A是雜湊表的一個容量N為15的陣列;將Keys(5、9、12、24、31、40、47、53、62、71)使用double hashing(我們假設h’(k)為13 - (k mod 13))按照順序依次插入到陣列中。public static void main(String[] args) { int N = 15; int[] A = new int [N]; int[] Keys = {5, 9, 12, 24, 31, 40, 47, 53, 62, 71}; for (int i = 0; i < Keys.length; i++) { int j = 0; int Position = (Keys[i] % N + (13 - (Keys[i] % 13)) * j) % N; while (A[Position] != 0) { j = j + 1; Position = (Keys[i] % N + (13 - (Keys[i] % 13)) * j) % N; } A[Position] = Keys[i]; } for (int i = 0; i < A.length; i++) { System.out.println(A[i]); } }
最新評論