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