你好！ 我們這里總共向您提供三種open addression的方法，分別為linear probing、quadratic probing和double hashing。

Linear Probing

Linear probing是計(jì)算機(jī)程序解決散列表沖突時(shí)所采取的一種策略。散列表這種數(shù)據(jù)結(jié)構(gòu)用于保存鍵值對(duì)，并且能通過(guò)給出的鍵來(lái)查找表中對(duì)應(yīng)的值。Linear probing這種策略是在1954年由Gene Amdahl, Elaine M. McGraw,和 Arthur Samuel 所發(fā)明，并且最早于1963年由Donald Knuth對(duì)其進(jìn)行分析。

假設(shè)A是哈希表的一個(gè)容量N為15的數(shù)組； 將Keys（5、9、12、24、31、40、47、53、62、71）使用linear probing按照順序依次插入到數(shù)組中。

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是計(jì)算機(jī)程序解決散列表沖突時(shí)所采取的另一種策略，用于解決散列表中的沖突。Quadratic probing通過(guò)獲取原始哈希索引并將任意二次多項(xiàng)式的連續(xù)值相加，直到找到一個(gè)空槽來(lái)進(jìn)行操作。

假設(shè)A是哈希表的一個(gè)容量N為15的數(shù)組； 將Keys（5、9、12、24、31、40、47、53、62、71）使用quadratic probing按照順序依次插入到數(shù)組中。

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 Hashing

Double hashing是計(jì)算機(jī)程序解決散列表沖突時(shí)所采取的另一種策略，與散列表中的開(kāi)放尋址結(jié)合使用，通過(guò)使用密鑰的輔助哈希作為沖突發(fā)生時(shí)的偏移來(lái)解決哈希沖突。具有open addressing的double hashing是表上的經(jīng)典數(shù)據(jù)結(jié)構(gòu)。

假設(shè)A是哈希表的一個(gè)容量N為15的數(shù)組； 將Keys（5、9、12、24、31、40、47、53、62、71）使用double hashing（我們假設(shè)h’(k)為13 - (k mod 13)）按照順序依次插入到數(shù)組中。

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]); } }

到此這篇關(guān)于詳解如何使用java實(shí)現(xiàn)Open Addressing的文章就介紹到這了,更多相關(guān)java實(shí)現(xiàn)Open Addressing內(nèi)容請(qǐng)搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)！