-
Notifications
You must be signed in to change notification settings - Fork 4.3k
/
HashTableLinearProbing.java
44 lines (36 loc) · 1.18 KB
/
HashTableLinearProbing.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
/**
* An implementation of a hash-table using open addressing with linear probing as a collision
* resolution method.
*
* @author William Fiset, william.alexandre.fiset@gmail.com
*/
package com.williamfiset.algorithms.datastructures.hashtable;
public class HashTableLinearProbing<K, V> extends HashTableOpenAddressingBase<K, V> {
// This is the linear constant used in the linear probing, it can be
// any positive number. The table capacity will be adjusted so that
// the GCD(capacity, LINEAR_CONSTANT) = 1 so that all buckets can be probed.
private static final int LINEAR_CONSTANT = 17;
public HashTableLinearProbing() {
super();
}
public HashTableLinearProbing(int capacity) {
super(capacity);
}
public HashTableLinearProbing(int capacity, double loadFactor) {
super(capacity, loadFactor);
}
@Override
protected void setupProbing(K key) {}
@Override
protected int probe(int x) {
return LINEAR_CONSTANT * x;
}
// Adjust the capacity so that the linear constant and
// the table capacity are relatively prime.
@Override
protected void adjustCapacity() {
while (gcd(LINEAR_CONSTANT, capacity) != 1) {
capacity++;
}
}
}