-
Notifications
You must be signed in to change notification settings - Fork 4.3k
/
HashTableQuadraticProbing.java
60 lines (51 loc) · 1.76 KB
/
HashTableQuadraticProbing.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
* An implementation of a hash-table using open addressing with quadratic probing as a collision
* resolution method.
*
* <p>In this implementation we are using the following probing function: H(k, x) = h(k) + f(x) mod
* 2^n
*
* <p>Where h(k) is the hash for the given key, f(x) = (x + x^2) / 2 and n is a natural number. We
* are using this probing function because it is guaranteed to find an empty cell (i.e it generates
* all the numbers in the range [0, 2^n) without repetition for the first 2^n numbers).
*
* @author William Fiset, william.alexandre.fiset@gmail.com
*/
package com.williamfiset.algorithms.datastructures.hashtable;
public class HashTableQuadraticProbing<K, V> extends HashTableOpenAddressingBase<K, V> {
public HashTableQuadraticProbing() {
super();
}
public HashTableQuadraticProbing(int capacity) {
super(capacity);
}
// Designated constructor
public HashTableQuadraticProbing(int capacity, double loadFactor) {
super(capacity, loadFactor);
}
// Given a number this method finds the next
// power of two above this value.
private static int nextPowerOfTwo(int n) {
return Integer.highestOneBit(n) << 1;
}
// No setup required for quadratic probing.
@Override
protected void setupProbing(K key) {}
@Override
protected int probe(int x) {
// Quadratic probing function (x^2+x)/2
return (x * x + x) >> 1;
}
// Increase the capacity of the hashtable to the next power of two.
@Override
protected void increaseCapacity() {
capacity = nextPowerOfTwo(capacity);
}
// Adjust the capacity of the hashtable to be a power of two.
@Override
protected void adjustCapacity() {
int pow2 = Integer.highestOneBit(capacity);
if (capacity == pow2) return;
increaseCapacity();
}
}