如何使用java实现Open Addressing

你好！ 我们这里总共向您提供三种open addression的方法，分别为linear probing、quadratic probing和double hashing。

Linear probing是计算机程序解决散列表冲突时所采取的一种策略。散列表这种数据结构用于保存键值对，并且能通过给出的键来查找表中对应的值。Linear probing这种策略是在1954年由Gene Amdahl, Elaine M. McGraw,和 Arthur Samuel 所发明，并且最早于1963年由Donald Knuth对其进行分析。

public static void main(String ] args) {

int N = 15;

int ] A = new int 

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 

for (int i = 0; i A.length; i++) {

 System.out.println(A i]);

Quadratic probing是计算机程序解决散列表冲突时所采取的另一种策略，用于解决散列表中的冲突。Quadratic probing通过获取原始哈希索引并将任意二次多项式的连续值相加，直到找到一个空槽来进行操作。

public static void main(String ] args) {

int N = 15;

int ] A = new int 

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 

for (int i = 0; i A.length; i++) {

 System.out.println(A i]);

Double hashing是计算机程序解决散列表冲突时所采取的另一种策略，与散列表中的开放寻址结合使用，通过使用密钥的辅助哈希作为冲突发生时的偏移来解决哈希冲突。具有open addressing的double hashing是表上的经典数据结构。

public static void main(String ] args) {

int N = 15;

int ] A = new int 

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 

for (int i = 0; i A.length; i++) {

 System.out.println(A i]);

2019-06-17

原创文章，转载请注明： 转载自并发编程网 ifeve.com本文链接地址: 如何使用java实现Open Addressing

原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/60286.html