詳解如何使用java實現(xiàn)Open Addressing

更新時間：2020年12月17日 11:51:35 作者：weixin_43146543

這篇文章主要介紹了詳解如何使用java實現(xiàn)Open Addressing，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧

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

Linear Probing

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

假設A是哈希表的一個容量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是計算機程序解決散列表沖突時所采取的另一種策略，用于解決散列表中的沖突。Quadratic probing通過獲取原始哈希索引并將任意二次多項式的連續(xù)值相加，直到找到一個空槽來進行操作。

假設A是哈希表的一個容量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是計算機程序解決散列表沖突時所采取的另一種策略，與散列表中的開放尋址結合使用，通過使用密鑰的輔助哈希作為沖突發(fā)生時的偏移來解決哈希沖突。具有open addressing的double hashing是表上的經(jīng)典數(shù)據(jù)結構。

假設A是哈希表的一個容量N為15的數(shù)組；
將Keys（5、9、12、24、31、40、47、53、62、71）使用double hashing（我們假設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]);
 } 
 }

到此這篇關于詳解如何使用java實現(xiàn)Open Addressing的文章就介紹到這了,更多相關java實現(xiàn)Open Addressing內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: