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