1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.collections4.map;
18
19 import java.io.IOException;
20 import java.io.ObjectInputStream;
21 import java.io.ObjectOutputStream;
22 import java.util.AbstractCollection;
23 import java.util.AbstractMap;
24 import java.util.AbstractSet;
25 import java.util.Arrays;
26 import java.util.Collection;
27 import java.util.ConcurrentModificationException;
28 import java.util.Iterator;
29 import java.util.Map;
30 import java.util.NoSuchElementException;
31 import java.util.Objects;
32 import java.util.Set;
33
34 import org.apache.commons.collections4.CollectionUtils;
35 import org.apache.commons.collections4.IterableMap;
36 import org.apache.commons.collections4.KeyValue;
37 import org.apache.commons.collections4.MapIterator;
38 import org.apache.commons.collections4.iterators.EmptyIterator;
39 import org.apache.commons.collections4.iterators.EmptyMapIterator;
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 public class AbstractHashedMap<K, V> extends AbstractMap<K, V> implements IterableMap<K, V> {
66
67
68
69
70
71
72
73 protected static class EntrySet<K, V> extends AbstractSet<Map.Entry<K, V>> {
74
75
76 private final AbstractHashedMap<K, V> parent;
77
78
79
80
81
82
83 protected EntrySet(final AbstractHashedMap<K, V> parent) {
84 this.parent = parent;
85 }
86
87 @Override
88 public void clear() {
89 parent.clear();
90 }
91
92 @Override
93 public boolean contains(final Object entry) {
94 if (entry instanceof Map.Entry) {
95 final Map.Entry<?, ?> e = (Map.Entry<?, ?>) entry;
96 final Entry<K, V> match = parent.getEntry(e.getKey());
97 return match != null && match.equals(e);
98 }
99 return false;
100 }
101
102 @Override
103 public Iterator<Map.Entry<K, V>> iterator() {
104 return parent.createEntrySetIterator();
105 }
106
107 @Override
108 public boolean remove(final Object obj) {
109 if (!(obj instanceof Map.Entry)) {
110 return false;
111 }
112 if (!contains(obj)) {
113 return false;
114 }
115 final Map.Entry<?, ?> entry = (Map.Entry<?, ?>) obj;
116 parent.remove(entry.getKey());
117 return true;
118 }
119
120 @Override
121 public int size() {
122 return parent.size();
123 }
124 }
125
126
127
128
129
130
131
132 protected static class EntrySetIterator<K, V> extends HashIterator<K, V> implements Iterator<Map.Entry<K, V>> {
133
134
135
136
137
138
139 protected EntrySetIterator(final AbstractHashedMap<K, V> parent) {
140 super(parent);
141 }
142
143 @Override
144 public Map.Entry<K, V> next() {
145 return super.nextEntry();
146 }
147 }
148
149
150
151
152
153
154
155
156
157
158
159
160
161 protected static class HashEntry<K, V> implements Map.Entry<K, V>, KeyValue<K, V> {
162
163
164 protected HashEntry<K, V> next;
165
166
167 protected int hashCode;
168
169
170 protected Object key;
171
172
173 protected Object value;
174
175
176
177
178
179
180
181
182
183 protected HashEntry(final HashEntry<K, V> next, final int hashCode, final Object key, final V value) {
184 this.next = next;
185 this.hashCode = hashCode;
186 this.key = key;
187 this.value = value;
188 }
189
190 @Override
191 public boolean equals(final Object obj) {
192 if (obj == this) {
193 return true;
194 }
195 if (!(obj instanceof Map.Entry)) {
196 return false;
197 }
198 final Map.Entry<?, ?> other = (Map.Entry<?, ?>) obj;
199 return
200 Objects.equals(getKey(), other.getKey()) &&
201 Objects.equals(getValue(), other.getValue());
202 }
203
204 @Override
205 @SuppressWarnings("unchecked")
206 public K getKey() {
207 if (key == NULL) {
208 return null;
209 }
210 return (K) key;
211 }
212
213 @Override
214 @SuppressWarnings("unchecked")
215 public V getValue() {
216 return (V) value;
217 }
218
219 @Override
220 public int hashCode() {
221 return (getKey() == null ? 0 : getKey().hashCode()) ^
222 (getValue() == null ? 0 : getValue().hashCode());
223 }
224
225 @Override
226 @SuppressWarnings("unchecked")
227 public V setValue(final V value) {
228 final Object old = this.value;
229 this.value = value;
230 return (V) old;
231 }
232
233 @Override
234 public String toString() {
235 return new StringBuilder().append(getKey()).append('=').append(getValue()).toString();
236 }
237 }
238
239
240
241
242
243
244 protected abstract static class HashIterator<K, V> {
245
246
247 private final AbstractHashedMap<K, V> parent;
248
249
250 private int hashIndex;
251
252
253 private HashEntry<K, V> last;
254
255
256 private HashEntry<K, V> next;
257
258
259 private int expectedModCount;
260
261
262
263
264
265
266 protected HashIterator(final AbstractHashedMap<K, V> parent) {
267 this.parent = parent;
268 final HashEntry<K, V>[] data = parent.data;
269 int i = data.length;
270 HashEntry<K, V> next = null;
271 while (i > 0 && next == null) {
272 next = data[--i];
273 }
274 this.next = next;
275 this.hashIndex = i;
276 this.expectedModCount = parent.modCount;
277 }
278
279
280
281
282
283
284 protected HashEntry<K, V> currentEntry() {
285 return last;
286 }
287
288
289
290
291
292
293 public boolean hasNext() {
294 return next != null;
295 }
296
297
298
299
300
301
302 protected HashEntry<K, V> nextEntry() {
303 if (parent.modCount != expectedModCount) {
304 throw new ConcurrentModificationException();
305 }
306 final HashEntry<K, V> newCurrent = next;
307 if (newCurrent == null) {
308 throw new NoSuchElementException(NO_NEXT_ENTRY);
309 }
310 final HashEntry<K, V>[] data = parent.data;
311 int i = hashIndex;
312 HashEntry<K, V> n = newCurrent.next;
313 while (n == null && i > 0) {
314 n = data[--i];
315 }
316 next = n;
317 hashIndex = i;
318 last = newCurrent;
319 return newCurrent;
320 }
321
322
323
324
325 public void remove() {
326 if (last == null) {
327 throw new IllegalStateException(REMOVE_INVALID);
328 }
329 if (parent.modCount != expectedModCount) {
330 throw new ConcurrentModificationException();
331 }
332 parent.remove(last.getKey());
333 last = null;
334 expectedModCount = parent.modCount;
335 }
336
337 @Override
338 public String toString() {
339 if (last != null) {
340 return "Iterator[" + last.getKey() + "=" + last.getValue() + "]";
341 }
342 return "Iterator[]";
343 }
344 }
345
346
347
348
349
350
351
352 protected static class HashMapIterator<K, V> extends HashIterator<K, V> implements MapIterator<K, V> {
353
354
355
356
357
358
359 protected HashMapIterator(final AbstractHashedMap<K, V> parent) {
360 super(parent);
361 }
362
363 @Override
364 public K getKey() {
365 final HashEntry<K, V> current = currentEntry();
366 if (current == null) {
367 throw new IllegalStateException(GETKEY_INVALID);
368 }
369 return current.getKey();
370 }
371
372 @Override
373 public V getValue() {
374 final HashEntry<K, V> current = currentEntry();
375 if (current == null) {
376 throw new IllegalStateException(GETVALUE_INVALID);
377 }
378 return current.getValue();
379 }
380
381 @Override
382 public K next() {
383 return super.nextEntry().getKey();
384 }
385
386 @Override
387 public V setValue(final V value) {
388 final HashEntry<K, V> current = currentEntry();
389 if (current == null) {
390 throw new IllegalStateException(SETVALUE_INVALID);
391 }
392 return current.setValue(value);
393 }
394 }
395
396
397
398
399
400
401 protected static class KeySet<K> extends AbstractSet<K> {
402
403
404 private final AbstractHashedMap<K, ?> parent;
405
406
407
408
409
410
411 protected KeySet(final AbstractHashedMap<K, ?> parent) {
412 this.parent = parent;
413 }
414
415 @Override
416 public void clear() {
417 parent.clear();
418 }
419
420 @Override
421 public boolean contains(final Object key) {
422 return parent.containsKey(key);
423 }
424
425 @Override
426 public Iterator<K> iterator() {
427 return parent.createKeySetIterator();
428 }
429
430 @Override
431 public boolean remove(final Object key) {
432 final boolean result = parent.containsKey(key);
433 parent.remove(key);
434 return result;
435 }
436
437 @Override
438 public int size() {
439 return parent.size();
440 }
441 }
442
443
444
445
446
447
448 protected static class KeySetIterator<K> extends HashIterator<K, Object> implements Iterator<K> {
449
450
451
452
453
454
455 @SuppressWarnings("unchecked")
456 protected KeySetIterator(final AbstractHashedMap<K, ?> parent) {
457 super((AbstractHashedMap<K, Object>) parent);
458 }
459
460 @Override
461 public K next() {
462 return super.nextEntry().getKey();
463 }
464 }
465
466
467
468
469
470
471 protected static class Values<V> extends AbstractCollection<V> {
472
473
474 private final AbstractHashedMap<?, V> parent;
475
476
477
478
479
480
481 protected Values(final AbstractHashedMap<?, V> parent) {
482 this.parent = parent;
483 }
484
485 @Override
486 public void clear() {
487 parent.clear();
488 }
489
490 @Override
491 public boolean contains(final Object value) {
492 return parent.containsValue(value);
493 }
494
495 @Override
496 public Iterator<V> iterator() {
497 return parent.createValuesIterator();
498 }
499
500 @Override
501 public int size() {
502 return parent.size();
503 }
504 }
505
506
507
508
509
510
511 protected static class ValuesIterator<V> extends HashIterator<Object, V> implements Iterator<V> {
512
513
514
515
516
517
518 @SuppressWarnings("unchecked")
519 protected ValuesIterator(final AbstractHashedMap<?, V> parent) {
520 super((AbstractHashedMap<Object, V>) parent);
521 }
522
523 @Override
524 public V next() {
525 return super.nextEntry().getValue();
526 }
527 }
528
529
530 protected static final String NO_NEXT_ENTRY = "No next() entry in the iteration";
531
532
533 protected static final String NO_PREVIOUS_ENTRY = "No previous() entry in the iteration";
534
535
536 protected static final String REMOVE_INVALID = "remove() can only be called once after next()";
537
538
539 protected static final String GETKEY_INVALID = "getKey() can only be called after next() and before remove()";
540
541
542 protected static final String GETVALUE_INVALID = "getValue() can only be called after next() and before remove()";
543
544
545 protected static final String SETVALUE_INVALID = "setValue() can only be called after next() and before remove()";
546
547
548 protected static final int DEFAULT_CAPACITY = 16;
549
550
551 protected static final int DEFAULT_THRESHOLD = 12;
552
553
554 protected static final float DEFAULT_LOAD_FACTOR = 0.75f;
555
556
557 protected static final int MAXIMUM_CAPACITY = 1 << 30;
558
559
560 protected static final Object NULL = new Object();
561
562
563 transient float loadFactor;
564
565
566 transient int size;
567
568
569 transient HashEntry<K, V>[] data;
570
571
572 transient int threshold;
573
574
575 transient int modCount;
576
577
578 transient EntrySet<K, V> entrySet;
579
580
581 transient KeySet<K> keySet;
582
583
584 transient Values<V> values;
585
586
587
588
589 protected AbstractHashedMap() {
590 }
591
592
593
594
595
596
597
598
599 protected AbstractHashedMap(final int initialCapacity) {
600 this(initialCapacity, DEFAULT_LOAD_FACTOR);
601 }
602
603
604
605
606
607
608
609
610
611
612 @SuppressWarnings("unchecked")
613 protected AbstractHashedMap(int initialCapacity, final float loadFactor) {
614 if (initialCapacity < 0) {
615 throw new IllegalArgumentException("Initial capacity must be a non negative number");
616 }
617 if (loadFactor <= 0.0f || Float.isNaN(loadFactor)) {
618 throw new IllegalArgumentException("Load factor must be greater than 0");
619 }
620 this.loadFactor = loadFactor;
621 initialCapacity = calculateNewCapacity(initialCapacity);
622 this.threshold = calculateThreshold(initialCapacity, loadFactor);
623 this.data = new HashEntry[initialCapacity];
624 init();
625 }
626
627
628
629
630
631
632
633
634 @SuppressWarnings("unchecked")
635 protected AbstractHashedMap(final int initialCapacity, final float loadFactor, final int threshold) {
636 this.loadFactor = loadFactor;
637 this.data = new HashEntry[initialCapacity];
638 this.threshold = threshold;
639 init();
640 }
641
642
643
644
645
646
647
648 protected AbstractHashedMap(final Map<? extends K, ? extends V> map) {
649 this(Math.max(2 * map.size(), DEFAULT_CAPACITY), DEFAULT_LOAD_FACTOR);
650 putAll(map);
651 }
652
653
654
655
656
657
658
659
660
661
662
663 protected void addEntry(final HashEntry<K, V> entry, final int hashIndex) {
664 data[hashIndex] = entry;
665 }
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681 protected void addMapping(final int hashIndex, final int hashCode, final K key, final V value) {
682 modCount++;
683 final HashEntry<K, V> entry = createEntry(data[hashIndex], hashCode, key, value);
684 addEntry(entry, hashIndex);
685 size++;
686 checkCapacity();
687 }
688
689
690
691
692
693
694
695
696 protected int calculateNewCapacity(final int proposedCapacity) {
697 int newCapacity = 1;
698 if (proposedCapacity > MAXIMUM_CAPACITY) {
699 newCapacity = MAXIMUM_CAPACITY;
700 } else {
701 while (newCapacity < proposedCapacity) {
702 newCapacity <<= 1;
703 }
704 if (newCapacity > MAXIMUM_CAPACITY) {
705 newCapacity = MAXIMUM_CAPACITY;
706 }
707 }
708 return newCapacity;
709 }
710
711
712
713
714
715
716
717
718
719 protected int calculateThreshold(final int newCapacity, final float factor) {
720 return (int) (newCapacity * factor);
721 }
722
723
724
725
726
727
728
729 protected void checkCapacity() {
730 if (size >= threshold) {
731 final int newCapacity = data.length * 2;
732 if (newCapacity <= MAXIMUM_CAPACITY) {
733 ensureCapacity(newCapacity);
734 }
735 }
736 }
737
738
739
740
741
742 @Override
743 public void clear() {
744 modCount++;
745 final HashEntry<K, V>[] data = this.data;
746 Arrays.fill(data, null);
747 size = 0;
748 }
749
750
751
752
753
754
755
756
757
758
759
760 @Override
761 @SuppressWarnings("unchecked")
762 protected AbstractHashedMap<K, V> clone() {
763 try {
764 final AbstractHashedMap<K, V> cloned = (AbstractHashedMap<K, V>) super.clone();
765 cloned.data = new HashEntry[data.length];
766 cloned.entrySet = null;
767 cloned.keySet = null;
768 cloned.values = null;
769 cloned.modCount = 0;
770 cloned.size = 0;
771 cloned.init();
772 cloned.putAll(this);
773 return cloned;
774 } catch (final CloneNotSupportedException ex) {
775 throw new UnsupportedOperationException(ex);
776 }
777 }
778
779
780
781
782
783
784
785 @Override
786 public boolean containsKey(Object key) {
787 key = convertKey(key);
788 final int hashCode = hash(key);
789 HashEntry<K, V> entry = data[hashIndex(hashCode, data.length)];
790 while (entry != null) {
791 if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
792 return true;
793 }
794 entry = entry.next;
795 }
796 return false;
797 }
798
799
800
801
802
803
804
805 @Override
806 public boolean containsValue(final Object value) {
807 if (value == null) {
808 for (final HashEntry<K, V> element : data) {
809 HashEntry<K, V> entry = element;
810 while (entry != null) {
811 if (entry.getValue() == null) {
812 return true;
813 }
814 entry = entry.next;
815 }
816 }
817 } else {
818 for (final HashEntry<K, V> element : data) {
819 HashEntry<K, V> entry = element;
820 while (entry != null) {
821 if (isEqualValue(value, entry.getValue())) {
822 return true;
823 }
824 entry = entry.next;
825 }
826 }
827 }
828 return false;
829 }
830
831
832
833
834
835
836
837
838
839
840
841
842
843 protected Object convertKey(final Object key) {
844 return key == null ? NULL : key;
845 }
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861 protected HashEntry<K, V> createEntry(final HashEntry<K, V> next, final int hashCode, final K key, final V value) {
862 return new HashEntry<>(next, hashCode, convertKey(key), value);
863 }
864
865
866
867
868
869
870
871 protected Iterator<Map.Entry<K, V>> createEntrySetIterator() {
872 if (isEmpty()) {
873 return EmptyIterator.<Map.Entry<K, V>>emptyIterator();
874 }
875 return new EntrySetIterator<>(this);
876 }
877
878
879
880
881
882
883
884 protected Iterator<K> createKeySetIterator() {
885 if (isEmpty()) {
886 return EmptyIterator.<K>emptyIterator();
887 }
888 return new KeySetIterator<>(this);
889 }
890
891
892
893
894
895
896
897 protected Iterator<V> createValuesIterator() {
898 if (isEmpty()) {
899 return EmptyIterator.<V>emptyIterator();
900 }
901 return new ValuesIterator<>(this);
902 }
903
904
905
906
907
908
909
910
911
912
913 protected void destroyEntry(final HashEntry<K, V> entry) {
914 entry.next = null;
915 entry.key = null;
916 entry.value = null;
917 }
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942 @SuppressWarnings("unchecked")
943 protected void doReadObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
944 loadFactor = in.readFloat();
945 final int capacity = in.readInt();
946 final int size = in.readInt();
947 init();
948 threshold = calculateThreshold(capacity, loadFactor);
949 data = new HashEntry[capacity];
950 for (int i = 0; i < size; i++) {
951 final K key = (K) in.readObject();
952 final V value = (V) in.readObject();
953 put(key, value);
954 }
955 }
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980 protected void doWriteObject(final ObjectOutputStream out) throws IOException {
981 out.writeFloat(loadFactor);
982 out.writeInt(data.length);
983 out.writeInt(size);
984 for (final MapIterator<K, V> it = mapIterator(); it.hasNext();) {
985 out.writeObject(it.next());
986 out.writeObject(it.getValue());
987 }
988 }
989
990
991
992
993
994
995 @SuppressWarnings("unchecked")
996 protected void ensureCapacity(final int newCapacity) {
997 final int oldCapacity = data.length;
998 if (newCapacity <= oldCapacity) {
999 return;
1000 }
1001 if (size == 0) {
1002 threshold = calculateThreshold(newCapacity, loadFactor);
1003 data = new HashEntry[newCapacity];
1004 } else {
1005 final HashEntry<K, V>[] oldEntries = data;
1006 final HashEntry<K, V>[] newEntries = new HashEntry[newCapacity];
1007
1008 modCount++;
1009 for (int i = oldCapacity - 1; i >= 0; i--) {
1010 HashEntry<K, V> entry = oldEntries[i];
1011 if (entry != null) {
1012 oldEntries[i] = null;
1013 do {
1014 final HashEntry<K, V> next = entry.next;
1015 final int index = hashIndex(entry.hashCode, newCapacity);
1016 entry.next = newEntries[index];
1017 newEntries[index] = entry;
1018 entry = next;
1019 } while (entry != null);
1020 }
1021 }
1022 threshold = calculateThreshold(newCapacity, loadFactor);
1023 data = newEntries;
1024 }
1025 }
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036 protected int entryHashCode(final HashEntry<K, V> entry) {
1037 return entry.hashCode;
1038 }
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049 protected K entryKey(final HashEntry<K, V> entry) {
1050 return entry.getKey();
1051 }
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062 protected HashEntry<K, V> entryNext(final HashEntry<K, V> entry) {
1063 return entry.next;
1064 }
1065
1066
1067
1068
1069
1070
1071
1072
1073 @Override
1074 public Set<Map.Entry<K, V>> entrySet() {
1075 if (entrySet == null) {
1076 entrySet = new EntrySet<>(this);
1077 }
1078 return entrySet;
1079 }
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090 protected V entryValue(final HashEntry<K, V> entry) {
1091 return entry.getValue();
1092 }
1093
1094
1095
1096
1097
1098
1099
1100 @Override
1101 public boolean equals(final Object obj) {
1102 if (obj == this) {
1103 return true;
1104 }
1105 if (!(obj instanceof Map)) {
1106 return false;
1107 }
1108 final Map<?, ?> map = (Map<?, ?>) obj;
1109 if (map.size() != size()) {
1110 return false;
1111 }
1112 final MapIterator<?, ?> it = mapIterator();
1113 try {
1114 while (it.hasNext()) {
1115 final Object key = it.next();
1116 final Object value = it.getValue();
1117 if (value == null) {
1118 if (map.get(key) != null || !map.containsKey(key)) {
1119 return false;
1120 }
1121 } else if (!value.equals(map.get(key))) {
1122 return false;
1123 }
1124 }
1125 } catch (final ClassCastException | NullPointerException ignored) {
1126 return false;
1127 }
1128 return true;
1129 }
1130
1131
1132
1133
1134
1135
1136
1137 @Override
1138 public V get(Object key) {
1139 key = convertKey(key);
1140 final int hashCode = hash(key);
1141 HashEntry<K, V> entry = data[hashIndex(hashCode, data.length)];
1142 while (entry != null) {
1143 if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
1144 return entry.getValue();
1145 }
1146 entry = entry.next;
1147 }
1148 return null;
1149 }
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162 protected HashEntry<K, V> getEntry(Object key) {
1163 key = convertKey(key);
1164 final int hashCode = hash(key);
1165 HashEntry<K, V> entry = data[hashIndex(hashCode, data.length)];
1166 while (entry != null) {
1167 if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
1168 return entry;
1169 }
1170 entry = entry.next;
1171 }
1172 return null;
1173 }
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183 protected int hash(final Object key) {
1184
1185 int h = key.hashCode();
1186 h += ~(h << 9);
1187 h ^= h >>> 14;
1188 h += h << 4;
1189 h ^= h >>> 10;
1190 return h;
1191 }
1192
1193
1194
1195
1196
1197
1198 @Override
1199 public int hashCode() {
1200 int total = 0;
1201 final Iterator<Map.Entry<K, V>> it = createEntrySetIterator();
1202 while (it.hasNext()) {
1203 total += it.next().hashCode();
1204 }
1205 return total;
1206 }
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217 protected int hashIndex(final int hashCode, final int dataSize) {
1218 return hashCode & dataSize - 1;
1219 }
1220
1221
1222
1223
1224 protected void init() {
1225
1226 }
1227
1228
1229
1230
1231
1232
1233 @Override
1234 public boolean isEmpty() {
1235 return size == 0;
1236 }
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247 protected boolean isEqualKey(final Object key1, final Object key2) {
1248 return Objects.equals(key1, key2);
1249 }
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260 protected boolean isEqualValue(final Object value1, final Object value2) {
1261 return Objects.equals(value1, value2);
1262 }
1263
1264
1265
1266
1267
1268
1269
1270
1271 @Override
1272 public Set<K> keySet() {
1273 if (keySet == null) {
1274 keySet = new KeySet<>(this);
1275 }
1276 return keySet;
1277 }
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291 @Override
1292 public MapIterator<K, V> mapIterator() {
1293 if (size == 0) {
1294 return EmptyMapIterator.<K, V>emptyMapIterator();
1295 }
1296 return new HashMapIterator<>(this);
1297 }
1298
1299
1300
1301
1302
1303
1304
1305
1306 @Override
1307 public V put(final K key, final V value) {
1308 final Object convertedKey = convertKey(key);
1309 final int hashCode = hash(convertedKey);
1310 final int index = hashIndex(hashCode, data.length);
1311 HashEntry<K, V> entry = data[index];
1312 while (entry != null) {
1313 if (entry.hashCode == hashCode && isEqualKey(convertedKey, entry.key)) {
1314 final V oldValue = entry.getValue();
1315 updateEntry(entry, value);
1316 return oldValue;
1317 }
1318 entry = entry.next;
1319 }
1320
1321 addMapping(index, hashCode, key, value);
1322 return null;
1323 }
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335 @Override
1336 public void putAll(final Map<? extends K, ? extends V> map) {
1337 final int mapSize = map.size();
1338 if (mapSize == 0) {
1339 return;
1340 }
1341 final int newSize = (int) ((size + mapSize) / loadFactor + 1);
1342 ensureCapacity(calculateNewCapacity(newSize));
1343 for (final Map.Entry<? extends K, ? extends V> entry: map.entrySet()) {
1344 put(entry.getKey(), entry.getValue());
1345 }
1346 }
1347
1348
1349
1350
1351
1352
1353
1354 @Override
1355 public V remove(Object key) {
1356 key = convertKey(key);
1357 final int hashCode = hash(key);
1358 final int index = hashIndex(hashCode, data.length);
1359 HashEntry<K, V> entry = data[index];
1360 HashEntry<K, V> previous = null;
1361 while (entry != null) {
1362 if (entry.hashCode == hashCode && isEqualKey(key, entry.key)) {
1363 final V oldValue = entry.getValue();
1364 removeMapping(entry, index, previous);
1365 return oldValue;
1366 }
1367 previous = entry;
1368 entry = entry.next;
1369 }
1370 return null;
1371 }
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385 protected void removeEntry(final HashEntry<K, V> entry, final int hashIndex, final HashEntry<K, V> previous) {
1386 if (previous == null) {
1387 data[hashIndex] = entry.next;
1388 } else {
1389 previous.next = entry.next;
1390 }
1391 }
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405 protected void removeMapping(final HashEntry<K, V> entry, final int hashIndex, final HashEntry<K, V> previous) {
1406 modCount++;
1407 removeEntry(entry, hashIndex, previous);
1408 size--;
1409 destroyEntry(entry);
1410 }
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425 protected void reuseEntry(final HashEntry<K, V> entry, final int hashIndex, final int hashCode,
1426 final K key, final V value) {
1427 entry.next = data[hashIndex];
1428 entry.hashCode = hashCode;
1429 entry.key = key;
1430 entry.value = value;
1431 }
1432
1433
1434
1435
1436
1437
1438 @Override
1439 public int size() {
1440 return size;
1441 }
1442
1443
1444
1445
1446
1447
1448 @Override
1449 public String toString() {
1450 if (isEmpty()) {
1451 return "{}";
1452 }
1453 final StringBuilder buf = new StringBuilder(32 * size());
1454 buf.append('{');
1455
1456 final MapIterator<K, V> it = mapIterator();
1457 boolean hasNext = it.hasNext();
1458 while (hasNext) {
1459 final K key = it.next();
1460 final V value = it.getValue();
1461 buf.append(key == this ? "(this Map)" : key)
1462 .append('=')
1463 .append(value == this ? "(this Map)" : value);
1464
1465 hasNext = it.hasNext();
1466 if (hasNext) {
1467 buf.append(CollectionUtils.COMMA).append(' ');
1468 }
1469 }
1470
1471 buf.append('}');
1472 return buf.toString();
1473 }
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485 protected void updateEntry(final HashEntry<K, V> entry, final V newValue) {
1486 entry.setValue(newValue);
1487 }
1488
1489
1490
1491
1492
1493
1494
1495
1496 @Override
1497 public Collection<V> values() {
1498 if (values == null) {
1499 values = new Values<>(this);
1500 }
1501 return values;
1502 }
1503 }