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

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

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

你好！我們這里總共向您提供三種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)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

相關(guān)文章

Spring排序機(jī)制之接口與注解的使用方法
本文介紹了Spring中多種排序機(jī)制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了詳細(xì)示例,并指導(dǎo)如何選擇合適的排序機(jī)制來(lái)控制Bean的加載順序和優(yōu)先級(jí),感興趣的朋友一起看看吧
2025-02-02
Java開(kāi)發(fā)深入分析講解二叉樹(shù)的遞歸和非遞歸遍歷方法
樹(shù)是一種重要的非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，直觀地看，它是數(shù)據(jù)元素（在樹(shù)中稱(chēng)為結(jié)點(diǎn)）按分支關(guān)系組織起來(lái)的結(jié)構(gòu)，很象自然界中的樹(shù)那樣。樹(shù)結(jié)構(gòu)在客觀世界中廣泛存在，如人類(lèi)社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)都可用樹(shù)形象表示，本篇介紹二叉樹(shù)的遞歸與非遞歸遍歷的方法
2022-05-05
spring?boot集成WebSocket日志實(shí)時(shí)輸出到web頁(yè)面
這篇文章主要為大家介紹了spring?boot集成WebSocket日志實(shí)時(shí)輸出到web頁(yè)面展示的詳細(xì)操作，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步
2022-03-03
解決IDEA2020 創(chuàng)建maven項(xiàng)目沒(méi)有src/main/java目錄和webapp目錄問(wèn)題
這篇文章主要介紹了IDEA2020 創(chuàng)建maven項(xiàng)目沒(méi)有src/main/java目錄和webapp目錄問(wèn)題解決方法，本文通過(guò)圖文并茂的形式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
2020-10-10
Java常用類(lèi)之System類(lèi)的使用指南
System類(lèi)代表系統(tǒng)，系統(tǒng)級(jí)的很多屬性和控制方法都放置在該類(lèi)的內(nèi)部。該類(lèi)位于java.lang包。本文將通過(guò)示例為大家詳細(xì)講講System類(lèi)的使用，需要的可以參考一下
2022-07-07
SpringSecurity獲取當(dāng)前登錄用戶(hù)的信息的幾種方法實(shí)現(xiàn)
本文主要介紹了SpringSecurity中獲取當(dāng)前登錄用戶(hù)信息的多種方式,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2025-03-03
Java代理模式(Proxy)實(shí)現(xiàn)方法詳解
這篇文章主要介紹了Java代理模式(Proxy)實(shí)現(xiàn)的相關(guān)資料,代理模式是一種結(jié)構(gòu)型設(shè)計(jì)模式,通過(guò)引入代理對(duì)象來(lái)控制對(duì)目標(biāo)對(duì)象的訪問(wèn),代理模式的優(yōu)點(diǎn)包括職責(zé)清晰、擴(kuò)展性好、保護(hù)目標(biāo)對(duì)象和增強(qiáng)功能,文中通過(guò)代碼介紹的非常詳細(xì),需要的朋友可以參考下
2025-04-04
SpringBoot整合JWT的入門(mén)指南
JWT全稱(chēng)是json web token,它將用戶(hù)信息加密到 token 里,服務(wù)器不保存任何用戶(hù)信息,服務(wù)器通過(guò)使用保存的密鑰驗(yàn)證 token 的正確性,只要正確即通過(guò)驗(yàn)證,這篇文章主要給大家介紹了關(guān)于SpringBoot整合JWT的相關(guān)資料,需要的朋友可以參考下
2021-06-06
spring jpa ManyToMany原理及用法詳解
這篇文章主要介紹了spring jpa ManyToMany原理及用法詳解,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
2019-10-10
spring boot空屬性賦值問(wèn)題與aspect日志實(shí)現(xiàn)方法
這篇文章主要介紹了spring boot空屬性賦值問(wèn)題與aspect日志實(shí)現(xiàn)方法，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
2020-08-08