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: * IdentityHashMap
027: *
028: * This is a variant on HashMap which tests equality by reference instead of by
029: * value. Basically, keys and values are compared for equality by checking if
030: * their references are equal rather than by calling the "equals" function.
031: *
032: * IdentityHashMap uses open addressing (linear probing in particular) for
033: * collision resolution. This is different from HashMap which uses Chaining.
034: *
035: * Like HashMap, IdentityHashMap is not thread safe, so access by multiple
036: * threads must be synchronized by an external mechanism such as
037: * Collections.synchronizedMap.
038: *
039: * @since 1.4
040: */
041: public class IdentityHashMap<K, V> extends AbstractMap<K, V> implements
042: Map<K, V>, Serializable, Cloneable {
043:
044: private static final long serialVersionUID = 8188218128353913216L;
045:
046: /*
047: * The internal data structure to hold key value pairs This array holds keys
048: * and values in an alternating fashion.
049: */
050: transient Object[] elementData;
051:
052: /* Actual number of key-value pairs. */
053: int size;
054:
055: /*
056: * maximum number of elements that can be put in this map before having to
057: * rehash.
058: */
059: transient int threshold;
060:
061: /*
062: * default threshold value that an IdentityHashMap created using the default
063: * constructor would have.
064: */
065: private static final int DEFAULT_MAX_SIZE = 21;
066:
067: /* Default load factor of 0.75; */
068: private static final int loadFactor = 7500;
069:
070: /*
071: * modification count, to keep track of structural modifications between the
072: * IdentityHashMap and the iterator
073: */
074: transient int modCount = 0;
075:
076: /*
077: * Object used to represent null keys and values. This is used to
078: * differentiate a literal 'null' key value pair from an empty spot in the
079: * map.
080: */
081: private static final Object NULL_OBJECT = new Object(); //$NON-LOCK-1$
082:
083: static class IdentityHashMapEntry<K, V> extends MapEntry<K, V> {
084: IdentityHashMapEntry(K theKey, V theValue) {
085: super (theKey, theValue);
086: }
087:
088: @Override
089: public Object clone() {
090: return super .clone();
091: }
092:
093: @Override
094: public boolean equals(Object object) {
095: if (this == object) {
096: return true;
097: }
098: if (object instanceof Map.Entry) {
099: Map.Entry<?, ?> entry = (Map.Entry) object;
100: return (key == entry.getKey())
101: && (value == entry.getValue());
102: }
103: return false;
104: }
105:
106: @Override
107: public int hashCode() {
108: return System.identityHashCode(key)
109: ^ System.identityHashCode(value);
110: }
111:
112: @Override
113: public String toString() {
114: return key + "=" + value; //$NON-NLS-1$
115: }
116: }
117:
118: static class IdentityHashMapIterator<E, KT, VT> implements
119: Iterator<E> {
120: private int position = 0; // the current position
121:
122: // the position of the entry that was last returned from next()
123: private int lastPosition = 0;
124:
125: final IdentityHashMap<KT, VT> associatedMap;
126:
127: int expectedModCount;
128:
129: final MapEntry.Type<E, KT, VT> type;
130:
131: boolean canRemove = false;
132:
133: IdentityHashMapIterator(MapEntry.Type<E, KT, VT> value,
134: IdentityHashMap<KT, VT> hm) {
135: associatedMap = hm;
136: type = value;
137: expectedModCount = hm.modCount;
138: }
139:
140: public boolean hasNext() {
141: while (position < associatedMap.elementData.length) {
142: // if this is an empty spot, go to the next one
143: if (associatedMap.elementData[position] == null) {
144: position += 2;
145: } else {
146: return true;
147: }
148: }
149: return false;
150: }
151:
152: void checkConcurrentMod()
153: throws ConcurrentModificationException {
154: if (expectedModCount != associatedMap.modCount) {
155: throw new ConcurrentModificationException();
156: }
157: }
158:
159: public E next() {
160: checkConcurrentMod();
161: if (!hasNext()) {
162: throw new NoSuchElementException();
163: }
164:
165: IdentityHashMapEntry<KT, VT> result = associatedMap
166: .getEntry(position);
167: lastPosition = position;
168: position += 2;
169:
170: canRemove = true;
171: return type.get(result);
172: }
173:
174: public void remove() {
175: checkConcurrentMod();
176: if (!canRemove) {
177: throw new IllegalStateException();
178: }
179:
180: canRemove = false;
181: associatedMap
182: .remove(associatedMap.elementData[lastPosition]);
183: position = lastPosition;
184: expectedModCount++;
185: }
186: }
187:
188: static class IdentityHashMapEntrySet<KT, VT> extends
189: AbstractSet<Map.Entry<KT, VT>> {
190: private final IdentityHashMap<KT, VT> associatedMap;
191:
192: public IdentityHashMapEntrySet(IdentityHashMap<KT, VT> hm) {
193: associatedMap = hm;
194: }
195:
196: IdentityHashMap<KT, VT> hashMap() {
197: return associatedMap;
198: }
199:
200: @Override
201: public int size() {
202: return associatedMap.size;
203: }
204:
205: @Override
206: public void clear() {
207: associatedMap.clear();
208: }
209:
210: @Override
211: public boolean remove(Object object) {
212: if (contains(object)) {
213: associatedMap.remove(((Map.Entry) object).getKey());
214: return true;
215: }
216: return false;
217: }
218:
219: @Override
220: public boolean contains(Object object) {
221: if (object instanceof Map.Entry) {
222: IdentityHashMapEntry<?, ?> entry = associatedMap
223: .getEntry(((Map.Entry) object).getKey());
224: // we must call equals on the entry obtained from "this"
225: return entry != null && entry.equals(object);
226: }
227: return false;
228: }
229:
230: @Override
231: public Iterator<Map.Entry<KT, VT>> iterator() {
232: return new IdentityHashMapIterator<Map.Entry<KT, VT>, KT, VT>(
233: new MapEntry.Type<Map.Entry<KT, VT>, KT, VT>() {
234: public Map.Entry<KT, VT> get(
235: MapEntry<KT, VT> entry) {
236: return entry;
237: }
238: }, associatedMap);
239: }
240: }
241:
242: /**
243: * Create an IdentityHashMap with default maximum size
244: */
245: public IdentityHashMap() {
246: this (DEFAULT_MAX_SIZE);
247: }
248:
249: /**
250: * Create an IdentityHashMap with the given maximum size parameter
251: *
252: * @param maxSize
253: * The estimated maximum number of entries that will be put in
254: * this map.
255: */
256: public IdentityHashMap(int maxSize) {
257: if (maxSize >= 0) {
258: this .size = 0;
259: threshold = getThreshold(maxSize);
260: elementData = newElementArray(computeElementArraySize());
261: } else {
262: throw new IllegalArgumentException();
263: }
264: }
265:
266: private int getThreshold(int maxSize) {
267: // assign the threshold to maxSize initially, this will change to a
268: // higher value if rehashing occurs.
269: return maxSize > 3 ? maxSize : 3;
270: }
271:
272: private int computeElementArraySize() {
273: return (int) (((long) threshold * 10000) / loadFactor) * 2;
274: }
275:
276: /**
277: * Create a new element array
278: *
279: * @param s
280: * the number of elements
281: * @return Reference to the element array
282: */
283: private Object[] newElementArray(int s) {
284: return new Object[s];
285: }
286:
287: /**
288: * Create an IdentityHashMap using the given Map as initial values.
289: *
290: * @param map
291: * A map of (key,value) pairs to copy into the IdentityHashMap
292: */
293: public IdentityHashMap(Map<? extends K, ? extends V> map) {
294: this (map.size() < 6 ? 11 : map.size() * 2);
295: putAllImpl(map);
296: }
297:
298: @SuppressWarnings("unchecked")
299: private V massageValue(Object value) {
300: return (V) ((value == NULL_OBJECT) ? null : value);
301: }
302:
303: /**
304: * Removes all elements from this Map, leaving it empty.
305: *
306: * @exception UnsupportedOperationException
307: * when removing from this Map is not supported
308: *
309: * @see #isEmpty
310: * @see #size
311: */
312: @Override
313: public void clear() {
314: size = 0;
315: for (int i = 0; i < elementData.length; i++) {
316: elementData[i] = null;
317: }
318: modCount++;
319: }
320:
321: /**
322: * Searches this Map for the specified key.
323: *
324: * @param key
325: * the object to search for
326: * @return true if <code>key</code> is a key of this Map, false otherwise
327: */
328: @Override
329: public boolean containsKey(Object key) {
330: if (key == null) {
331: key = NULL_OBJECT;
332: }
333:
334: int index = findIndex(key, elementData);
335: return elementData[index] == key;
336: }
337:
338: /**
339: * Searches this Map for the specified value.
340: *
341: *
342: * @param value
343: * the object to search for
344: * @return true if <code>value</code> is a value of this Map, false
345: * otherwise
346: */
347: @Override
348: public boolean containsValue(Object value) {
349: if (value == null) {
350: value = NULL_OBJECT;
351: }
352:
353: for (int i = 1; i < elementData.length; i = i + 2) {
354: if (elementData[i] == value) {
355: return true;
356: }
357: }
358: return false;
359: }
360:
361: /**
362: * Answers the value of the mapping with the specified key.
363: *
364: * @param key
365: * the key
366: * @return the value of the mapping with the specified key
367: */
368: @Override
369: public V get(Object key) {
370: if (key == null) {
371: key = NULL_OBJECT;
372: }
373:
374: int index = findIndex(key, elementData);
375:
376: if (elementData[index] == key) {
377: Object result = elementData[index + 1];
378: return massageValue(result);
379: }
380:
381: return null;
382: }
383:
384: private IdentityHashMapEntry<K, V> getEntry(Object key) {
385: if (key == null) {
386: key = NULL_OBJECT;
387: }
388:
389: int index = findIndex(key, elementData);
390: if (elementData[index] == key) {
391: return getEntry(index);
392: }
393:
394: return null;
395: }
396:
397: /**
398: * Convenience method for getting the IdentityHashMapEntry without the
399: * NULL_OBJECT elements
400: */
401: @SuppressWarnings("unchecked")
402: private IdentityHashMapEntry<K, V> getEntry(int index) {
403: Object key = elementData[index];
404: Object value = elementData[index + 1];
405:
406: if (key == NULL_OBJECT) {
407: key = null;
408: }
409: if (value == NULL_OBJECT) {
410: value = null;
411: }
412:
413: return new IdentityHashMapEntry<K, V>((K) key, (V) value);
414: }
415:
416: /**
417: * Returns the index where the key is found at, or the index of the next
418: * empty spot if the key is not found in this table.
419: */
420: private int findIndex(Object key, Object[] array) {
421: int length = array.length;
422: int index = getModuloHash(key, length);
423: int last = (index + length - 2) % length;
424: while (index != last) {
425: if (array[index] == key || (array[index] == null)) {
426: /*
427: * Found the key, or the next empty spot (which means key is not
428: * in the table)
429: */
430: break;
431: }
432: index = (index + 2) % length;
433: }
434: return index;
435: }
436:
437: private int getModuloHash(Object key, int length) {
438: return ((System.identityHashCode(key) & 0x7FFFFFFF) % (length / 2)) * 2;
439: }
440:
441: /**
442: * Maps the specified key to the specified value.
443: *
444: * @param key
445: * the key
446: * @param value
447: * the value
448: * @return the value of any previous mapping with the specified key or null
449: * if there was no mapping
450: */
451: @Override
452: public V put(K key, V value) {
453: Object _key = key;
454: Object _value = value;
455: if (_key == null) {
456: _key = NULL_OBJECT;
457: }
458:
459: if (_value == null) {
460: _value = NULL_OBJECT;
461: }
462:
463: int index = findIndex(_key, elementData);
464:
465: // if the key doesn't exist in the table
466: if (elementData[index] != _key) {
467: modCount++;
468: if (++size > threshold) {
469: rehash();
470: index = findIndex(_key, elementData);
471: }
472:
473: // insert the key and assign the value to null initially
474: elementData[index] = _key;
475: elementData[index + 1] = null;
476: }
477:
478: // insert value to where it needs to go, return the old value
479: Object result = elementData[index + 1];
480: elementData[index + 1] = _value;
481:
482: return massageValue(result);
483: }
484:
485: /**
486: * Copies all the mappings in the given map to this map. These mappings will
487: * replace all mappings that this map had for any of the keys currently in
488: * the given map.
489: *
490: * @param map
491: * the Map to copy mappings from
492: * @throws NullPointerException
493: * if the given map is null
494: */
495: @Override
496: public void putAll(Map<? extends K, ? extends V> map) {
497: putAllImpl(map);
498: }
499:
500: private void rehash() {
501: int newlength = elementData.length << 1;
502: if (newlength == 0) {
503: newlength = 1;
504: }
505: Object[] newData = newElementArray(newlength);
506: for (int i = 0; i < elementData.length; i = i + 2) {
507: Object key = elementData[i];
508: if (key != null) {
509: // if not empty
510: int index = findIndex(key, newData);
511: newData[index] = key;
512: newData[index + 1] = elementData[i + 1];
513: }
514: }
515: elementData = newData;
516: computeMaxSize();
517: }
518:
519: private void computeMaxSize() {
520: threshold = (int) ((long) (elementData.length / 2) * loadFactor / 10000);
521: }
522:
523: /**
524: * Removes a mapping with the specified key from this IdentityHashMap.
525: *
526: * @param key
527: * the key of the mapping to remove
528: * @return the value of the removed mapping, or null if key is not a key in
529: * this Map
530: */
531: @Override
532: public V remove(Object key) {
533: if (key == null) {
534: key = NULL_OBJECT;
535: }
536:
537: boolean hashedOk;
538: int index, next, hash;
539: Object result, object;
540: index = next = findIndex(key, elementData);
541:
542: if (elementData[index] != key) {
543: return null;
544: }
545:
546: // store the value for this key
547: result = elementData[index + 1];
548:
549: // shift the following elements up if needed
550: // until we reach an empty spot
551: int length = elementData.length;
552: while (true) {
553: next = (next + 2) % length;
554: object = elementData[next];
555: if (object == null) {
556: break;
557: }
558:
559: hash = getModuloHash(object, length);
560: hashedOk = hash > index;
561: if (next < index) {
562: hashedOk = hashedOk || (hash <= next);
563: } else {
564: hashedOk = hashedOk && (hash <= next);
565: }
566: if (!hashedOk) {
567: elementData[index] = object;
568: elementData[index + 1] = elementData[next + 1];
569: index = next;
570: }
571: }
572:
573: size--;
574: modCount++;
575:
576: // clear both the key and the value
577: elementData[index] = null;
578: elementData[index + 1] = null;
579:
580: return massageValue(result);
581: }
582:
583: /**
584: * Answers a Set of the mappings contained in this IdentityHashMap. Each
585: * element in the set is a Map.Entry. The set is backed by this Map so
586: * changes to one are reflected by the other. The set does not support
587: * adding.
588: *
589: * @return a Set of the mappings
590: */
591: @Override
592: public Set<Map.Entry<K, V>> entrySet() {
593: return new IdentityHashMapEntrySet<K, V>(this );
594: }
595:
596: /**
597: * Answers a Set of the keys contained in this IdentityHashMap. The set is
598: * backed by this IdentityHashMap so changes to one are reflected by the
599: * other. The set does not support adding.
600: *
601: * @return a Set of the keys
602: */
603: @Override
604: public Set<K> keySet() {
605: if (keySet == null) {
606: keySet = new AbstractSet<K>() {
607: @Override
608: public boolean contains(Object object) {
609: return containsKey(object);
610: }
611:
612: @Override
613: public int size() {
614: return IdentityHashMap.this .size();
615: }
616:
617: @Override
618: public void clear() {
619: IdentityHashMap.this .clear();
620: }
621:
622: @Override
623: public boolean remove(Object key) {
624: if (containsKey(key)) {
625: IdentityHashMap.this .remove(key);
626: return true;
627: }
628: return false;
629: }
630:
631: @Override
632: public Iterator<K> iterator() {
633: return new IdentityHashMapIterator<K, K, V>(
634: new MapEntry.Type<K, K, V>() {
635: public K get(MapEntry<K, V> entry) {
636: return entry.key;
637: }
638: }, IdentityHashMap.this );
639: }
640: };
641: }
642: return keySet;
643: }
644:
645: /**
646: * Answers a Collection of the values contained in this IdentityHashMap. The
647: * collection is backed by this IdentityHashMap so changes to one are
648: * reflected by the other. The collection does not support adding.
649: *
650: * @return a Collection of the values
651: */
652: @Override
653: public Collection<V> values() {
654: if (valuesCollection == null) {
655: valuesCollection = new AbstractCollection<V>() {
656: @Override
657: public boolean contains(Object object) {
658: return containsValue(object);
659: }
660:
661: @Override
662: public int size() {
663: return IdentityHashMap.this .size();
664: }
665:
666: @Override
667: public void clear() {
668: IdentityHashMap.this .clear();
669: }
670:
671: @Override
672: public Iterator<V> iterator() {
673: return new IdentityHashMapIterator<V, K, V>(
674: new MapEntry.Type<V, K, V>() {
675: public V get(MapEntry<K, V> entry) {
676: return entry.value;
677: }
678: }, IdentityHashMap.this );
679: }
680:
681: @Override
682: public boolean remove(Object object) {
683: Iterator<?> it = iterator();
684: while (it.hasNext()) {
685: if (object == it.next()) {
686: it.remove();
687: return true;
688: }
689: }
690: return false;
691: }
692: };
693: }
694: return valuesCollection;
695: }
696:
697: /**
698: * Compares this map with other objects. This map is equal to another map is
699: * it represents the same set of mappings. With this map, two mappings are
700: * the same if both the key and the value are equal by reference.
701: *
702: * When compared with a map that is not an IdentityHashMap, the equals
703: * method is not necessarily symmetric (a.equals(b) implies b.equals(a)) nor
704: * transitive (a.equals(b) and b.equals(c) implies a.equals(c)).
705: *
706: * @return whether the argument object is equal to this object
707: */
708: @Override
709: public boolean equals(Object object) {
710: /*
711: * We need to override the equals method in AbstractMap because
712: * AbstractMap.equals will call ((Map) object).entrySet().contains() to
713: * determine equality of the entries, so it will defer to the argument
714: * for comparison, meaning that reference-based comparison will not take
715: * place. We must ensure that all comparison is implemented by methods
716: * in this class (or in one of our inner classes) for reference-based
717: * comparison to take place.
718: */
719: if (this == object) {
720: return true;
721: }
722: if (object instanceof Map) {
723: Map<?, ?> map = (Map) object;
724: if (size() != map.size()) {
725: return false;
726: }
727:
728: Set<Map.Entry<K, V>> set = entrySet();
729: // ensure we use the equals method of the set created by "this"
730: return set.equals(map.entrySet());
731: }
732: return false;
733: }
734:
735: /**
736: * Answers a new IdentityHashMap with the same mappings and size as this
737: * one.
738: *
739: * @return a shallow copy of this IdentityHashMap
740: *
741: * @see java.lang.Cloneable
742: */
743: @Override
744: public Object clone() {
745: try {
746: return super .clone();
747: } catch (CloneNotSupportedException e) {
748: return null;
749: }
750: }
751:
752: /**
753: * Answers if this IdentityHashMap has no elements, a size of zero.
754: *
755: * @return true if this IdentityHashMap has no elements, false otherwise
756: *
757: * @see #size
758: */
759: @Override
760: public boolean isEmpty() {
761: return size == 0;
762: }
763:
764: /**
765: * Answers the number of mappings in this IdentityHashMap.
766: *
767: * @return the number of mappings in this IdentityHashMap
768: */
769: @Override
770: public int size() {
771: return size;
772: }
773:
774: private void writeObject(ObjectOutputStream stream)
775: throws IOException {
776: stream.defaultWriteObject();
777: stream.writeInt(size);
778: Iterator<?> iterator = entrySet().iterator();
779: while (iterator.hasNext()) {
780: MapEntry<?, ?> entry = (MapEntry) iterator.next();
781: stream.writeObject(entry.key);
782: stream.writeObject(entry.value);
783: }
784: }
785:
786: @SuppressWarnings("unchecked")
787: private void readObject(ObjectInputStream stream)
788: throws IOException, ClassNotFoundException {
789: stream.defaultReadObject();
790: int savedSize = stream.readInt();
791: threshold = getThreshold(DEFAULT_MAX_SIZE);
792: elementData = newElementArray(computeElementArraySize());
793: for (int i = savedSize; --i >= 0;) {
794: K key = (K) stream.readObject();
795: put(key, (V) stream.readObject());
796: }
797: size = savedSize;
798: }
799:
800: private void putAllImpl(Map<? extends K, ? extends V> map) {
801: if (map.entrySet() != null) {
802: super.putAll(map);
803: }
804: }
805: }
|