利用java怎么实现一个OpenAddressing功能-创新互联

利用java怎么实现一个Open Addressing功能?针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

十载专注成都网站制作,企业网站建设,个人网站制作服务,为大家分享网站制作知识、方案,网站设计流程、步骤,成功服务上千家企业。为您提供网站建设,网站制作,网页设计及定制高端网站建设服务,专注于企业网站建设,高端网页制作,对成都发电机租赁等多个方面,拥有多年建站经验。

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怎么实现一个OpenAddressing功能-创新互联
文章出自:http://scyanting.com/article/eidjo.html