112 *
113 * @author Arthur van Hoff
114 * @author Josh Bloch
115 * @author Neal Gafter
116 * @see Object#equals(java.lang.Object)
117 * @see Object#hashCode()
118 * @see Hashtable#rehash()
119 * @see Collection
120 * @see Map
121 * @see HashMap
122 * @see TreeMap
123 * @since JDK1.0
124 */
125 public class Hashtable<K,V>
126 extends Dictionary<K,V>
127 implements Map<K,V>, Cloneable, java.io.Serializable {
128
129 /**
130 * The hash table data.
131 */
132 private transient Entry[] table;
133
134 /**
135 * The total number of entries in the hash table.
136 */
137 private transient int count;
138
139 /**
140 * The table is rehashed when its size exceeds this threshold. (The
141 * value of this field is (int)(capacity * loadFactor).)
142 *
143 * @serial
144 */
145 private int threshold;
146
147 /**
148 * The load factor for the hashtable.
149 *
150 * @serial
151 */
152 private float loadFactor;
271 * Tests if some key maps into the specified value in this hashtable.
272 * This operation is more expensive than the {@link #containsKey
273 * containsKey} method.
274 *
275 * <p>Note that this method is identical in functionality to
276 * {@link #containsValue containsValue}, (which is part of the
277 * {@link Map} interface in the collections framework).
278 *
279 * @param value a value to search for
280 * @return <code>true</code> if and only if some key maps to the
281 * <code>value</code> argument in this hashtable as
282 * determined by the <tt>equals</tt> method;
283 * <code>false</code> otherwise.
284 * @exception NullPointerException if the value is <code>null</code>
285 */
286 public synchronized boolean contains(Object value) {
287 if (value == null) {
288 throw new NullPointerException();
289 }
290
291 Entry tab[] = table;
292 for (int i = tab.length ; i-- > 0 ;) {
293 for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {
294 if (e.value.equals(value)) {
295 return true;
296 }
297 }
298 }
299 return false;
300 }
301
302 /**
303 * Returns true if this hashtable maps one or more keys to this value.
304 *
305 * <p>Note that this method is identical in functionality to {@link
306 * #contains contains} (which predates the {@link Map} interface).
307 *
308 * @param value value whose presence in this hashtable is to be tested
309 * @return <tt>true</tt> if this map maps one or more keys to the
310 * specified value
311 * @throws NullPointerException if the value is <code>null</code>
312 * @since 1.2
313 */
314 public boolean containsValue(Object value) {
315 return contains(value);
316 }
317
318 /**
319 * Tests if the specified object is a key in this hashtable.
320 *
321 * @param key possible key
322 * @return <code>true</code> if and only if the specified object
323 * is a key in this hashtable, as determined by the
324 * <tt>equals</tt> method; <code>false</code> otherwise.
325 * @throws NullPointerException if the key is <code>null</code>
326 * @see #contains(Object)
327 */
328 public synchronized boolean containsKey(Object key) {
329 Entry tab[] = table;
330 int hash = key.hashCode();
331 int index = (hash & 0x7FFFFFFF) % tab.length;
332 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
333 if ((e.hash == hash) && e.key.equals(key)) {
334 return true;
335 }
336 }
337 return false;
338 }
339
340 /**
341 * Returns the value to which the specified key is mapped,
342 * or {@code null} if this map contains no mapping for the key.
343 *
344 * <p>More formally, if this map contains a mapping from a key
345 * {@code k} to a value {@code v} such that {@code (key.equals(k))},
346 * then this method returns {@code v}; otherwise it returns
347 * {@code null}. (There can be at most one such mapping.)
348 *
349 * @param key the key whose associated value is to be returned
350 * @return the value to which the specified key is mapped, or
351 * {@code null} if this map contains no mapping for the key
352 * @throws NullPointerException if the specified key is null
353 * @see #put(Object, Object)
354 */
355 public synchronized V get(Object key) {
356 Entry tab[] = table;
357 int hash = key.hashCode();
358 int index = (hash & 0x7FFFFFFF) % tab.length;
359 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
360 if ((e.hash == hash) && e.key.equals(key)) {
361 return e.value;
362 }
363 }
364 return null;
365 }
366
367 /**
368 * The maximum size of array to allocate.
369 * Some VMs reserve some header words in an array.
370 * Attempts to allocate larger arrays may result in
371 * OutOfMemoryError: Requested array size exceeds VM limit
372 */
373 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
374
375 /**
376 * Increases the capacity of and internally reorganizes this
377 * hashtable, in order to accommodate and access its entries more
378 * efficiently. This method is called automatically when the
379 * number of keys in the hashtable exceeds this hashtable's capacity
380 * and load factor.
381 */
382 protected void rehash() {
383 int oldCapacity = table.length;
384 Entry[] oldMap = table;
385
386 // overflow-conscious code
387 int newCapacity = (oldCapacity << 1) + 1;
388 if (newCapacity - MAX_ARRAY_SIZE > 0) {
389 if (oldCapacity == MAX_ARRAY_SIZE)
390 // Keep running with MAX_ARRAY_SIZE buckets
391 return;
392 newCapacity = MAX_ARRAY_SIZE;
393 }
394 Entry[] newMap = new Entry[newCapacity];
395
396 modCount++;
397 threshold = (int)(newCapacity * loadFactor);
398 table = newMap;
399
400 for (int i = oldCapacity ; i-- > 0 ;) {
401 for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
402 Entry<K,V> e = old;
403 old = old.next;
404
405 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
406 e.next = newMap[index];
407 newMap[index] = e;
408 }
409 }
410 }
411
412 /**
413 * Maps the specified <code>key</code> to the specified
414 * <code>value</code> in this hashtable. Neither the key nor the
415 * value can be <code>null</code>. <p>
416 *
417 * The value can be retrieved by calling the <code>get</code> method
418 * with a key that is equal to the original key.
419 *
420 * @param key the hashtable key
421 * @param value the value
422 * @return the previous value of the specified key in this hashtable,
423 * or <code>null</code> if it did not have one
424 * @exception NullPointerException if the key or value is
425 * <code>null</code>
426 * @see Object#equals(Object)
427 * @see #get(Object)
428 */
429 public synchronized V put(K key, V value) {
430 // Make sure the value is not null
431 if (value == null) {
432 throw new NullPointerException();
433 }
434
435 // Makes sure the key is not already in the hashtable.
436 Entry tab[] = table;
437 int hash = key.hashCode();
438 int index = (hash & 0x7FFFFFFF) % tab.length;
439 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
440 if ((e.hash == hash) && e.key.equals(key)) {
441 V old = e.value;
442 e.value = value;
443 return old;
444 }
445 }
446
447 modCount++;
448 if (count >= threshold) {
449 // Rehash the table if the threshold is exceeded
450 rehash();
451
452 tab = table;
453 index = (hash & 0x7FFFFFFF) % tab.length;
454 }
455
456 // Creates the new entry.
457 Entry<K,V> e = tab[index];
458 tab[index] = new Entry<>(hash, key, value, e);
459 count++;
460 return null;
461 }
462
463 /**
464 * Removes the key (and its corresponding value) from this
465 * hashtable. This method does nothing if the key is not in the hashtable.
466 *
467 * @param key the key that needs to be removed
468 * @return the value to which the key had been mapped in this hashtable,
469 * or <code>null</code> if the key did not have a mapping
470 * @throws NullPointerException if the key is <code>null</code>
471 */
472 public synchronized V remove(Object key) {
473 Entry tab[] = table;
474 int hash = key.hashCode();
475 int index = (hash & 0x7FFFFFFF) % tab.length;
476 for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
477 if ((e.hash == hash) && e.key.equals(key)) {
478 modCount++;
479 if (prev != null) {
480 prev.next = e.next;
481 } else {
482 tab[index] = e.next;
483 }
484 count--;
485 V oldValue = e.value;
486 e.value = null;
487 return oldValue;
488 }
489 }
490 return null;
491 }
492
493 /**
494 * Copies all of the mappings from the specified map to this hashtable.
495 * These mappings will replace any mappings that this hashtable had for any
496 * of the keys currently in the specified map.
497 *
498 * @param t mappings to be stored in this map
499 * @throws NullPointerException if the specified map is null
500 * @since 1.2
501 */
502 public synchronized void putAll(Map<? extends K, ? extends V> t) {
503 for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
504 put(e.getKey(), e.getValue());
505 }
506
507 /**
508 * Clears this hashtable so that it contains no keys.
509 */
510 public synchronized void clear() {
511 Entry tab[] = table;
512 modCount++;
513 for (int index = tab.length; --index >= 0; )
514 tab[index] = null;
515 count = 0;
516 }
517
518 /**
519 * Creates a shallow copy of this hashtable. All the structure of the
520 * hashtable itself is copied, but the keys and values are not cloned.
521 * This is a relatively expensive operation.
522 *
523 * @return a clone of the hashtable
524 */
525 public synchronized Object clone() {
526 try {
527 Hashtable<K,V> t = (Hashtable<K,V>) super.clone();
528 t.table = new Entry[table.length];
529 for (int i = table.length ; i-- > 0 ; ) {
530 t.table[i] = (table[i] != null)
531 ? (Entry<K,V>) table[i].clone() : null;
532 }
533 t.keySet = null;
534 t.entrySet = null;
535 t.values = null;
536 t.modCount = 0;
537 return t;
538 } catch (CloneNotSupportedException e) {
539 // this shouldn't happen, since we are Cloneable
540 throw new InternalError(e);
541 }
542 }
543
544 /**
545 * Returns a string representation of this <tt>Hashtable</tt> object
546 * in the form of a set of entries, enclosed in braces and separated
547 * by the ASCII characters "<tt>, </tt>" (comma and space). Each
548 * entry is rendered as the key, an equals sign <tt>=</tt>, and the
549 * associated element, where the <tt>toString</tt> method is used to
550 * convert the key and element to strings.
551 *
658 * @since 1.2
659 */
660 public Set<Map.Entry<K,V>> entrySet() {
661 if (entrySet==null)
662 entrySet = Collections.synchronizedSet(new EntrySet(), this);
663 return entrySet;
664 }
665
666 private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
667 public Iterator<Map.Entry<K,V>> iterator() {
668 return getIterator(ENTRIES);
669 }
670
671 public boolean add(Map.Entry<K,V> o) {
672 return super.add(o);
673 }
674
675 public boolean contains(Object o) {
676 if (!(o instanceof Map.Entry))
677 return false;
678 Map.Entry entry = (Map.Entry)o;
679 Object key = entry.getKey();
680 Entry[] tab = table;
681 int hash = key.hashCode();
682 int index = (hash & 0x7FFFFFFF) % tab.length;
683
684 for (Entry e = tab[index]; e != null; e = e.next)
685 if (e.hash==hash && e.equals(entry))
686 return true;
687 return false;
688 }
689
690 public boolean remove(Object o) {
691 if (!(o instanceof Map.Entry))
692 return false;
693 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
694 K key = entry.getKey();
695 Entry[] tab = table;
696 int hash = key.hashCode();
697 int index = (hash & 0x7FFFFFFF) % tab.length;
698
699 for (Entry<K,V> e = tab[index], prev = null; e != null;
700 prev = e, e = e.next) {
701 if (e.hash==hash && e.equals(entry)) {
702 modCount++;
703 if (prev != null)
704 prev.next = e.next;
705 else
706 tab[index] = e.next;
707
708 count--;
709 e.value = null;
710 return true;
711 }
712 }
713 return false;
714 }
715
716 public int size() {
717 return count;
718 }
719
759 }
760 }
761
762 // Comparison and hashing
763
764 /**
765 * Compares the specified Object with this Map for equality,
766 * as per the definition in the Map interface.
767 *
768 * @param o object to be compared for equality with this hashtable
769 * @return true if the specified Object is equal to this Map
770 * @see Map#equals(Object)
771 * @since 1.2
772 */
773 public synchronized boolean equals(Object o) {
774 if (o == this)
775 return true;
776
777 if (!(o instanceof Map))
778 return false;
779 Map<K,V> t = (Map<K,V>) o;
780 if (t.size() != size())
781 return false;
782
783 try {
784 Iterator<Map.Entry<K,V>> i = entrySet().iterator();
785 while (i.hasNext()) {
786 Map.Entry<K,V> e = i.next();
787 K key = e.getKey();
788 V value = e.getValue();
789 if (value == null) {
790 if (!(t.get(key)==null && t.containsKey(key)))
791 return false;
792 } else {
793 if (!value.equals(t.get(key)))
794 return false;
795 }
796 }
797 } catch (ClassCastException unused) {
798 return false;
799 } catch (NullPointerException unused) {
809 *
810 * @see Map#hashCode()
811 * @since 1.2
812 */
813 public synchronized int hashCode() {
814 /*
815 * This code detects the recursion caused by computing the hash code
816 * of a self-referential hash table and prevents the stack overflow
817 * that would otherwise result. This allows certain 1.1-era
818 * applets with self-referential hash tables to work. This code
819 * abuses the loadFactor field to do double-duty as a hashCode
820 * in progress flag, so as not to worsen the space performance.
821 * A negative load factor indicates that hash code computation is
822 * in progress.
823 */
824 int h = 0;
825 if (count == 0 || loadFactor < 0)
826 return h; // Returns zero
827
828 loadFactor = -loadFactor; // Mark hashCode computation in progress
829 Entry[] tab = table;
830 for (int i = 0; i < tab.length; i++)
831 for (Entry e = tab[i]; e != null; e = e.next)
832 h += e.key.hashCode() ^ e.value.hashCode();
833 loadFactor = -loadFactor; // Mark hashCode computation complete
834
835 return h;
836 }
837
838 /**
839 * Save the state of the Hashtable to a stream (i.e., serialize it).
840 *
841 * @serialData The <i>capacity</i> of the Hashtable (the length of the
842 * bucket array) is emitted (int), followed by the
843 * <i>size</i> of the Hashtable (the number of key-value
844 * mappings), followed by the key (Object) and value (Object)
845 * for each key-value mapping represented by the Hashtable
846 * The key-value mappings are emitted in no particular order.
847 */
848 private void writeObject(java.io.ObjectOutputStream s)
849 throws IOException {
850 Entry<Object, Object> entryStack = null;
851
852 synchronized (this) {
853 // Write out the length, threshold, loadfactor
854 s.defaultWriteObject();
855
856 // Write out length, count of elements
857 s.writeInt(table.length);
858 s.writeInt(count);
859
860 // Stack copies of the entries in the table
861 for (int index = 0; index < table.length; index++) {
862 Entry entry = table[index];
863
864 while (entry != null) {
865 entryStack =
866 new Entry<>(0, entry.key, entry.value, entryStack);
867 entry = entry.next;
868 }
869 }
870 }
871
872 // Write out the key/value objects from the stacked entries
873 while (entryStack != null) {
874 s.writeObject(entryStack.key);
875 s.writeObject(entryStack.value);
876 entryStack = entryStack.next;
877 }
878 }
879
880 /**
881 * Reconstitute the Hashtable from a stream (i.e., deserialize it).
882 */
883 private void readObject(java.io.ObjectInputStream s)
884 throws IOException, ClassNotFoundException
885 {
886 // Read in the length, threshold, and loadfactor
887 s.defaultReadObject();
888
889 // Read the original length of the array and number of elements
890 int origlength = s.readInt();
891 int elements = s.readInt();
892
893 // Compute new size with a bit of room 5% to grow but
894 // no larger than the original size. Make the length
895 // odd if it's large enough, this helps distribute the entries.
896 // Guard against the length ending up zero, that's not valid.
897 int length = (int)(elements * loadFactor) + (elements / 20) + 3;
898 if (length > elements && (length & 1) == 0)
899 length--;
900 if (origlength > 0 && length > origlength)
901 length = origlength;
902
903 Entry[] table = new Entry[length];
904 count = 0;
905
906 // Read the number of elements and then all the key/value objects
907 for (; elements > 0; elements--) {
908 K key = (K)s.readObject();
909 V value = (V)s.readObject();
910 // synch could be eliminated for performance
911 reconstitutionPut(table, key, value);
912 }
913 this.table = table;
914 }
915
916 /**
917 * The put method used by readObject. This is provided because put
918 * is overridable and should not be called in readObject since the
919 * subclass will not yet be initialized.
920 *
921 * <p>This differs from the regular put method in several ways. No
922 * checking for rehashing is necessary since the number of elements
923 * initially in the table is known. The modCount is not incremented
924 * because we are creating a new instance. Also, no return value
925 * is needed.
926 */
927 private void reconstitutionPut(Entry[] tab, K key, V value)
928 throws StreamCorruptedException
929 {
930 if (value == null) {
931 throw new java.io.StreamCorruptedException();
932 }
933 // Makes sure the key is not already in the hashtable.
934 // This should not happen in deserialized version.
935 int hash = key.hashCode();
936 int index = (hash & 0x7FFFFFFF) % tab.length;
937 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
938 if ((e.hash == hash) && e.key.equals(key)) {
939 throw new java.io.StreamCorruptedException();
940 }
941 }
942 // Creates the new entry.
943 Entry<K,V> e = tab[index];
944 tab[index] = new Entry<>(hash, key, value, e);
945 count++;
946 }
947
948 /**
949 * Hashtable collision list.
950 */
951 private static class Entry<K,V> implements Map.Entry<K,V> {
952 int hash;
953 K key;
954 V value;
955 Entry<K,V> next;
956
957 protected Entry(int hash, K key, V value, Entry<K,V> next) {
958 this.hash = hash;
959 this.key = key;
960 this.value = value;
961 this.next = next;
962 }
963
964 protected Object clone() {
965 return new Entry<>(hash, key, value,
966 (next==null ? null : (Entry<K,V>) next.clone()));
967 }
968
969 // Map.Entry Ops
970
971 public K getKey() {
972 return key;
973 }
974
975 public V getValue() {
976 return value;
977 }
978
979 public V setValue(V value) {
980 if (value == null)
981 throw new NullPointerException();
982
983 V oldValue = this.value;
984 this.value = value;
985 return oldValue;
986 }
987
988 public boolean equals(Object o) {
989 if (!(o instanceof Map.Entry))
990 return false;
991 Map.Entry e = (Map.Entry)o;
992
993 return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
994 (value==null ? e.getValue()==null : value.equals(e.getValue()));
995 }
996
997 public int hashCode() {
998 return hash ^ (value==null ? 0 : value.hashCode());
999 }
1000
1001 public String toString() {
1002 return key.toString()+"="+value.toString();
1003 }
1004 }
1005
1006 // Types of Enumerations/Iterations
1007 private static final int KEYS = 0;
1008 private static final int VALUES = 1;
1009 private static final int ENTRIES = 2;
1010
1011 /**
1012 * A hashtable enumerator class. This class implements both the
1013 * Enumeration and Iterator interfaces, but individual instances
1014 * can be created with the Iterator methods disabled. This is necessary
1015 * to avoid unintentionally increasing the capabilities granted a user
1016 * by passing an Enumeration.
1017 */
1018 private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
1019 Entry[] table = Hashtable.this.table;
1020 int index = table.length;
1021 Entry<K,V> entry = null;
1022 Entry<K,V> lastReturned = null;
1023 int type;
1024
1025 /**
1026 * Indicates whether this Enumerator is serving as an Iterator
1027 * or an Enumeration. (true -> Iterator).
1028 */
1029 boolean iterator;
1030
1031 /**
1032 * The modCount value that the iterator believes that the backing
1033 * Hashtable should have. If this expectation is violated, the iterator
1034 * has detected concurrent modification.
1035 */
1036 protected int expectedModCount = modCount;
1037
1038 Enumerator(int type, boolean iterator) {
1039 this.type = type;
1040 this.iterator = iterator;
1041 }
1042
1043 public boolean hasMoreElements() {
1044 Entry<K,V> e = entry;
1045 int i = index;
1046 Entry[] t = table;
1047 /* Use locals for faster loop iteration */
1048 while (e == null && i > 0) {
1049 e = t[--i];
1050 }
1051 entry = e;
1052 index = i;
1053 return e != null;
1054 }
1055
1056 public T nextElement() {
1057 Entry<K,V> et = entry;
1058 int i = index;
1059 Entry[] t = table;
1060 /* Use locals for faster loop iteration */
1061 while (et == null && i > 0) {
1062 et = t[--i];
1063 }
1064 entry = et;
1065 index = i;
1066 if (et != null) {
1067 Entry<K,V> e = lastReturned = entry;
1068 entry = e.next;
1069 return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
1070 }
1071 throw new NoSuchElementException("Hashtable Enumerator");
1072 }
1073
1074 // Iterator methods
1075 public boolean hasNext() {
1076 return hasMoreElements();
1077 }
1078
1079 public T next() {
1080 if (modCount != expectedModCount)
1081 throw new ConcurrentModificationException();
1082 return nextElement();
1083 }
1084
1085 public void remove() {
1086 if (!iterator)
1087 throw new UnsupportedOperationException();
1088 if (lastReturned == null)
1089 throw new IllegalStateException("Hashtable Enumerator");
1090 if (modCount != expectedModCount)
1091 throw new ConcurrentModificationException();
1092
1093 synchronized(Hashtable.this) {
1094 Entry[] tab = Hashtable.this.table;
1095 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
1096
1097 for (Entry<K,V> e = tab[index], prev = null; e != null;
1098 prev = e, e = e.next) {
1099 if (e == lastReturned) {
1100 modCount++;
1101 expectedModCount++;
1102 if (prev == null)
1103 tab[index] = e.next;
1104 else
1105 prev.next = e.next;
1106 count--;
1107 lastReturned = null;
1108 return;
1109 }
1110 }
1111 throw new ConcurrentModificationException();
1112 }
1113 }
1114 }
1115 }
|
112 *
113 * @author Arthur van Hoff
114 * @author Josh Bloch
115 * @author Neal Gafter
116 * @see Object#equals(java.lang.Object)
117 * @see Object#hashCode()
118 * @see Hashtable#rehash()
119 * @see Collection
120 * @see Map
121 * @see HashMap
122 * @see TreeMap
123 * @since JDK1.0
124 */
125 public class Hashtable<K,V>
126 extends Dictionary<K,V>
127 implements Map<K,V>, Cloneable, java.io.Serializable {
128
129 /**
130 * The hash table data.
131 */
132 private transient Entry<?,?>[] table;
133
134 /**
135 * The total number of entries in the hash table.
136 */
137 private transient int count;
138
139 /**
140 * The table is rehashed when its size exceeds this threshold. (The
141 * value of this field is (int)(capacity * loadFactor).)
142 *
143 * @serial
144 */
145 private int threshold;
146
147 /**
148 * The load factor for the hashtable.
149 *
150 * @serial
151 */
152 private float loadFactor;
271 * Tests if some key maps into the specified value in this hashtable.
272 * This operation is more expensive than the {@link #containsKey
273 * containsKey} method.
274 *
275 * <p>Note that this method is identical in functionality to
276 * {@link #containsValue containsValue}, (which is part of the
277 * {@link Map} interface in the collections framework).
278 *
279 * @param value a value to search for
280 * @return <code>true</code> if and only if some key maps to the
281 * <code>value</code> argument in this hashtable as
282 * determined by the <tt>equals</tt> method;
283 * <code>false</code> otherwise.
284 * @exception NullPointerException if the value is <code>null</code>
285 */
286 public synchronized boolean contains(Object value) {
287 if (value == null) {
288 throw new NullPointerException();
289 }
290
291 Entry<?,?> tab[] = table;
292 for (int i = tab.length ; i-- > 0 ;) {
293 for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {
294 if (e.value.equals(value)) {
295 return true;
296 }
297 }
298 }
299 return false;
300 }
301
302 /**
303 * Returns true if this hashtable maps one or more keys to this value.
304 *
305 * <p>Note that this method is identical in functionality to {@link
306 * #contains contains} (which predates the {@link Map} interface).
307 *
308 * @param value value whose presence in this hashtable is to be tested
309 * @return <tt>true</tt> if this map maps one or more keys to the
310 * specified value
311 * @throws NullPointerException if the value is <code>null</code>
312 * @since 1.2
313 */
314 public boolean containsValue(Object value) {
315 return contains(value);
316 }
317
318 /**
319 * Tests if the specified object is a key in this hashtable.
320 *
321 * @param key possible key
322 * @return <code>true</code> if and only if the specified object
323 * is a key in this hashtable, as determined by the
324 * <tt>equals</tt> method; <code>false</code> otherwise.
325 * @throws NullPointerException if the key is <code>null</code>
326 * @see #contains(Object)
327 */
328 public synchronized boolean containsKey(Object key) {
329 Entry<?,?> tab[] = table;
330 int hash = key.hashCode();
331 int index = (hash & 0x7FFFFFFF) % tab.length;
332 for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
333 if ((e.hash == hash) && e.key.equals(key)) {
334 return true;
335 }
336 }
337 return false;
338 }
339
340 /**
341 * Returns the value to which the specified key is mapped,
342 * or {@code null} if this map contains no mapping for the key.
343 *
344 * <p>More formally, if this map contains a mapping from a key
345 * {@code k} to a value {@code v} such that {@code (key.equals(k))},
346 * then this method returns {@code v}; otherwise it returns
347 * {@code null}. (There can be at most one such mapping.)
348 *
349 * @param key the key whose associated value is to be returned
350 * @return the value to which the specified key is mapped, or
351 * {@code null} if this map contains no mapping for the key
352 * @throws NullPointerException if the specified key is null
353 * @see #put(Object, Object)
354 */
355 public synchronized V get(Object key) {
356 Entry<?,?> tab[] = table;
357 int hash = key.hashCode();
358 int index = (hash & 0x7FFFFFFF) % tab.length;
359 for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
360 if ((e.hash == hash) && e.key.equals(key)) {
361 return (V)e.value;
362 }
363 }
364 return null;
365 }
366
367 /**
368 * The maximum size of array to allocate.
369 * Some VMs reserve some header words in an array.
370 * Attempts to allocate larger arrays may result in
371 * OutOfMemoryError: Requested array size exceeds VM limit
372 */
373 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
374
375 /**
376 * Increases the capacity of and internally reorganizes this
377 * hashtable, in order to accommodate and access its entries more
378 * efficiently. This method is called automatically when the
379 * number of keys in the hashtable exceeds this hashtable's capacity
380 * and load factor.
381 */
382 @SuppressWarnings("unchecked")
383 protected void rehash() {
384 int oldCapacity = table.length;
385 Entry<?,?>[] oldMap = table;
386
387 // overflow-conscious code
388 int newCapacity = (oldCapacity << 1) + 1;
389 if (newCapacity - MAX_ARRAY_SIZE > 0) {
390 if (oldCapacity == MAX_ARRAY_SIZE)
391 // Keep running with MAX_ARRAY_SIZE buckets
392 return;
393 newCapacity = MAX_ARRAY_SIZE;
394 }
395 Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
396
397 modCount++;
398 threshold = (int)(newCapacity * loadFactor);
399 table = newMap;
400
401 for (int i = oldCapacity ; i-- > 0 ;) {
402 for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
403 Entry<K,V> e = old;
404 old = old.next;
405
406 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
407 e.next = (Entry<K,V>)newMap[index];
408 newMap[index] = e;
409 }
410 }
411 }
412
413 /**
414 * Maps the specified <code>key</code> to the specified
415 * <code>value</code> in this hashtable. Neither the key nor the
416 * value can be <code>null</code>. <p>
417 *
418 * The value can be retrieved by calling the <code>get</code> method
419 * with a key that is equal to the original key.
420 *
421 * @param key the hashtable key
422 * @param value the value
423 * @return the previous value of the specified key in this hashtable,
424 * or <code>null</code> if it did not have one
425 * @exception NullPointerException if the key or value is
426 * <code>null</code>
427 * @see Object#equals(Object)
428 * @see #get(Object)
429 */
430 public synchronized V put(K key, V value) {
431 // Make sure the value is not null
432 if (value == null) {
433 throw new NullPointerException();
434 }
435
436 // Makes sure the key is not already in the hashtable.
437 Entry<?,?> tab[] = table;
438 int hash = key.hashCode();
439 int index = (hash & 0x7FFFFFFF) % tab.length;
440 for (@SuppressWarnings("unchecked")
441 Entry<K,V> e = (Entry<K,V>)tab[index] ; e != null ; e = e.next) {
442 if ((e.hash == hash) && e.key.equals(key)) {
443 V old = e.value;
444 e.value = value;
445 return old;
446 }
447 }
448
449 modCount++;
450 if (count >= threshold) {
451 // Rehash the table if the threshold is exceeded
452 rehash();
453
454 tab = table;
455 index = (hash & 0x7FFFFFFF) % tab.length;
456 }
457
458 // Creates the new entry.
459 @SuppressWarnings("unchecked")
460 Entry<K,V> e = (Entry<K,V>)tab[index];
461 tab[index] = new Entry<>(hash, key, value, e);
462 count++;
463 return null;
464 }
465
466 /**
467 * Removes the key (and its corresponding value) from this
468 * hashtable. This method does nothing if the key is not in the hashtable.
469 *
470 * @param key the key that needs to be removed
471 * @return the value to which the key had been mapped in this hashtable,
472 * or <code>null</code> if the key did not have a mapping
473 * @throws NullPointerException if the key is <code>null</code>
474 */
475 public synchronized V remove(Object key) {
476 Entry<?,?> tab[] = table;
477 int hash = key.hashCode();
478 int index = (hash & 0x7FFFFFFF) % tab.length;
479 for (@SuppressWarnings("unchecked")
480 Entry<K,V> e = (Entry<K,V>)tab[index], prev = null ; e != null ; prev = e, e = e.next) {
481 if ((e.hash == hash) && e.key.equals(key)) {
482 modCount++;
483 if (prev != null) {
484 prev.next = e.next;
485 } else {
486 tab[index] = e.next;
487 }
488 count--;
489 V oldValue = e.value;
490 e.value = null;
491 return oldValue;
492 }
493 }
494 return null;
495 }
496
497 /**
498 * Copies all of the mappings from the specified map to this hashtable.
499 * These mappings will replace any mappings that this hashtable had for any
500 * of the keys currently in the specified map.
501 *
502 * @param t mappings to be stored in this map
503 * @throws NullPointerException if the specified map is null
504 * @since 1.2
505 */
506 public synchronized void putAll(Map<? extends K, ? extends V> t) {
507 for (Map.Entry<? extends K, ? extends V> e : t.entrySet())
508 put(e.getKey(), e.getValue());
509 }
510
511 /**
512 * Clears this hashtable so that it contains no keys.
513 */
514 public synchronized void clear() {
515 Entry<?,?> tab[] = table;
516 modCount++;
517 for (int index = tab.length; --index >= 0; )
518 tab[index] = null;
519 count = 0;
520 }
521
522 /**
523 * Creates a shallow copy of this hashtable. All the structure of the
524 * hashtable itself is copied, but the keys and values are not cloned.
525 * This is a relatively expensive operation.
526 *
527 * @return a clone of the hashtable
528 */
529 public synchronized Object clone() {
530 try {
531 Hashtable<?,?> t = (Hashtable<?,?>)super.clone();
532 t.table = new Entry<?,?>[table.length];
533 for (int i = table.length ; i-- > 0 ; ) {
534 t.table[i] = (table[i] != null)
535 ? (Entry<?,?>) table[i].clone() : null;
536 }
537 t.keySet = null;
538 t.entrySet = null;
539 t.values = null;
540 t.modCount = 0;
541 return t;
542 } catch (CloneNotSupportedException e) {
543 // this shouldn't happen, since we are Cloneable
544 throw new InternalError(e);
545 }
546 }
547
548 /**
549 * Returns a string representation of this <tt>Hashtable</tt> object
550 * in the form of a set of entries, enclosed in braces and separated
551 * by the ASCII characters "<tt>, </tt>" (comma and space). Each
552 * entry is rendered as the key, an equals sign <tt>=</tt>, and the
553 * associated element, where the <tt>toString</tt> method is used to
554 * convert the key and element to strings.
555 *
662 * @since 1.2
663 */
664 public Set<Map.Entry<K,V>> entrySet() {
665 if (entrySet==null)
666 entrySet = Collections.synchronizedSet(new EntrySet(), this);
667 return entrySet;
668 }
669
670 private class EntrySet extends AbstractSet<Map.Entry<K,V>> {
671 public Iterator<Map.Entry<K,V>> iterator() {
672 return getIterator(ENTRIES);
673 }
674
675 public boolean add(Map.Entry<K,V> o) {
676 return super.add(o);
677 }
678
679 public boolean contains(Object o) {
680 if (!(o instanceof Map.Entry))
681 return false;
682 Map.Entry<?,?> entry = (Map.Entry<?,?>)o;
683 Object key = entry.getKey();
684 Entry<?,?>[] tab = table;
685 int hash = key.hashCode();
686 int index = (hash & 0x7FFFFFFF) % tab.length;
687
688 for (Entry<?,?> e = tab[index]; e != null; e = e.next)
689 if (e.hash==hash && e.equals(entry))
690 return true;
691 return false;
692 }
693
694 public boolean remove(Object o) {
695 if (!(o instanceof Map.Entry))
696 return false;
697 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
698 Object key = entry.getKey();
699 Entry<?,?>[] tab = table;
700 int hash = key.hashCode();
701 int index = (hash & 0x7FFFFFFF) % tab.length;
702
703 for (@SuppressWarnings("unchecked")
704 Entry<K,V> e = (Entry<K,V>)tab[index], prev = null; e != null;
705 prev = e, e = e.next) {
706 if (e.hash==hash && e.equals(entry)) {
707 modCount++;
708 if (prev != null)
709 prev.next = e.next;
710 else
711 tab[index] = e.next;
712
713 count--;
714 e.value = null;
715 return true;
716 }
717 }
718 return false;
719 }
720
721 public int size() {
722 return count;
723 }
724
764 }
765 }
766
767 // Comparison and hashing
768
769 /**
770 * Compares the specified Object with this Map for equality,
771 * as per the definition in the Map interface.
772 *
773 * @param o object to be compared for equality with this hashtable
774 * @return true if the specified Object is equal to this Map
775 * @see Map#equals(Object)
776 * @since 1.2
777 */
778 public synchronized boolean equals(Object o) {
779 if (o == this)
780 return true;
781
782 if (!(o instanceof Map))
783 return false;
784 Map<?,?> t = (Map<?,?>) o;
785 if (t.size() != size())
786 return false;
787
788 try {
789 Iterator<Map.Entry<K,V>> i = entrySet().iterator();
790 while (i.hasNext()) {
791 Map.Entry<K,V> e = i.next();
792 K key = e.getKey();
793 V value = e.getValue();
794 if (value == null) {
795 if (!(t.get(key)==null && t.containsKey(key)))
796 return false;
797 } else {
798 if (!value.equals(t.get(key)))
799 return false;
800 }
801 }
802 } catch (ClassCastException unused) {
803 return false;
804 } catch (NullPointerException unused) {
814 *
815 * @see Map#hashCode()
816 * @since 1.2
817 */
818 public synchronized int hashCode() {
819 /*
820 * This code detects the recursion caused by computing the hash code
821 * of a self-referential hash table and prevents the stack overflow
822 * that would otherwise result. This allows certain 1.1-era
823 * applets with self-referential hash tables to work. This code
824 * abuses the loadFactor field to do double-duty as a hashCode
825 * in progress flag, so as not to worsen the space performance.
826 * A negative load factor indicates that hash code computation is
827 * in progress.
828 */
829 int h = 0;
830 if (count == 0 || loadFactor < 0)
831 return h; // Returns zero
832
833 loadFactor = -loadFactor; // Mark hashCode computation in progress
834 Entry<?,?>[] tab = table;
835 for (int i = 0; i < tab.length; i++)
836 for (Entry<?,?> e = tab[i]; e != null; e = e.next)
837 h += e.key.hashCode() ^ e.value.hashCode();
838 loadFactor = -loadFactor; // Mark hashCode computation complete
839
840 return h;
841 }
842
843 /**
844 * Save the state of the Hashtable to a stream (i.e., serialize it).
845 *
846 * @serialData The <i>capacity</i> of the Hashtable (the length of the
847 * bucket array) is emitted (int), followed by the
848 * <i>size</i> of the Hashtable (the number of key-value
849 * mappings), followed by the key (Object) and value (Object)
850 * for each key-value mapping represented by the Hashtable
851 * The key-value mappings are emitted in no particular order.
852 */
853 private void writeObject(java.io.ObjectOutputStream s)
854 throws IOException {
855 Entry<Object, Object> entryStack = null;
856
857 synchronized (this) {
858 // Write out the length, threshold, loadfactor
859 s.defaultWriteObject();
860
861 // Write out length, count of elements
862 s.writeInt(table.length);
863 s.writeInt(count);
864
865 // Stack copies of the entries in the table
866 for (int index = 0; index < table.length; index++) {
867 Entry<?,?> entry = table[index];
868
869 while (entry != null) {
870 entryStack =
871 new Entry<>(0, entry.key, entry.value, entryStack);
872 entry = entry.next;
873 }
874 }
875 }
876
877 // Write out the key/value objects from the stacked entries
878 while (entryStack != null) {
879 s.writeObject(entryStack.key);
880 s.writeObject(entryStack.value);
881 entryStack = entryStack.next;
882 }
883 }
884
885 /**
886 * Reconstitute the Hashtable from a stream (i.e., deserialize it).
887 */
888 private void readObject(java.io.ObjectInputStream s)
889 throws IOException, ClassNotFoundException
890 {
891 // Read in the length, threshold, and loadfactor
892 s.defaultReadObject();
893
894 // Read the original length of the array and number of elements
895 int origlength = s.readInt();
896 int elements = s.readInt();
897
898 // Compute new size with a bit of room 5% to grow but
899 // no larger than the original size. Make the length
900 // odd if it's large enough, this helps distribute the entries.
901 // Guard against the length ending up zero, that's not valid.
902 int length = (int)(elements * loadFactor) + (elements / 20) + 3;
903 if (length > elements && (length & 1) == 0)
904 length--;
905 if (origlength > 0 && length > origlength)
906 length = origlength;
907
908 Entry<?,?>[] table = new Entry[length];
909 count = 0;
910
911 // Read the number of elements and then all the key/value objects
912 for (; elements > 0; elements--) {
913 @SuppressWarnings("unchecked")
914 K key = (K)s.readObject();
915 @SuppressWarnings("unchecked")
916 V value = (V)s.readObject();
917 // synch could be eliminated for performance
918 reconstitutionPut(table, key, value);
919 }
920 this.table = table;
921 }
922
923 /**
924 * The put method used by readObject. This is provided because put
925 * is overridable and should not be called in readObject since the
926 * subclass will not yet be initialized.
927 *
928 * <p>This differs from the regular put method in several ways. No
929 * checking for rehashing is necessary since the number of elements
930 * initially in the table is known. The modCount is not incremented
931 * because we are creating a new instance. Also, no return value
932 * is needed.
933 */
934 private void reconstitutionPut(Entry<?,?>[] tab, K key, V value)
935 throws StreamCorruptedException
936 {
937 if (value == null) {
938 throw new java.io.StreamCorruptedException();
939 }
940 // Makes sure the key is not already in the hashtable.
941 // This should not happen in deserialized version.
942 int hash = key.hashCode();
943 int index = (hash & 0x7FFFFFFF) % tab.length;
944 for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
945 if ((e.hash == hash) && e.key.equals(key)) {
946 throw new java.io.StreamCorruptedException();
947 }
948 }
949 // Creates the new entry.
950 @SuppressWarnings("unchecked")
951 Entry<K,V> e = (Entry<K,V>)tab[index];
952 tab[index] = new Entry<>(hash, key, value, e);
953 count++;
954 }
955
956 /**
957 * Hashtable collision list.
958 */
959 private static class Entry<K,V> implements Map.Entry<K,V> {
960 int hash;
961 K key;
962 V value;
963 Entry<K,V> next;
964
965 protected Entry(int hash, K key, V value, Entry<K,V> next) {
966 this.hash = hash;
967 this.key = key;
968 this.value = value;
969 this.next = next;
970 }
971
972 @SuppressWarnings("unchecked")
973 protected Object clone() {
974 return new Entry<>(hash, key, value,
975 (next==null ? null : (Entry<K,V>) next.clone()));
976 }
977
978 // Map.Entry Ops
979
980 public K getKey() {
981 return key;
982 }
983
984 public V getValue() {
985 return value;
986 }
987
988 public V setValue(V value) {
989 if (value == null)
990 throw new NullPointerException();
991
992 V oldValue = this.value;
993 this.value = value;
994 return oldValue;
995 }
996
997 public boolean equals(Object o) {
998 if (!(o instanceof Map.Entry))
999 return false;
1000 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
1001
1002 return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
1003 (value==null ? e.getValue()==null : value.equals(e.getValue()));
1004 }
1005
1006 public int hashCode() {
1007 return hash ^ (value==null ? 0 : value.hashCode());
1008 }
1009
1010 public String toString() {
1011 return key.toString()+"="+value.toString();
1012 }
1013 }
1014
1015 // Types of Enumerations/Iterations
1016 private static final int KEYS = 0;
1017 private static final int VALUES = 1;
1018 private static final int ENTRIES = 2;
1019
1020 /**
1021 * A hashtable enumerator class. This class implements both the
1022 * Enumeration and Iterator interfaces, but individual instances
1023 * can be created with the Iterator methods disabled. This is necessary
1024 * to avoid unintentionally increasing the capabilities granted a user
1025 * by passing an Enumeration.
1026 */
1027 private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
1028 Entry<?,?>[] table = Hashtable.this.table;
1029 int index = table.length;
1030 Entry<?,?> entry = null;
1031 Entry<?,?> lastReturned = null;
1032 int type;
1033
1034 /**
1035 * Indicates whether this Enumerator is serving as an Iterator
1036 * or an Enumeration. (true -> Iterator).
1037 */
1038 boolean iterator;
1039
1040 /**
1041 * The modCount value that the iterator believes that the backing
1042 * Hashtable should have. If this expectation is violated, the iterator
1043 * has detected concurrent modification.
1044 */
1045 protected int expectedModCount = modCount;
1046
1047 Enumerator(int type, boolean iterator) {
1048 this.type = type;
1049 this.iterator = iterator;
1050 }
1051
1052 public boolean hasMoreElements() {
1053 Entry<?,?> e = entry;
1054 int i = index;
1055 Entry<?,?>[] t = table;
1056 /* Use locals for faster loop iteration */
1057 while (e == null && i > 0) {
1058 e = t[--i];
1059 }
1060 entry = e;
1061 index = i;
1062 return e != null;
1063 }
1064
1065 @SuppressWarnings("unchecked")
1066 public T nextElement() {
1067 Entry<?,?> et = entry;
1068 int i = index;
1069 Entry<?,?>[] t = table;
1070 /* Use locals for faster loop iteration */
1071 while (et == null && i > 0) {
1072 et = t[--i];
1073 }
1074 entry = et;
1075 index = i;
1076 if (et != null) {
1077 Entry<?,?> e = lastReturned = entry;
1078 entry = e.next;
1079 return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
1080 }
1081 throw new NoSuchElementException("Hashtable Enumerator");
1082 }
1083
1084 // Iterator methods
1085 public boolean hasNext() {
1086 return hasMoreElements();
1087 }
1088
1089 public T next() {
1090 if (modCount != expectedModCount)
1091 throw new ConcurrentModificationException();
1092 return nextElement();
1093 }
1094
1095 public void remove() {
1096 if (!iterator)
1097 throw new UnsupportedOperationException();
1098 if (lastReturned == null)
1099 throw new IllegalStateException("Hashtable Enumerator");
1100 if (modCount != expectedModCount)
1101 throw new ConcurrentModificationException();
1102
1103 synchronized(Hashtable.this) {
1104 Entry<?,?>[] tab = Hashtable.this.table;
1105 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
1106
1107 for (@SuppressWarnings("unchecked")
1108 Entry<K,V> e = (Entry<K,V>)tab[index], prev = null; e != null;
1109 prev = e, e = e.next) {
1110 if (e == lastReturned) {
1111 modCount++;
1112 expectedModCount++;
1113 if (prev == null)
1114 tab[index] = e.next;
1115 else
1116 prev.next = e.next;
1117 count--;
1118 lastReturned = null;
1119 return;
1120 }
1121 }
1122 throw new ConcurrentModificationException();
1123 }
1124 }
1125 }
1126 }
|