-
Notifications
You must be signed in to change notification settings - Fork 0
/
SeparateChainingHashST.java
73 lines (59 loc) · 1.98 KB
/
SeparateChainingHashST.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
61
62
63
64
65
66
67
68
69
70
71
72
73
public class SeparateChainingHashST<Key, Value> {
private static final int INIT_CAPACITY = 4;
private int n;
private int m;
private SequentialSearchST<Key, Value>[] st;
public SeparateChainingHashST() {
this(INIT_CAPACITY);
}
public SeparateChainingHashST(int m) {
this.m = m;
st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[m];
for (int i = 0; i < m; i++)
st[i] = new SequentialSearchST<Key, Value>();
}
private void resize(int chains) {
SeparateChainingHashST<Key, Value> temp = new SeparateChainingHashST<Key, Value>(chains);
for (int i = 0; i < m; i++) {
for (Key key : st[i].keys()) {
temp.put(key, st[i].get(key));
}
}
this.m = temp.m;
this.n = temp.n;
this.st = temp.st;
}
private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % m;
}
public int size() {
return n;
}
public boolean contains(Key key) {
if (key == null) throw new IllegalArgumentException("argument to contains() is null");
return get(key) != null;
}
public Value get(Key key) {
if (key == null) throw new IllegalArgumentException("argument to get() is null");
int i = hash(key);
return st[i].get(key);
}
public void put(Key key, Value val) {
if (key == null) throw new IllegalArgumentException("first argument to put() is null");
if (val == null) {
delete(key);
return;
}
if (n >= 10*m) resize(2*m);
int i = hash(key);
if (!st[i].contains(key)) n++;
st[i].put(key, val);
}
public void delete(Key key) {
if (key == null) throw new IllegalArgumentException("argument to delete() is null");
int i = hash(key);
if (st[i].contains(key)) n--;
st[i].delete(key);
if (m > INIT_CAPACITY && n <= 2*m) resize(m/2);
}
}