详解怎样使用java实现Open Addressing
weixin_43146543 人气:0这篇文章主要介绍了详解如何使用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]); } }
加载全部内容