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