-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHashMap.java
More file actions
125 lines (96 loc) · 3.1 KB
/
HashMap.java
File metadata and controls
125 lines (96 loc) · 3.1 KB
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
package DataStructures;
import java.util.LinkedList;
public class HashMap<K, V> {
private LinkedList<Entry<K, V>>[] table; //HashMap with chaining. Array with LinkedLists holding all collisions
private int numKeys; //Size of HashMap
private static int CAPACITY = 101; //A prime number!
private static double LOAD_THRESHOLD = 3.0; //Double size of HashMap when over threshold
public HashMap() {
table = new LinkedList[CAPACITY];
}
public V get(K key){
int index = key.hashCode() % numKeys;
index = index < 0 ? index + table.length : index;
if(table[index] == null){
return null;
}
for(Entry<K, V> entry : table[index]){
if(entry.getKey().equals(key)){
return entry.getValue();
}
}
return null;
}
public V put(K key, V value){
int index = key.hashCode() % table.length;
index = index < 0 ? index + table.length : index;
if(table[index] == null){
table[index] = new LinkedList<>();
}
for(Entry<K, V> entry : table[index]){
if(entry.getKey().equals(key)){
V oldValue = entry.setValue(value);
return oldValue;
}
}
table[index].addFirst(new Entry(key, value));
numKeys++;
if(numKeys > (LOAD_THRESHOLD * table.length)){
rehash();
}
return null;
}
public V remove(K key){
int index = key.hashCode() % table.length;
index = index < 0 ? index + table.length : index;
if(table[index] == null){
return null;
}
for(Entry<K, V> entry : table[index]){
if(entry.getKey().equals(key)){
V oldValue = entry.getValue();
table[index].remove(key);
if(table[index].size() == 0){
table[index] = null;
}
return oldValue;
}
}
return null;
}
private void rehash(){
LinkedList<Entry<K, V>>[] newTable = new LinkedList[CAPACITY * 2];
CAPACITY = CAPACITY * 2;
for(LinkedList<Entry<K, V>> chain : table){
if(chain == null) continue;
for(Entry<K, V> entry : chain) {
int index = entry.getKey().hashCode() % newTable.length;
index = index < 0 ? index + newTable.length : index;
if(newTable[index] == null){
newTable[index] = new LinkedList<>();
}
newTable[index].addFirst(entry);
}
}
table = newTable;
}
public class Entry<K, V> {
private K key;
private V value;
public Entry(K key, V value){
this.key = key;
this.value = value;
}
public K getKey(){
return this.key;
}
public V getValue(){
return this.value;
}
public V setValue(V value){
V oldValue = value;
this.value = value;
return oldValue;
}
}
}