001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: package java.util;
019:
020: import java.io.IOException;
021: import java.io.ObjectInputStream;
022: import java.io.ObjectOutputStream;
023: import java.io.Serializable;
024:
025: /**
026: * HashMap is an implementation of Map. All optional operations are supported,
027: * adding and removing. Keys and values can be any objects.
028: */
029: public class HashMap<K, V> extends AbstractMap<K, V> implements
030: Map<K, V>, Cloneable, Serializable {
031: private static final long serialVersionUID = 362498820763181265L;
032:
033: transient int elementCount;
034:
035: transient Entry<K, V>[] elementData;
036:
037: final float loadFactor;
038:
039: int threshold;
040:
041: transient int modCount = 0;
042:
043: private static final int DEFAULT_SIZE = 16;
044:
045: static class Entry<K, V> extends MapEntry<K, V> {
046: final int origKeyHash;
047:
048: Entry<K, V> next;
049:
050: Entry(K theKey, int hash) {
051: super (theKey, null);
052: this .origKeyHash = hash;
053: }
054:
055: Entry(K theKey, V theValue) {
056: super (theKey, theValue);
057: origKeyHash = (theKey == null ? 0 : theKey.hashCode());
058: }
059:
060: @Override
061: @SuppressWarnings("unchecked")
062: public Object clone() {
063: Entry<K, V> entry = (Entry<K, V>) super .clone();
064: if (next != null) {
065: entry.next = (Entry<K, V>) next.clone();
066: }
067: return entry;
068: }
069: }
070:
071: private static class AbstractMapIterator<K, V> {
072: private int position = 0;
073: int expectedModCount;
074: Entry<K, V> futureEntry;
075: Entry<K, V> currentEntry;
076: Entry<K, V> prevEntry;
077:
078: final HashMap<K, V> associatedMap;
079:
080: AbstractMapIterator(HashMap<K, V> hm) {
081: associatedMap = hm;
082: expectedModCount = hm.modCount;
083: futureEntry = null;
084: }
085:
086: public boolean hasNext() {
087: if (futureEntry != null) {
088: return true;
089: }
090: while (position < associatedMap.elementData.length) {
091: if (associatedMap.elementData[position] == null) {
092: position++;
093: } else {
094: return true;
095: }
096: }
097: return false;
098: }
099:
100: final void checkConcurrentMod()
101: throws ConcurrentModificationException {
102: if (expectedModCount != associatedMap.modCount) {
103: throw new ConcurrentModificationException();
104: }
105: }
106:
107: final void makeNext() {
108: checkConcurrentMod();
109: if (!hasNext()) {
110: throw new NoSuchElementException();
111: }
112: if (futureEntry == null) {
113: currentEntry = associatedMap.elementData[position++];
114: futureEntry = currentEntry.next;
115: prevEntry = null;
116: } else {
117: if (currentEntry != null) {
118: prevEntry = currentEntry;
119: }
120: currentEntry = futureEntry;
121: futureEntry = futureEntry.next;
122: }
123: }
124:
125: public final void remove() {
126: checkConcurrentMod();
127: if (currentEntry == null) {
128: throw new IllegalStateException();
129: }
130: if (prevEntry == null) {
131: int index = currentEntry.origKeyHash
132: & (associatedMap.elementData.length - 1);
133: //assert associatedMap.elementData[index] == currentEntry;
134: associatedMap.elementData[index] = associatedMap.elementData[index].next;
135: } else {
136: prevEntry.next = currentEntry.next;
137: }
138: currentEntry = null;
139: expectedModCount++;
140: associatedMap.modCount++;
141: associatedMap.elementCount--;
142:
143: }
144: }
145:
146: private static class EntryIterator<K, V> extends
147: AbstractMapIterator<K, V> implements
148: Iterator<Map.Entry<K, V>> {
149:
150: EntryIterator(HashMap<K, V> map) {
151: super (map);
152: }
153:
154: public Map.Entry<K, V> next() {
155: makeNext();
156: return currentEntry;
157: }
158: }
159:
160: private static class KeyIterator<K, V> extends
161: AbstractMapIterator<K, V> implements Iterator<K> {
162:
163: KeyIterator(HashMap<K, V> map) {
164: super (map);
165: }
166:
167: public K next() {
168: makeNext();
169: return currentEntry.key;
170: }
171: }
172:
173: private static class ValueIterator<K, V> extends
174: AbstractMapIterator<K, V> implements Iterator<V> {
175:
176: ValueIterator(HashMap<K, V> map) {
177: super (map);
178: }
179:
180: public V next() {
181: makeNext();
182: return currentEntry.value;
183: }
184: }
185:
186: static class HashMapEntrySet<KT, VT> extends
187: AbstractSet<Map.Entry<KT, VT>> {
188: private final HashMap<KT, VT> associatedMap;
189:
190: public HashMapEntrySet(HashMap<KT, VT> hm) {
191: associatedMap = hm;
192: }
193:
194: HashMap<KT, VT> hashMap() {
195: return associatedMap;
196: }
197:
198: @Override
199: public int size() {
200: return associatedMap.elementCount;
201: }
202:
203: @Override
204: public void clear() {
205: associatedMap.clear();
206: }
207:
208: @Override
209: public boolean remove(Object object) {
210: if (object instanceof Map.Entry) {
211: Map.Entry<?, ?> oEntry = (Map.Entry<?, ?>) object;
212: Entry<KT, VT> entry = associatedMap.getEntry(oEntry
213: .getKey());
214: if (valuesEq(entry, oEntry)) {
215: associatedMap.removeEntry(entry);
216: return true;
217: }
218: }
219: return false;
220: }
221:
222: @Override
223: public boolean contains(Object object) {
224: if (object instanceof Map.Entry) {
225: Map.Entry<?, ?> oEntry = (Map.Entry<?, ?>) object;
226: Entry entry = associatedMap.getEntry(oEntry.getKey());
227: return valuesEq(entry, oEntry);
228: }
229: return false;
230: }
231:
232: private static boolean valuesEq(Entry entry,
233: Map.Entry<?, ?> oEntry) {
234: return (entry != null)
235: && ((entry.value == null) ? (oEntry.getValue() == null)
236: : (entry.value.equals(oEntry.getValue())));
237: }
238:
239: @Override
240: public Iterator<Map.Entry<KT, VT>> iterator() {
241: return new EntryIterator<KT, VT>(associatedMap);
242: }
243: }
244:
245: /**
246: * Create a new element array
247: *
248: * @param s
249: * @return Reference to the element array
250: */
251: @SuppressWarnings("unchecked")
252: Entry<K, V>[] newElementArray(int s) {
253: return new Entry[s];
254: }
255:
256: /**
257: * Constructs a new empty instance of HashMap.
258: *
259: */
260: public HashMap() {
261: this (DEFAULT_SIZE);
262: }
263:
264: /**
265: * Constructs a new instance of HashMap with the specified capacity.
266: *
267: * @param capacity
268: * the initial capacity of this HashMap
269: *
270: * @exception IllegalArgumentException
271: * when the capacity is less than zero
272: */
273: public HashMap(int capacity) {
274: if (capacity >= 0) {
275: capacity = calculateCapacity(capacity);
276: elementCount = 0;
277: elementData = newElementArray(capacity);
278: loadFactor = 0.75f; // Default load factor of 0.75
279: computeMaxSize();
280: } else {
281: throw new IllegalArgumentException();
282: }
283: }
284:
285: private static final int calculateCapacity(int x) {
286: if (x >= 1 << 30) {
287: return 1 << 30;
288: }
289: if (x == 0) {
290: return 16;
291: }
292: x = x - 1;
293: x |= x >> 1;
294: x |= x >> 2;
295: x |= x >> 4;
296: x |= x >> 8;
297: x |= x >> 16;
298: return x + 1;
299: }
300:
301: /**
302: * Constructs a new instance of HashMap with the specified capacity and load
303: * factor.
304: *
305: *
306: * @param capacity
307: * the initial capacity
308: * @param loadFactor
309: * the initial load factor
310: *
311: * @exception IllegalArgumentException
312: * when the capacity is less than zero or the load factor is
313: * less or equal to zero
314: */
315: public HashMap(int capacity, float loadFactor) {
316: if (capacity >= 0 && loadFactor > 0) {
317: capacity = calculateCapacity(capacity);
318: elementCount = 0;
319: elementData = newElementArray(capacity == 0 ? 1 : capacity);
320: this .loadFactor = loadFactor;
321: computeMaxSize();
322: } else {
323: throw new IllegalArgumentException();
324: }
325: }
326:
327: /**
328: * Constructs a new instance of HashMap containing the mappings from the
329: * specified Map.
330: *
331: * @param map
332: * the mappings to add
333: */
334: public HashMap(Map<? extends K, ? extends V> map) {
335: this (map.size() < 6 ? 11 : map.size() * 2);
336: putAllImpl(map);
337: }
338:
339: /**
340: * Removes all mappings from this HashMap, leaving it empty.
341: *
342: * @see #isEmpty
343: * @see #size
344: */
345: @Override
346: public void clear() {
347: if (elementCount > 0) {
348: elementCount = 0;
349: Arrays.fill(elementData, null);
350: modCount++;
351: }
352: }
353:
354: /**
355: * Answers a new HashMap with the same mappings and size as this HashMap.
356: *
357: * @return a shallow copy of this HashMap
358: *
359: * @see java.lang.Cloneable
360: */
361: @Override
362: @SuppressWarnings("unchecked")
363: public Object clone() {
364: try {
365: HashMap<K, V> map = (HashMap<K, V>) super .clone();
366: map.elementCount = 0;
367: map.elementData = newElementArray(elementData.length);
368: Entry<K, V> entry;
369: for (int i = 0; i < elementData.length; i++) {
370: if ((entry = elementData[i]) != null) {
371: map.putImpl(entry.getKey(), entry.getValue());
372: while (entry.next != null) {
373: entry = entry.next;
374: map.putImpl(entry.getKey(), entry.getValue());
375: }
376: }
377: }
378: return map;
379: } catch (CloneNotSupportedException e) {
380: return null;
381: }
382: }
383:
384: private void computeMaxSize() {
385: threshold = (int) (elementData.length * loadFactor);
386: }
387:
388: /**
389: * Searches this HashMap for the specified key.
390: *
391: * @param key
392: * the object to search for
393: * @return true if <code>key</code> is a key of this HashMap, false
394: * otherwise
395: */
396: @Override
397: public boolean containsKey(Object key) {
398: Entry<K, V> m = getEntry(key);
399: return m != null;
400: }
401:
402: /**
403: * Searches this HashMap for the specified value.
404: *
405: * @param value
406: * the object to search for
407: * @return true if <code>value</code> is a value of this HashMap, false
408: * otherwise
409: */
410: @Override
411: public boolean containsValue(Object value) {
412: if (value != null) {
413: for (int i = elementData.length; --i >= 0;) {
414: Entry<K, V> entry = elementData[i];
415: while (entry != null) {
416: if (value.equals(entry.value)) {
417: return true;
418: }
419: entry = entry.next;
420: }
421: }
422: } else {
423: for (int i = elementData.length; --i >= 0;) {
424: Entry<K, V> entry = elementData[i];
425: while (entry != null) {
426: if (entry.value == null) {
427: return true;
428: }
429: entry = entry.next;
430: }
431: }
432: }
433: return false;
434: }
435:
436: /**
437: * Answers a Set of the mappings contained in this HashMap. Each element in
438: * the set is a Map.Entry. The set is backed by this HashMap so changes to
439: * one are reflected by the other. The set does not support adding.
440: *
441: * @return a Set of the mappings
442: */
443: @Override
444: public Set<Map.Entry<K, V>> entrySet() {
445: return new HashMapEntrySet<K, V>(this );
446: }
447:
448: /**
449: * Answers the value of the mapping with the specified key.
450: *
451: * @param key
452: * the key
453: * @return the value of the mapping with the specified key
454: */
455: @Override
456: public V get(Object key) {
457: Entry<K, V> m = getEntry(key);
458: if (m != null) {
459: return m.value;
460: }
461: return null;
462: }
463:
464: final Entry<K, V> getEntry(Object key) {
465: Entry<K, V> m;
466: if (key == null) {
467: m = findNullKeyEntry();
468: } else {
469: int hash = key.hashCode();
470: int index = hash & (elementData.length - 1);
471: m = findNonNullKeyEntry(key, index, hash);
472: }
473: return m;
474: }
475:
476: final Entry<K, V> findNonNullKeyEntry(Object key, int index,
477: int keyHash) {
478: Entry<K, V> m = elementData[index];
479: while (m != null
480: && (m.origKeyHash != keyHash || !key.equals(m.key))) {
481: m = m.next;
482: }
483: return m;
484: }
485:
486: final Entry<K, V> findNullKeyEntry() {
487: Entry<K, V> m = elementData[0];
488: while (m != null && m.key != null)
489: m = m.next;
490: return m;
491: }
492:
493: /**
494: * Answers if this HashMap has no elements, a size of zero.
495: *
496: * @return true if this HashMap has no elements, false otherwise
497: *
498: * @see #size
499: */
500: @Override
501: public boolean isEmpty() {
502: return elementCount == 0;
503: }
504:
505: /**
506: * Answers a Set of the keys contained in this HashMap. The set is backed by
507: * this HashMap so changes to one are reflected by the other. The set does
508: * not support adding.
509: *
510: * @return a Set of the keys
511: */
512: @Override
513: public Set<K> keySet() {
514: if (keySet == null) {
515: keySet = new AbstractSet<K>() {
516: @Override
517: public boolean contains(Object object) {
518: return containsKey(object);
519: }
520:
521: @Override
522: public int size() {
523: return HashMap.this .size();
524: }
525:
526: @Override
527: public void clear() {
528: HashMap.this .clear();
529: }
530:
531: @Override
532: public boolean remove(Object key) {
533: Entry<K, V> entry = HashMap.this .removeEntry(key);
534: return entry != null;
535: }
536:
537: @Override
538: public Iterator<K> iterator() {
539: return new KeyIterator<K, V>(HashMap.this );
540: }
541: };
542: }
543: return keySet;
544: }
545:
546: /**
547: * Maps the specified key to the specified value.
548: *
549: * @param key
550: * the key
551: * @param value
552: * the value
553: * @return the value of any previous mapping with the specified key or null
554: * if there was no mapping
555: */
556: @Override
557: public V put(K key, V value) {
558: return putImpl(key, value);
559: }
560:
561: V putImpl(K key, V value) {
562: Entry<K, V> entry;
563: if (key == null) {
564: entry = findNullKeyEntry();
565: if (entry == null) {
566: modCount++;
567: if (++elementCount > threshold) {
568: rehash();
569: }
570: entry = createHashedEntry(null, 0, 0);
571: }
572: } else {
573: int hash = key.hashCode();
574: int index = hash & (elementData.length - 1);
575: entry = findNonNullKeyEntry(key, index, hash);
576: if (entry == null) {
577: modCount++;
578: if (++elementCount > threshold) {
579: rehash();
580: index = hash & (elementData.length - 1);
581: }
582: entry = createHashedEntry(key, index, hash);
583: }
584: }
585:
586: V result = entry.value;
587: entry.value = value;
588: return result;
589: }
590:
591: Entry<K, V> createEntry(K key, int index, V value) {
592: Entry<K, V> entry = new Entry<K, V>(key, value);
593: entry.next = elementData[index];
594: elementData[index] = entry;
595: return entry;
596: }
597:
598: Entry<K, V> createHashedEntry(K key, int index, int hash) {
599: Entry<K, V> entry = new Entry<K, V>(key, hash);
600: entry.next = elementData[index];
601: elementData[index] = entry;
602: return entry;
603: }
604:
605: /**
606: * Copies all the mappings in the given map to this map. These mappings will
607: * replace all mappings that this map had for any of the keys currently in
608: * the given map.
609: *
610: * @param map
611: * the Map to copy mappings from
612: * @throws NullPointerException
613: * if the given map is null
614: */
615: @Override
616: public void putAll(Map<? extends K, ? extends V> map) {
617: if (!map.isEmpty()) {
618: putAllImpl(map);
619: }
620: }
621:
622: private void putAllImpl(Map<? extends K, ? extends V> map) {
623: int capacity = elementCount + map.size();
624: if (capacity > threshold) {
625: rehash(capacity);
626: }
627: for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
628: putImpl(entry.getKey(), entry.getValue());
629: }
630: }
631:
632: void rehash(int capacity) {
633: int length = calculateCapacity((capacity == 0 ? 1
634: : capacity << 1));
635:
636: Entry<K, V>[] newData = newElementArray(length);
637: for (int i = 0; i < elementData.length; i++) {
638: Entry<K, V> entry = elementData[i];
639: while (entry != null) {
640: int index = entry.origKeyHash & (length - 1);
641: Entry<K, V> next = entry.next;
642: entry.next = newData[index];
643: newData[index] = entry;
644: entry = next;
645: }
646: }
647: elementData = newData;
648: computeMaxSize();
649: }
650:
651: void rehash() {
652: rehash(elementData.length);
653: }
654:
655: /**
656: * Removes a mapping with the specified key from this HashMap.
657: *
658: * @param key
659: * the key of the mapping to remove
660: * @return the value of the removed mapping or null if key is not a key in
661: * this HashMap
662: */
663: @Override
664: public V remove(Object key) {
665: Entry<K, V> entry = removeEntry(key);
666: if (entry != null) {
667: return entry.value;
668: }
669: return null;
670: }
671:
672: final void removeEntry(Entry<K, V> entry) {
673: int index = entry.origKeyHash & (elementData.length - 1);
674: Entry<K, V> m = elementData[index];
675: if (m == entry) {
676: elementData[index] = entry.next;
677: } else {
678: while (m.next != entry && m.next != null) {
679: m = m.next;
680: }
681: m.next = entry.next;
682:
683: }
684: modCount++;
685: elementCount--;
686: }
687:
688: final Entry<K, V> removeEntry(Object key) {
689: int index = 0;
690: Entry<K, V> entry;
691: Entry<K, V> last = null;
692: if (key != null) {
693: int hash = key.hashCode();
694: index = hash & (elementData.length - 1);
695: entry = elementData[index];
696: while (entry != null
697: && !(entry.origKeyHash == hash && key
698: .equals(entry.key))) {
699: last = entry;
700: entry = entry.next;
701: }
702: } else {
703: entry = elementData[0];
704: while (entry != null && entry.key != null) {
705: last = entry;
706: entry = entry.next;
707: }
708: }
709: if (entry == null) {
710: return null;
711: }
712: if (last == null) {
713: elementData[index] = entry.next;
714: } else {
715: last.next = entry.next;
716: }
717: modCount++;
718: elementCount--;
719: return entry;
720: }
721:
722: /**
723: * Answers the number of mappings in this HashMap.
724: *
725: * @return the number of mappings in this HashMap
726: */
727: @Override
728: public int size() {
729: return elementCount;
730: }
731:
732: /**
733: * Answers a Collection of the values contained in this HashMap. The
734: * collection is backed by this HashMap so changes to one are reflected by
735: * the other. The collection does not support adding.
736: *
737: * @return a Collection of the values
738: */
739: @Override
740: public Collection<V> values() {
741: if (valuesCollection == null) {
742: valuesCollection = new AbstractCollection<V>() {
743: @Override
744: public boolean contains(Object object) {
745: return containsValue(object);
746: }
747:
748: @Override
749: public int size() {
750: return HashMap.this .size();
751: }
752:
753: @Override
754: public void clear() {
755: HashMap.this .clear();
756: }
757:
758: @Override
759: public Iterator<V> iterator() {
760: return new ValueIterator<K, V>(HashMap.this );
761: }
762: };
763: }
764: return valuesCollection;
765: }
766:
767: private void writeObject(ObjectOutputStream stream)
768: throws IOException {
769: stream.defaultWriteObject();
770: stream.writeInt(elementData.length);
771: stream.writeInt(elementCount);
772: Iterator<?> iterator = entrySet().iterator();
773: while (iterator.hasNext()) {
774: Entry<?, ?> entry = (Entry<?, ?>) iterator.next();
775: stream.writeObject(entry.key);
776: stream.writeObject(entry.value);
777: entry = entry.next;
778: }
779: }
780:
781: @SuppressWarnings("unchecked")
782: private void readObject(ObjectInputStream stream)
783: throws IOException, ClassNotFoundException {
784: stream.defaultReadObject();
785: int length = stream.readInt();
786: elementData = newElementArray(length);
787: elementCount = stream.readInt();
788: for (int i = elementCount; --i >= 0;) {
789: K key = (K) stream.readObject();
790: int index = (null == key) ? 0
791: : (key.hashCode() & (length - 1));
792: createEntry(key, index, (V) stream.readObject());
793: }
794: }
795:
796: }
|