1 import java.util.LinkedList;
2
3 public class MyHashMap<K, V> implements MyMap<K, V> {
4
5 private final static int DEFAULT_INITIAL_CAPACITY = 4;
6
7
8 private final static int MAXIMUM_CAPACITY = 1 << 30;
9
10
11 private int capacity;
12
13
14 private final static float DEFAULT_MAX_LOAD_FACTOR = 0.75f;
15
16
17 private float loadFactorThreshold;
18
19
20 private int size = 0;
21
22
23 LinkedList<MyMap.Entry<K,V>>[] table;
24
25
26 public MyHashMap() {
27 this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR);
28 }
29
30
32 public MyHashMap(int initialCapacity) {
33 this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR);
34 }
35
36
38 public MyHashMap(int initialCapacity, float loadFactorThreshold) {
39 if (initialCapacity > MAXIMUM_CAPACITY)
40 this.capacity = MAXIMUM_CAPACITY;
41 else
42 this.capacity = trimToPowerOf2(initialCapacity);
43
44 this.loadFactorThreshold = loadFactorThreshold;
45 table = new LinkedList[capacity];
46 }
47
48 @Override
49 public void clear() {
50 size = 0;
51 removeEntries();
52 }
53
54 @Override
55 public boolean containsKey(K key) {
56 if (get(key) != null)
57 return true;
58 else
59 return false;
60 }
61
62 @Override
63 public boolean containsValue(V value) {
64 for (int i = 0; i < capacity; i++) {
65 if (table[i] != null) {
66 LinkedList<Entry<K, V>> bucket = table[i];
67 for (Entry<K, V> entry: bucket)
68 if (entry.getValue().equals(value))
69 return true;
70 }
71 }
72
73 return false;
74 }
75
76 @Override
77 public java.util.Set<MyMap.Entry<K,V>> entrySet() {
78 java.util.Set<MyMap.Entry<K, V>> set =
79 new java.util.HashSet<>();
80
81 for (int i = 0; i < capacity; i++) {
82 if (table[i] != null) {
83 LinkedList<Entry<K, V>> bucket = table[i];
84 for (Entry<K, V> entry: bucket)
85 set.add(entry);
86 }
87 }
88
89 return set;
90 }
91
92 @Override
93 public V get(K key) {
94 int bucketIndex = hash(key.hashCode());
95 if (table[bucketIndex] != null) {
96 LinkedList<Entry<K, V>> bucket = table[bucketIndex];
97 for (Entry<K, V> entry: bucket)
98 if (entry.getKey().equals(key))
99 return entry.getValue();
100 }
101
102 return null;
103 }
104
105 @Override
106 public boolean isEmpty() {
107 return size == 0;
108 }
109
110 @Override
111 public java.util.Set<K> keySet() {
112 java.util.Set<K> set = new java.util.HashSet<>();
113
114 for (int i = 0; i < capacity; i++) {
115 if (table[i] != null) {
116 LinkedList<Entry<K, V>> bucket = table[i];
117 for (Entry<K, V> entry: bucket)
118 set.add(entry.getKey());
119 }
120 }
121
122 return set;
123 }
124
125 @Override
126 public V put(K key, V value) {
127 if (get(key) != null) {
128 int bucketIndex = hash(key.hashCode());
129 LinkedList<Entry<K, V>> bucket = table[bucketIndex];
130 for (Entry<K, V> entry: bucket)
131 if (entry.getKey().equals(key)) {
132 V oldValue = entry.getValue();
133
134 entry.value = value;
135
136 return oldValue;
137 }
138 }
139
140
141 if (size >= capacity * loadFactorThreshold) {
142 if (capacity == MAXIMUM_CAPACITY)
143 throw new RuntimeException("Exceeding maximum capacity");
144
145 rehash();
146 }
147
148 int bucketIndex = hash(key.hashCode());
149
150
151 if (table[bucketIndex] == null) {
152 table[bucketIndex] = new LinkedList<Entry<K, V>>();
153 }
154
155
156 table[bucketIndex].add(new MyMap.Entry<K, V>(key, value));
157
158 size++;
159
160 return value;
161 }
162
163 @Override
164 public void remove(K key) {
165 int bucketIndex = hash(key.hashCode());
166
167
168 if (table[bucketIndex] != null) {
169 LinkedList<Entry<K, V>> bucket = table[bucketIndex];
170 for (Entry<K, V> entry: bucket)
171 if (entry.getKey().equals(key)) {
172 bucket.remove(entry);
173 size--;
174 break;
175 }
176 }
177 }
178
179 @Override
180 public int size() {
181 return size;
182 }
183
184 @Override
185 public java.util.Set<V> values() {
186 java.util.Set<V> set = new java.util.HashSet<>();
187
188 for (int i = 0; i < capacity; i++) {
189 if (table[i] != null) {
190 LinkedList<Entry<K, V>> bucket = table[i];
191 for (Entry<K, V> entry: bucket)
192 set.add(entry.getValue());
193 }
194 }
195
196 return set;
197 }
198
199
200 private int hash(int hashCode) {
201 return supplementalHash(hashCode) & (capacity - 1);
202 }
203
204
205 private static int supplementalHash(int h) {
206 h ^= (h >>> 20) ^ (h >>> 12);
207 return h ^ (h >>> 7) ^ (h >>> 4);
208 }
209
210
211 private int trimToPowerOf2(int initialCapacity) {
212 int capacity = 1;
213 while (capacity < initialCapacity) {
214 capacity <<= 1;
215 }
216
217 return capacity;
218 }
219
220
221 private void removeEntries() {
222 for (int i = 0; i < capacity; i++) {
223 if (table[i] != null) {
224 table[i].clear();
225 }
226 }
227 }
228
229
230 private void rehash() {
231 java.util.Set<Entry<K, V>> set = entrySet();
232 capacity <<= 1;
233 table = new LinkedList[capacity];
234 size = 0;
235
236 for (Entry<K, V> entry: set) {
237 put(entry.getKey(), entry.getValue());
238 }
239 }
240
241 @Override
242 public String toString() {
243 StringBuilder builder = new StringBuilder("[");
244
245 for (int i = 0; i < capacity; i++) {
246 if (table[i] != null && table[i].size() > 0)
247 for (Entry<K, V> entry: table[i])
248 builder.append(entry);
249 }
250
251 builder.append("]");
252 return builder.toString();
253 }
254 }