-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathHashMap.java
More file actions
155 lines (119 loc) · 3.99 KB
/
HashMap.java
File metadata and controls
155 lines (119 loc) · 3.99 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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
package Implementations;
import java.util.Iterator;
public class HashMap<K, V> implements Map<K, V>{
private LinkedList<KeyValuePair<K, V>>[] array = new LinkedList[3];
private int elementsCount = 0;
public HashMap(){
for(int i = 0; i < array.length; i++)
array[i] = new LinkedList<>();
setArraySize(3);
}
private void setArraySize(int size){
LinkedList<KeyValuePair<K, V>> newArray[] = new LinkedList[size];
for(int i = 0; i < size; i++)
newArray[i] = new LinkedList<>();
for(LinkedList<KeyValuePair<K, V>> bucket : array)
for(KeyValuePair<K, V> pair : bucket)
newArray[Math.abs(pair.key.hashCode()) % size].add(pair);
array = newArray;
}
@Override
public void set(K key, V value){
KeyValuePair<K, V> pair = new KeyValuePair<>(key, value);
int bucket = getBucket(key);
int listIndex = array[bucket].getIndex(pair);
if(listIndex == -1) {
array[bucket].add(pair);
elementsCount++;
}
else
array[bucket].get(listIndex).value = pair.value;
if(elementsCount > array.length)
setArraySize(array.length + array.length / 3);
}
@Override
public V get(K key){
KeyValuePair<K, V> pair = new KeyValuePair<>(key, null);
int bucket = getBucket(key);
int listIndex = array[bucket].getIndex(pair);
if(listIndex == -1)
throw new RuntimeException("Key not found: " + key);
return array[bucket].get(listIndex).value;
}
@Override
public void remove(K key){
KeyValuePair<K, V> pair = new KeyValuePair<>(key, null);
int bucket = getBucket(key);
int listIndex = array[bucket].getIndex(pair);
if(listIndex == -1)
throw new RuntimeException("Key not found: " + key);
array[bucket].remove(listIndex);
elementsCount--;
if(elementsCount < array.length - array.length / 3 && elementsCount > 3)
setArraySize(elementsCount);
}
@Override
public boolean contains(K key){
KeyValuePair<K, V> pair = new KeyValuePair<>(key, null);
return array[getBucket(key)].getIndex(pair) != -1;
}
@Override
public int size(){
return elementsCount;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
for(int i = 0; i < array.length; i++) {
sb.append(array[i].toString());
if (i < array.length - 1)
sb.append(", ");
}
sb.append("]");
return sb.toString();
}
private int getBucket(K key){
return Math.abs(key.hashCode()) % array.length;
}
@Override
public Iterator<K> keys() {
return new Iterator<K>() {
int currentItem = 0;
int currentIndex = 0;
Iterator<KeyValuePair<K, V>> currentInterator = null;
@Override
public boolean hasNext() {
return currentItem < elementsCount;
}
@Override
public K next() {
currentItem++;
if(currentInterator != null && currentInterator.hasNext())
return currentInterator.next().key;
while(currentIndex < array.length){
currentInterator = array[currentIndex].iterator();
currentIndex++;
if(currentInterator.hasNext())
return currentInterator.next().key;
}
return null;
}
};
}
}
class KeyValuePair<K, V>{
public K key;
public V value;
public KeyValuePair(K key, V value){
this.key = key;
this.value = value;
}
@Override
public boolean equals(Object obj) {
return key.equals(((KeyValuePair<K, V>) obj).key);
}
@Override
public String toString() {
return "{"+ key + ":" + value + "}";
}
}