详解如何使用java实现Open Addressing

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

linear probing

linear probing是计算机程序解决散列表冲突时所采取的一种策略。散列表这种数据结构用于保存键值对，并且能通过给出的键来查找表中对应的值。linear probing这种策略是在1954年由gene amdahl, elaine m. mcgraw,和 arthur samuel 所发明，并且最早于1963年由donald knuth对其进行分析。

• 假设a是哈希表的一个容量n为15的数组；
  
• 将keys（5、9、12、24、31、40、47、53、62、71）使用linear probing按照顺序依次插入到数组中。
  

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通过获取原始哈希索引并将任意二次多项式的连续值相加，直到找到一个空槽来进行操作。

• 假设a是哈希表的一个容量n为15的数组；
  
• 将keys（5、9、12、24、31、40、47、53、62、71）使用quadratic probing按照顺序依次插入到数组中。

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

• 假设a是哈希表的一个容量n为15的数组；
• 将keys（5、9、12、24、31、40、47、53、62、71）使用double hashing（我们假设h'(k)为13 - (k mod 13)）按照顺序依次插入到数组中。

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实现open addressing的文章就介绍到这了,更多相关java实现open addressing内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！