jaroslav@597: /*
jaroslav@597: * Copyright (c) 1994, 2011, Oracle and/or its affiliates. All rights reserved.
jaroslav@597: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
jaroslav@597: *
jaroslav@597: * This code is free software; you can redistribute it and/or modify it
jaroslav@597: * under the terms of the GNU General Public License version 2 only, as
jaroslav@597: * published by the Free Software Foundation. Oracle designates this
jaroslav@597: * particular file as subject to the "Classpath" exception as provided
jaroslav@597: * by Oracle in the LICENSE file that accompanied this code.
jaroslav@597: *
jaroslav@597: * This code is distributed in the hope that it will be useful, but WITHOUT
jaroslav@597: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
jaroslav@597: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
jaroslav@597: * version 2 for more details (a copy is included in the LICENSE file that
jaroslav@597: * accompanied this code).
jaroslav@597: *
jaroslav@597: * You should have received a copy of the GNU General Public License version
jaroslav@597: * 2 along with this work; if not, write to the Free Software Foundation,
jaroslav@597: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
jaroslav@597: *
jaroslav@597: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
jaroslav@597: * or visit www.oracle.com if you need additional information or have any
jaroslav@597: * questions.
jaroslav@597: */
jaroslav@597:
jaroslav@597: package java.util;
jaroslav@597: import java.io.*;
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * This class implements a hash table, which maps keys to values. Any
jaroslav@597: * non-null object can be used as a key or as a value.
jaroslav@597: *
jaroslav@597: * To successfully store and retrieve objects from a hashtable, the
jaroslav@597: * objects used as keys must implement the hashCode
jaroslav@597: * method and the equals method.
jaroslav@597: *
jaroslav@597: * An instance of Hashtable has two parameters that affect its
jaroslav@597: * performance: initial capacity and load factor. The
jaroslav@597: * capacity is the number of buckets in the hash table, and the
jaroslav@597: * initial capacity is simply the capacity at the time the hash table
jaroslav@597: * is created. Note that the hash table is open: in the case of a "hash
jaroslav@597: * collision", a single bucket stores multiple entries, which must be searched
jaroslav@597: * sequentially. The load factor is a measure of how full the hash
jaroslav@597: * table is allowed to get before its capacity is automatically increased.
jaroslav@597: * The initial capacity and load factor parameters are merely hints to
jaroslav@597: * the implementation. The exact details as to when and whether the rehash
jaroslav@597: * method is invoked are implementation-dependent.
jaroslav@597: *
jaroslav@597: * Generally, the default load factor (.75) offers a good tradeoff between
jaroslav@597: * time and space costs. Higher values decrease the space overhead but
jaroslav@597: * increase the time cost to look up an entry (which is reflected in most
jaroslav@597: * Hashtable operations, including get and put).
jaroslav@597: *
jaroslav@597: * The initial capacity controls a tradeoff between wasted space and the
jaroslav@597: * need for rehash operations, which are time-consuming.
jaroslav@597: * No rehash operations will ever occur if the initial
jaroslav@597: * capacity is greater than the maximum number of entries the
jaroslav@597: * Hashtable will contain divided by its load factor. However,
jaroslav@597: * setting the initial capacity too high can waste space.
jaroslav@597: *
jaroslav@597: * If many entries are to be made into a Hashtable,
jaroslav@597: * creating it with a sufficiently large capacity may allow the
jaroslav@597: * entries to be inserted more efficiently than letting it perform
jaroslav@597: * automatic rehashing as needed to grow the table.
jaroslav@597: *
jaroslav@597: * This example creates a hashtable of numbers. It uses the names of
jaroslav@597: * the numbers as keys:
jaroslav@597: *
{@code
jaroslav@597: * Hashtable numbers
jaroslav@597: * = new Hashtable();
jaroslav@597: * numbers.put("one", 1);
jaroslav@597: * numbers.put("two", 2);
jaroslav@597: * numbers.put("three", 3);}
jaroslav@597: *
jaroslav@597: * To retrieve a number, use the following code:
jaroslav@597: *
{@code
jaroslav@597: * Integer n = numbers.get("two");
jaroslav@597: * if (n != null) {
jaroslav@597: * System.out.println("two = " + n);
jaroslav@597: * }}
jaroslav@597: *
jaroslav@597: * The iterators returned by the iterator method of the collections
jaroslav@597: * returned by all of this class's "collection view methods" are
jaroslav@597: * fail-fast: if the Hashtable is structurally modified at any time
jaroslav@597: * after the iterator is created, in any way except through the iterator's own
jaroslav@597: * remove method, the iterator will throw a {@link
jaroslav@597: * ConcurrentModificationException}. Thus, in the face of concurrent
jaroslav@597: * modification, the iterator fails quickly and cleanly, rather than risking
jaroslav@597: * arbitrary, non-deterministic behavior at an undetermined time in the future.
jaroslav@597: * The Enumerations returned by Hashtable's keys and elements methods are
jaroslav@597: * not fail-fast.
jaroslav@597: *
jaroslav@597: *
Note that the fail-fast behavior of an iterator cannot be guaranteed
jaroslav@597: * as it is, generally speaking, impossible to make any hard guarantees in the
jaroslav@597: * presence of unsynchronized concurrent modification. Fail-fast iterators
jaroslav@597: * throw ConcurrentModificationException on a best-effort basis.
jaroslav@597: * Therefore, it would be wrong to write a program that depended on this
jaroslav@597: * exception for its correctness: the fail-fast behavior of iterators
jaroslav@597: * should be used only to detect bugs.
jaroslav@597: *
jaroslav@597: *
As of the Java 2 platform v1.2, this class was retrofitted to
jaroslav@597: * implement the {@link Map} interface, making it a member of the
jaroslav@597: *
jaroslav@597: *
jaroslav@597: * Java Collections Framework. Unlike the new collection
jaroslav@597: * implementations, {@code Hashtable} is synchronized. If a
jaroslav@597: * thread-safe implementation is not needed, it is recommended to use
jaroslav@597: * {@link HashMap} in place of {@code Hashtable}. If a thread-safe
jaroslav@597: * highly-concurrent implementation is desired, then it is recommended
jaroslav@597: * to use {@link java.util.concurrent.ConcurrentHashMap} in place of
jaroslav@597: * {@code Hashtable}.
jaroslav@597: *
jaroslav@597: * @author Arthur van Hoff
jaroslav@597: * @author Josh Bloch
jaroslav@597: * @author Neal Gafter
jaroslav@597: * @see Object#equals(java.lang.Object)
jaroslav@597: * @see Object#hashCode()
jaroslav@597: * @see Hashtable#rehash()
jaroslav@597: * @see Collection
jaroslav@597: * @see Map
jaroslav@597: * @see HashMap
jaroslav@597: * @see TreeMap
jaroslav@597: * @since JDK1.0
jaroslav@597: */
jaroslav@597: public class Hashtable
jaroslav@597: extends Dictionary
jaroslav@597: implements Map, Cloneable, java.io.Serializable {
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * The hash table data.
jaroslav@597: */
jaroslav@597: private transient Entry[] table;
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * The total number of entries in the hash table.
jaroslav@597: */
jaroslav@597: private transient int count;
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * The table is rehashed when its size exceeds this threshold. (The
jaroslav@597: * value of this field is (int)(capacity * loadFactor).)
jaroslav@597: *
jaroslav@597: * @serial
jaroslav@597: */
jaroslav@597: private int threshold;
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * The load factor for the hashtable.
jaroslav@597: *
jaroslav@597: * @serial
jaroslav@597: */
jaroslav@597: private float loadFactor;
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * The number of times this Hashtable has been structurally modified
jaroslav@597: * Structural modifications are those that change the number of entries in
jaroslav@597: * the Hashtable or otherwise modify its internal structure (e.g.,
jaroslav@597: * rehash). This field is used to make iterators on Collection-views of
jaroslav@597: * the Hashtable fail-fast. (See ConcurrentModificationException).
jaroslav@597: */
jaroslav@597: private transient int modCount = 0;
jaroslav@597:
jaroslav@597: /** use serialVersionUID from JDK 1.0.2 for interoperability */
jaroslav@597: private static final long serialVersionUID = 1421746759512286392L;
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Constructs a new, empty hashtable with the specified initial
jaroslav@597: * capacity and the specified load factor.
jaroslav@597: *
jaroslav@597: * @param initialCapacity the initial capacity of the hashtable.
jaroslav@597: * @param loadFactor the load factor of the hashtable.
jaroslav@597: * @exception IllegalArgumentException if the initial capacity is less
jaroslav@597: * than zero, or if the load factor is nonpositive.
jaroslav@597: */
jaroslav@597: public Hashtable(int initialCapacity, float loadFactor) {
jaroslav@597: if (initialCapacity < 0)
jaroslav@597: throw new IllegalArgumentException("Illegal Capacity: "+
jaroslav@597: initialCapacity);
jaroslav@597: if (loadFactor <= 0 || Float.isNaN(loadFactor))
jaroslav@597: throw new IllegalArgumentException("Illegal Load: "+loadFactor);
jaroslav@597:
jaroslav@597: if (initialCapacity==0)
jaroslav@597: initialCapacity = 1;
jaroslav@597: this.loadFactor = loadFactor;
jaroslav@597: table = new Entry[initialCapacity];
jaroslav@597: threshold = (int)(initialCapacity * loadFactor);
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Constructs a new, empty hashtable with the specified initial capacity
jaroslav@597: * and default load factor (0.75).
jaroslav@597: *
jaroslav@597: * @param initialCapacity the initial capacity of the hashtable.
jaroslav@597: * @exception IllegalArgumentException if the initial capacity is less
jaroslav@597: * than zero.
jaroslav@597: */
jaroslav@597: public Hashtable(int initialCapacity) {
jaroslav@597: this(initialCapacity, 0.75f);
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Constructs a new, empty hashtable with a default initial capacity (11)
jaroslav@597: * and load factor (0.75).
jaroslav@597: */
jaroslav@597: public Hashtable() {
jaroslav@597: this(11, 0.75f);
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Constructs a new hashtable with the same mappings as the given
jaroslav@597: * Map. The hashtable is created with an initial capacity sufficient to
jaroslav@597: * hold the mappings in the given Map and a default load factor (0.75).
jaroslav@597: *
jaroslav@597: * @param t the map whose mappings are to be placed in this map.
jaroslav@597: * @throws NullPointerException if the specified map is null.
jaroslav@597: * @since 1.2
jaroslav@597: */
jaroslav@597: public Hashtable(Map t) {
jaroslav@597: this(Math.max(2*t.size(), 11), 0.75f);
jaroslav@597: putAll(t);
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Returns the number of keys in this hashtable.
jaroslav@597: *
jaroslav@597: * @return the number of keys in this hashtable.
jaroslav@597: */
jaroslav@597: public synchronized int size() {
jaroslav@597: return count;
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Tests if this hashtable maps no keys to values.
jaroslav@597: *
jaroslav@597: * @return true if this hashtable maps no keys to values;
jaroslav@597: * false otherwise.
jaroslav@597: */
jaroslav@597: public synchronized boolean isEmpty() {
jaroslav@597: return count == 0;
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Returns an enumeration of the keys in this hashtable.
jaroslav@597: *
jaroslav@597: * @return an enumeration of the keys in this hashtable.
jaroslav@597: * @see Enumeration
jaroslav@597: * @see #elements()
jaroslav@597: * @see #keySet()
jaroslav@597: * @see Map
jaroslav@597: */
jaroslav@597: public synchronized Enumeration keys() {
jaroslav@597: return this.getEnumeration(KEYS);
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Returns an enumeration of the values in this hashtable.
jaroslav@597: * Use the Enumeration methods on the returned object to fetch the elements
jaroslav@597: * sequentially.
jaroslav@597: *
jaroslav@597: * @return an enumeration of the values in this hashtable.
jaroslav@597: * @see java.util.Enumeration
jaroslav@597: * @see #keys()
jaroslav@597: * @see #values()
jaroslav@597: * @see Map
jaroslav@597: */
jaroslav@597: public synchronized Enumeration elements() {
jaroslav@597: return this.getEnumeration(VALUES);
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Tests if some key maps into the specified value in this hashtable.
jaroslav@597: * This operation is more expensive than the {@link #containsKey
jaroslav@597: * containsKey} method.
jaroslav@597: *
jaroslav@597: * Note that this method is identical in functionality to
jaroslav@597: * {@link #containsValue containsValue}, (which is part of the
jaroslav@597: * {@link Map} interface in the collections framework).
jaroslav@597: *
jaroslav@597: * @param value a value to search for
jaroslav@597: * @return true if and only if some key maps to the
jaroslav@597: * value argument in this hashtable as
jaroslav@597: * determined by the equals method;
jaroslav@597: * false otherwise.
jaroslav@597: * @exception NullPointerException if the value is null
jaroslav@597: */
jaroslav@597: public synchronized boolean contains(Object value) {
jaroslav@597: if (value == null) {
jaroslav@597: throw new NullPointerException();
jaroslav@597: }
jaroslav@597:
jaroslav@597: Entry tab[] = table;
jaroslav@597: for (int i = tab.length ; i-- > 0 ;) {
jaroslav@597: for (Entry e = tab[i] ; e != null ; e = e.next) {
jaroslav@597: if (e.value.equals(value)) {
jaroslav@597: return true;
jaroslav@597: }
jaroslav@597: }
jaroslav@597: }
jaroslav@597: return false;
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Returns true if this hashtable maps one or more keys to this value.
jaroslav@597: *
jaroslav@597: * Note that this method is identical in functionality to {@link
jaroslav@597: * #contains contains} (which predates the {@link Map} interface).
jaroslav@597: *
jaroslav@597: * @param value value whose presence in this hashtable is to be tested
jaroslav@597: * @return true if this map maps one or more keys to the
jaroslav@597: * specified value
jaroslav@597: * @throws NullPointerException if the value is null
jaroslav@597: * @since 1.2
jaroslav@597: */
jaroslav@597: public boolean containsValue(Object value) {
jaroslav@597: return contains(value);
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Tests if the specified object is a key in this hashtable.
jaroslav@597: *
jaroslav@597: * @param key possible key
jaroslav@597: * @return true if and only if the specified object
jaroslav@597: * is a key in this hashtable, as determined by the
jaroslav@597: * equals method; false otherwise.
jaroslav@597: * @throws NullPointerException if the key is null
jaroslav@597: * @see #contains(Object)
jaroslav@597: */
jaroslav@597: public synchronized boolean containsKey(Object key) {
jaroslav@597: Entry tab[] = table;
jaroslav@597: int hash = key.hashCode();
jaroslav@597: int index = (hash & 0x7FFFFFFF) % tab.length;
jaroslav@597: for (Entry e = tab[index] ; e != null ; e = e.next) {
jaroslav@597: if ((e.hash == hash) && e.key.equals(key)) {
jaroslav@597: return true;
jaroslav@597: }
jaroslav@597: }
jaroslav@597: return false;
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Returns the value to which the specified key is mapped,
jaroslav@597: * or {@code null} if this map contains no mapping for the key.
jaroslav@597: *
jaroslav@597: * More formally, if this map contains a mapping from a key
jaroslav@597: * {@code k} to a value {@code v} such that {@code (key.equals(k))},
jaroslav@597: * then this method returns {@code v}; otherwise it returns
jaroslav@597: * {@code null}. (There can be at most one such mapping.)
jaroslav@597: *
jaroslav@597: * @param key the key whose associated value is to be returned
jaroslav@597: * @return the value to which the specified key is mapped, or
jaroslav@597: * {@code null} if this map contains no mapping for the key
jaroslav@597: * @throws NullPointerException if the specified key is null
jaroslav@597: * @see #put(Object, Object)
jaroslav@597: */
jaroslav@597: public synchronized V get(Object key) {
jaroslav@597: Entry tab[] = table;
jaroslav@597: int hash = key.hashCode();
jaroslav@597: int index = (hash & 0x7FFFFFFF) % tab.length;
jaroslav@597: for (Entry e = tab[index] ; e != null ; e = e.next) {
jaroslav@597: if ((e.hash == hash) && e.key.equals(key)) {
jaroslav@597: return e.value;
jaroslav@597: }
jaroslav@597: }
jaroslav@597: return null;
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * The maximum size of array to allocate.
jaroslav@597: * Some VMs reserve some header words in an array.
jaroslav@597: * Attempts to allocate larger arrays may result in
jaroslav@597: * OutOfMemoryError: Requested array size exceeds VM limit
jaroslav@597: */
jaroslav@597: private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Increases the capacity of and internally reorganizes this
jaroslav@597: * hashtable, in order to accommodate and access its entries more
jaroslav@597: * efficiently. This method is called automatically when the
jaroslav@597: * number of keys in the hashtable exceeds this hashtable's capacity
jaroslav@597: * and load factor.
jaroslav@597: */
jaroslav@597: protected void rehash() {
jaroslav@597: int oldCapacity = table.length;
jaroslav@597: Entry[] oldMap = table;
jaroslav@597:
jaroslav@597: // overflow-conscious code
jaroslav@597: int newCapacity = (oldCapacity << 1) + 1;
jaroslav@597: if (newCapacity - MAX_ARRAY_SIZE > 0) {
jaroslav@597: if (oldCapacity == MAX_ARRAY_SIZE)
jaroslav@597: // Keep running with MAX_ARRAY_SIZE buckets
jaroslav@597: return;
jaroslav@597: newCapacity = MAX_ARRAY_SIZE;
jaroslav@597: }
jaroslav@597: Entry[] newMap = new Entry[newCapacity];
jaroslav@597:
jaroslav@597: modCount++;
jaroslav@597: threshold = (int)(newCapacity * loadFactor);
jaroslav@597: table = newMap;
jaroslav@597:
jaroslav@597: for (int i = oldCapacity ; i-- > 0 ;) {
jaroslav@597: for (Entry old = oldMap[i] ; old != null ; ) {
jaroslav@597: Entry e = old;
jaroslav@597: old = old.next;
jaroslav@597:
jaroslav@597: int index = (e.hash & 0x7FFFFFFF) % newCapacity;
jaroslav@597: e.next = newMap[index];
jaroslav@597: newMap[index] = e;
jaroslav@597: }
jaroslav@597: }
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Maps the specified key to the specified
jaroslav@597: * value in this hashtable. Neither the key nor the
jaroslav@597: * value can be null.
jaroslav@597: *
jaroslav@597: * The value can be retrieved by calling the get method
jaroslav@597: * with a key that is equal to the original key.
jaroslav@597: *
jaroslav@597: * @param key the hashtable key
jaroslav@597: * @param value the value
jaroslav@597: * @return the previous value of the specified key in this hashtable,
jaroslav@597: * or null if it did not have one
jaroslav@597: * @exception NullPointerException if the key or value is
jaroslav@597: * null
jaroslav@597: * @see Object#equals(Object)
jaroslav@597: * @see #get(Object)
jaroslav@597: */
jaroslav@597: public synchronized V put(K key, V value) {
jaroslav@597: // Make sure the value is not null
jaroslav@597: if (value == null) {
jaroslav@597: throw new NullPointerException();
jaroslav@597: }
jaroslav@597:
jaroslav@597: // Makes sure the key is not already in the hashtable.
jaroslav@597: Entry tab[] = table;
jaroslav@597: int hash = key.hashCode();
jaroslav@597: int index = (hash & 0x7FFFFFFF) % tab.length;
jaroslav@597: for (Entry e = tab[index] ; e != null ; e = e.next) {
jaroslav@597: if ((e.hash == hash) && e.key.equals(key)) {
jaroslav@597: V old = e.value;
jaroslav@597: e.value = value;
jaroslav@597: return old;
jaroslav@597: }
jaroslav@597: }
jaroslav@597:
jaroslav@597: modCount++;
jaroslav@597: if (count >= threshold) {
jaroslav@597: // Rehash the table if the threshold is exceeded
jaroslav@597: rehash();
jaroslav@597:
jaroslav@597: tab = table;
jaroslav@597: index = (hash & 0x7FFFFFFF) % tab.length;
jaroslav@597: }
jaroslav@597:
jaroslav@597: // Creates the new entry.
jaroslav@597: Entry e = tab[index];
jaroslav@597: tab[index] = new Entry<>(hash, key, value, e);
jaroslav@597: count++;
jaroslav@597: return null;
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Removes the key (and its corresponding value) from this
jaroslav@597: * hashtable. This method does nothing if the key is not in the hashtable.
jaroslav@597: *
jaroslav@597: * @param key the key that needs to be removed
jaroslav@597: * @return the value to which the key had been mapped in this hashtable,
jaroslav@597: * or null if the key did not have a mapping
jaroslav@597: * @throws NullPointerException if the key is null
jaroslav@597: */
jaroslav@597: public synchronized V remove(Object key) {
jaroslav@597: Entry tab[] = table;
jaroslav@597: int hash = key.hashCode();
jaroslav@597: int index = (hash & 0x7FFFFFFF) % tab.length;
jaroslav@597: for (Entry e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
jaroslav@597: if ((e.hash == hash) && e.key.equals(key)) {
jaroslav@597: modCount++;
jaroslav@597: if (prev != null) {
jaroslav@597: prev.next = e.next;
jaroslav@597: } else {
jaroslav@597: tab[index] = e.next;
jaroslav@597: }
jaroslav@597: count--;
jaroslav@597: V oldValue = e.value;
jaroslav@597: e.value = null;
jaroslav@597: return oldValue;
jaroslav@597: }
jaroslav@597: }
jaroslav@597: return null;
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Copies all of the mappings from the specified map to this hashtable.
jaroslav@597: * These mappings will replace any mappings that this hashtable had for any
jaroslav@597: * of the keys currently in the specified map.
jaroslav@597: *
jaroslav@597: * @param t mappings to be stored in this map
jaroslav@597: * @throws NullPointerException if the specified map is null
jaroslav@597: * @since 1.2
jaroslav@597: */
jaroslav@597: public synchronized void putAll(Map t) {
jaroslav@597: for (Map.Entry e : t.entrySet())
jaroslav@597: put(e.getKey(), e.getValue());
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Clears this hashtable so that it contains no keys.
jaroslav@597: */
jaroslav@597: public synchronized void clear() {
jaroslav@597: Entry tab[] = table;
jaroslav@597: modCount++;
jaroslav@597: for (int index = tab.length; --index >= 0; )
jaroslav@597: tab[index] = null;
jaroslav@597: count = 0;
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Creates a shallow copy of this hashtable. All the structure of the
jaroslav@597: * hashtable itself is copied, but the keys and values are not cloned.
jaroslav@597: * This is a relatively expensive operation.
jaroslav@597: *
jaroslav@597: * @return a clone of the hashtable
jaroslav@597: */
jaroslav@597: public synchronized Object clone() {
jaroslav@597: try {
jaroslav@597: Hashtable t = (Hashtable) super.clone();
jaroslav@597: t.table = new Entry[table.length];
jaroslav@597: for (int i = table.length ; i-- > 0 ; ) {
jaroslav@597: t.table[i] = (table[i] != null)
jaroslav@597: ? (Entry) table[i].clone() : null;
jaroslav@597: }
jaroslav@597: t.keySet = null;
jaroslav@597: t.entrySet = null;
jaroslav@597: t.values = null;
jaroslav@597: t.modCount = 0;
jaroslav@597: return t;
jaroslav@597: } catch (CloneNotSupportedException e) {
jaroslav@597: // this shouldn't happen, since we are Cloneable
jaroslav@597: throw new InternalError();
jaroslav@597: }
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Returns a string representation of this Hashtable object
jaroslav@597: * in the form of a set of entries, enclosed in braces and separated
jaroslav@597: * by the ASCII characters ", " (comma and space). Each
jaroslav@597: * entry is rendered as the key, an equals sign =, and the
jaroslav@597: * associated element, where the toString method is used to
jaroslav@597: * convert the key and element to strings.
jaroslav@597: *
jaroslav@597: * @return a string representation of this hashtable
jaroslav@597: */
jaroslav@597: public synchronized String toString() {
jaroslav@597: int max = size() - 1;
jaroslav@597: if (max == -1)
jaroslav@597: return "{}";
jaroslav@597:
jaroslav@597: StringBuilder sb = new StringBuilder();
jaroslav@597: Iterator> it = entrySet().iterator();
jaroslav@597:
jaroslav@597: sb.append('{');
jaroslav@597: for (int i = 0; ; i++) {
jaroslav@597: Map.Entry e = it.next();
jaroslav@597: K key = e.getKey();
jaroslav@597: V value = e.getValue();
jaroslav@597: sb.append(key == this ? "(this Map)" : key.toString());
jaroslav@597: sb.append('=');
jaroslav@597: sb.append(value == this ? "(this Map)" : value.toString());
jaroslav@597:
jaroslav@597: if (i == max)
jaroslav@597: return sb.append('}').toString();
jaroslav@597: sb.append(", ");
jaroslav@597: }
jaroslav@597: }
jaroslav@597:
jaroslav@597:
jaroslav@597: private Enumeration getEnumeration(int type) {
jaroslav@597: if (count == 0) {
jaroslav@597: return Collections.emptyEnumeration();
jaroslav@597: } else {
jaroslav@597: return new Enumerator<>(type, false);
jaroslav@597: }
jaroslav@597: }
jaroslav@597:
jaroslav@597: private Iterator getIterator(int type) {
jaroslav@597: if (count == 0) {
jaroslav@597: return Collections.emptyIterator();
jaroslav@597: } else {
jaroslav@597: return new Enumerator<>(type, true);
jaroslav@597: }
jaroslav@597: }
jaroslav@597:
jaroslav@597: // Views
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Each of these fields are initialized to contain an instance of the
jaroslav@597: * appropriate view the first time this view is requested. The views are
jaroslav@597: * stateless, so there's no reason to create more than one of each.
jaroslav@597: */
jaroslav@597: private transient volatile Set keySet = null;
jaroslav@597: private transient volatile Set> entrySet = null;
jaroslav@597: private transient volatile Collection values = null;
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Returns a {@link Set} view of the keys contained in this map.
jaroslav@597: * The set is backed by the map, so changes to the map are
jaroslav@597: * reflected in the set, and vice-versa. If the map is modified
jaroslav@597: * while an iteration over the set is in progress (except through
jaroslav@597: * the iterator's own remove operation), the results of
jaroslav@597: * the iteration are undefined. The set supports element removal,
jaroslav@597: * which removes the corresponding mapping from the map, via the
jaroslav@597: * Iterator.remove, Set.remove,
jaroslav@597: * removeAll, retainAll, and clear
jaroslav@597: * operations. It does not support the add or addAll
jaroslav@597: * operations.
jaroslav@597: *
jaroslav@597: * @since 1.2
jaroslav@597: */
jaroslav@597: public Set keySet() {
jaroslav@597: if (keySet == null)
jaroslav@597: keySet = Collections.synchronizedSet(new KeySet(), this);
jaroslav@597: return keySet;
jaroslav@597: }
jaroslav@597:
jaroslav@597: private class KeySet extends AbstractSet {
jaroslav@597: public Iterator iterator() {
jaroslav@597: return getIterator(KEYS);
jaroslav@597: }
jaroslav@597: public int size() {
jaroslav@597: return count;
jaroslav@597: }
jaroslav@597: public boolean contains(Object o) {
jaroslav@597: return containsKey(o);
jaroslav@597: }
jaroslav@597: public boolean remove(Object o) {
jaroslav@597: return Hashtable.this.remove(o) != null;
jaroslav@597: }
jaroslav@597: public void clear() {
jaroslav@597: Hashtable.this.clear();
jaroslav@597: }
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Returns a {@link Set} view of the mappings contained in this map.
jaroslav@597: * The set is backed by the map, so changes to the map are
jaroslav@597: * reflected in the set, and vice-versa. If the map is modified
jaroslav@597: * while an iteration over the set is in progress (except through
jaroslav@597: * the iterator's own remove operation, or through the
jaroslav@597: * setValue operation on a map entry returned by the
jaroslav@597: * iterator) the results of the iteration are undefined. The set
jaroslav@597: * supports element removal, which removes the corresponding
jaroslav@597: * mapping from the map, via the Iterator.remove,
jaroslav@597: * Set.remove, removeAll, retainAll and
jaroslav@597: * clear operations. It does not support the
jaroslav@597: * add or addAll operations.
jaroslav@597: *
jaroslav@597: * @since 1.2
jaroslav@597: */
jaroslav@597: public Set> entrySet() {
jaroslav@597: if (entrySet==null)
jaroslav@597: entrySet = Collections.synchronizedSet(new EntrySet(), this);
jaroslav@597: return entrySet;
jaroslav@597: }
jaroslav@597:
jaroslav@597: private class EntrySet extends AbstractSet> {
jaroslav@597: public Iterator> iterator() {
jaroslav@597: return getIterator(ENTRIES);
jaroslav@597: }
jaroslav@597:
jaroslav@597: public boolean add(Map.Entry o) {
jaroslav@597: return super.add(o);
jaroslav@597: }
jaroslav@597:
jaroslav@597: public boolean contains(Object o) {
jaroslav@597: if (!(o instanceof Map.Entry))
jaroslav@597: return false;
jaroslav@597: Map.Entry entry = (Map.Entry)o;
jaroslav@597: Object key = entry.getKey();
jaroslav@597: Entry[] tab = table;
jaroslav@597: int hash = key.hashCode();
jaroslav@597: int index = (hash & 0x7FFFFFFF) % tab.length;
jaroslav@597:
jaroslav@597: for (Entry e = tab[index]; e != null; e = e.next)
jaroslav@597: if (e.hash==hash && e.equals(entry))
jaroslav@597: return true;
jaroslav@597: return false;
jaroslav@597: }
jaroslav@597:
jaroslav@597: public boolean remove(Object o) {
jaroslav@597: if (!(o instanceof Map.Entry))
jaroslav@597: return false;
jaroslav@597: Map.Entry entry = (Map.Entry) o;
jaroslav@597: K key = entry.getKey();
jaroslav@597: Entry[] tab = table;
jaroslav@597: int hash = key.hashCode();
jaroslav@597: int index = (hash & 0x7FFFFFFF) % tab.length;
jaroslav@597:
jaroslav@597: for (Entry e = tab[index], prev = null; e != null;
jaroslav@597: prev = e, e = e.next) {
jaroslav@597: if (e.hash==hash && e.equals(entry)) {
jaroslav@597: modCount++;
jaroslav@597: if (prev != null)
jaroslav@597: prev.next = e.next;
jaroslav@597: else
jaroslav@597: tab[index] = e.next;
jaroslav@597:
jaroslav@597: count--;
jaroslav@597: e.value = null;
jaroslav@597: return true;
jaroslav@597: }
jaroslav@597: }
jaroslav@597: return false;
jaroslav@597: }
jaroslav@597:
jaroslav@597: public int size() {
jaroslav@597: return count;
jaroslav@597: }
jaroslav@597:
jaroslav@597: public void clear() {
jaroslav@597: Hashtable.this.clear();
jaroslav@597: }
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Returns a {@link Collection} view of the values contained in this map.
jaroslav@597: * The collection is backed by the map, so changes to the map are
jaroslav@597: * reflected in the collection, and vice-versa. If the map is
jaroslav@597: * modified while an iteration over the collection is in progress
jaroslav@597: * (except through the iterator's own remove operation),
jaroslav@597: * the results of the iteration are undefined. The collection
jaroslav@597: * supports element removal, which removes the corresponding
jaroslav@597: * mapping from the map, via the Iterator.remove,
jaroslav@597: * Collection.remove, removeAll,
jaroslav@597: * retainAll and clear operations. It does not
jaroslav@597: * support the add or addAll operations.
jaroslav@597: *
jaroslav@597: * @since 1.2
jaroslav@597: */
jaroslav@597: public Collection values() {
jaroslav@597: if (values==null)
jaroslav@597: values = Collections.synchronizedCollection(new ValueCollection(),
jaroslav@597: this);
jaroslav@597: return values;
jaroslav@597: }
jaroslav@597:
jaroslav@597: private class ValueCollection extends AbstractCollection {
jaroslav@597: public Iterator iterator() {
jaroslav@597: return getIterator(VALUES);
jaroslav@597: }
jaroslav@597: public int size() {
jaroslav@597: return count;
jaroslav@597: }
jaroslav@597: public boolean contains(Object o) {
jaroslav@597: return containsValue(o);
jaroslav@597: }
jaroslav@597: public void clear() {
jaroslav@597: Hashtable.this.clear();
jaroslav@597: }
jaroslav@597: }
jaroslav@597:
jaroslav@597: // Comparison and hashing
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Compares the specified Object with this Map for equality,
jaroslav@597: * as per the definition in the Map interface.
jaroslav@597: *
jaroslav@597: * @param o object to be compared for equality with this hashtable
jaroslav@597: * @return true if the specified Object is equal to this Map
jaroslav@597: * @see Map#equals(Object)
jaroslav@597: * @since 1.2
jaroslav@597: */
jaroslav@597: public synchronized boolean equals(Object o) {
jaroslav@597: if (o == this)
jaroslav@597: return true;
jaroslav@597:
jaroslav@597: if (!(o instanceof Map))
jaroslav@597: return false;
jaroslav@597: Map t = (Map) o;
jaroslav@597: if (t.size() != size())
jaroslav@597: return false;
jaroslav@597:
jaroslav@597: try {
jaroslav@597: Iterator> i = entrySet().iterator();
jaroslav@597: while (i.hasNext()) {
jaroslav@597: Map.Entry e = i.next();
jaroslav@597: K key = e.getKey();
jaroslav@597: V value = e.getValue();
jaroslav@597: if (value == null) {
jaroslav@597: if (!(t.get(key)==null && t.containsKey(key)))
jaroslav@597: return false;
jaroslav@597: } else {
jaroslav@597: if (!value.equals(t.get(key)))
jaroslav@597: return false;
jaroslav@597: }
jaroslav@597: }
jaroslav@597: } catch (ClassCastException unused) {
jaroslav@597: return false;
jaroslav@597: } catch (NullPointerException unused) {
jaroslav@597: return false;
jaroslav@597: }
jaroslav@597:
jaroslav@597: return true;
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Returns the hash code value for this Map as per the definition in the
jaroslav@597: * Map interface.
jaroslav@597: *
jaroslav@597: * @see Map#hashCode()
jaroslav@597: * @since 1.2
jaroslav@597: */
jaroslav@597: public synchronized int hashCode() {
jaroslav@597: /*
jaroslav@597: * This code detects the recursion caused by computing the hash code
jaroslav@597: * of a self-referential hash table and prevents the stack overflow
jaroslav@597: * that would otherwise result. This allows certain 1.1-era
jaroslav@597: * applets with self-referential hash tables to work. This code
jaroslav@597: * abuses the loadFactor field to do double-duty as a hashCode
jaroslav@597: * in progress flag, so as not to worsen the space performance.
jaroslav@597: * A negative load factor indicates that hash code computation is
jaroslav@597: * in progress.
jaroslav@597: */
jaroslav@597: int h = 0;
jaroslav@597: if (count == 0 || loadFactor < 0)
jaroslav@597: return h; // Returns zero
jaroslav@597:
jaroslav@597: loadFactor = -loadFactor; // Mark hashCode computation in progress
jaroslav@597: Entry[] tab = table;
jaroslav@597: for (int i = 0; i < tab.length; i++)
jaroslav@597: for (Entry e = tab[i]; e != null; e = e.next)
jaroslav@597: h += e.key.hashCode() ^ e.value.hashCode();
jaroslav@597: loadFactor = -loadFactor; // Mark hashCode computation complete
jaroslav@597:
jaroslav@597: return h;
jaroslav@597: }
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Hashtable collision list.
jaroslav@597: */
jaroslav@597: private static class Entry implements Map.Entry {
jaroslav@597: int hash;
jaroslav@597: K key;
jaroslav@597: V value;
jaroslav@597: Entry next;
jaroslav@597:
jaroslav@597: protected Entry(int hash, K key, V value, Entry next) {
jaroslav@597: this.hash = hash;
jaroslav@597: this.key = key;
jaroslav@597: this.value = value;
jaroslav@597: this.next = next;
jaroslav@597: }
jaroslav@597:
jaroslav@597: protected Object clone() {
jaroslav@597: return new Entry<>(hash, key, value,
jaroslav@597: (next==null ? null : (Entry) next.clone()));
jaroslav@597: }
jaroslav@597:
jaroslav@597: // Map.Entry Ops
jaroslav@597:
jaroslav@597: public K getKey() {
jaroslav@597: return key;
jaroslav@597: }
jaroslav@597:
jaroslav@597: public V getValue() {
jaroslav@597: return value;
jaroslav@597: }
jaroslav@597:
jaroslav@597: public V setValue(V value) {
jaroslav@597: if (value == null)
jaroslav@597: throw new NullPointerException();
jaroslav@597:
jaroslav@597: V oldValue = this.value;
jaroslav@597: this.value = value;
jaroslav@597: return oldValue;
jaroslav@597: }
jaroslav@597:
jaroslav@597: public boolean equals(Object o) {
jaroslav@597: if (!(o instanceof Map.Entry))
jaroslav@597: return false;
jaroslav@597: Map.Entry e = (Map.Entry)o;
jaroslav@597:
jaroslav@597: return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
jaroslav@597: (value==null ? e.getValue()==null : value.equals(e.getValue()));
jaroslav@597: }
jaroslav@597:
jaroslav@597: public int hashCode() {
jaroslav@597: return hash ^ (value==null ? 0 : value.hashCode());
jaroslav@597: }
jaroslav@597:
jaroslav@597: public String toString() {
jaroslav@597: return key.toString()+"="+value.toString();
jaroslav@597: }
jaroslav@597: }
jaroslav@597:
jaroslav@597: // Types of Enumerations/Iterations
jaroslav@597: private static final int KEYS = 0;
jaroslav@597: private static final int VALUES = 1;
jaroslav@597: private static final int ENTRIES = 2;
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * A hashtable enumerator class. This class implements both the
jaroslav@597: * Enumeration and Iterator interfaces, but individual instances
jaroslav@597: * can be created with the Iterator methods disabled. This is necessary
jaroslav@597: * to avoid unintentionally increasing the capabilities granted a user
jaroslav@597: * by passing an Enumeration.
jaroslav@597: */
jaroslav@597: private class Enumerator implements Enumeration, Iterator {
jaroslav@597: Entry[] table = Hashtable.this.table;
jaroslav@597: int index = table.length;
jaroslav@597: Entry entry = null;
jaroslav@597: Entry lastReturned = null;
jaroslav@597: int type;
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * Indicates whether this Enumerator is serving as an Iterator
jaroslav@597: * or an Enumeration. (true -> Iterator).
jaroslav@597: */
jaroslav@597: boolean iterator;
jaroslav@597:
jaroslav@597: /**
jaroslav@597: * The modCount value that the iterator believes that the backing
jaroslav@597: * Hashtable should have. If this expectation is violated, the iterator
jaroslav@597: * has detected concurrent modification.
jaroslav@597: */
jaroslav@597: protected int expectedModCount = modCount;
jaroslav@597:
jaroslav@597: Enumerator(int type, boolean iterator) {
jaroslav@597: this.type = type;
jaroslav@597: this.iterator = iterator;
jaroslav@597: }
jaroslav@597:
jaroslav@597: public boolean hasMoreElements() {
jaroslav@597: Entry e = entry;
jaroslav@597: int i = index;
jaroslav@597: Entry[] t = table;
jaroslav@597: /* Use locals for faster loop iteration */
jaroslav@597: while (e == null && i > 0) {
jaroslav@597: e = t[--i];
jaroslav@597: }
jaroslav@597: entry = e;
jaroslav@597: index = i;
jaroslav@597: return e != null;
jaroslav@597: }
jaroslav@597:
jaroslav@597: public T nextElement() {
jaroslav@597: Entry et = entry;
jaroslav@597: int i = index;
jaroslav@597: Entry[] t = table;
jaroslav@597: /* Use locals for faster loop iteration */
jaroslav@597: while (et == null && i > 0) {
jaroslav@597: et = t[--i];
jaroslav@597: }
jaroslav@597: entry = et;
jaroslav@597: index = i;
jaroslav@597: if (et != null) {
jaroslav@597: Entry e = lastReturned = entry;
jaroslav@597: entry = e.next;
jaroslav@597: return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
jaroslav@597: }
jaroslav@597: throw new NoSuchElementException("Hashtable Enumerator");
jaroslav@597: }
jaroslav@597:
jaroslav@597: // Iterator methods
jaroslav@597: public boolean hasNext() {
jaroslav@597: return hasMoreElements();
jaroslav@597: }
jaroslav@597:
jaroslav@597: public T next() {
jaroslav@597: if (modCount != expectedModCount)
jaroslav@597: throw new ConcurrentModificationException();
jaroslav@597: return nextElement();
jaroslav@597: }
jaroslav@597:
jaroslav@597: public void remove() {
jaroslav@597: if (!iterator)
jaroslav@597: throw new UnsupportedOperationException();
jaroslav@597: if (lastReturned == null)
jaroslav@597: throw new IllegalStateException("Hashtable Enumerator");
jaroslav@597: if (modCount != expectedModCount)
jaroslav@597: throw new ConcurrentModificationException();
jaroslav@597:
jaroslav@597: synchronized(Hashtable.this) {
jaroslav@597: Entry[] tab = Hashtable.this.table;
jaroslav@597: int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
jaroslav@597:
jaroslav@597: for (Entry e = tab[index], prev = null; e != null;
jaroslav@597: prev = e, e = e.next) {
jaroslav@597: if (e == lastReturned) {
jaroslav@597: modCount++;
jaroslav@597: expectedModCount++;
jaroslav@597: if (prev == null)
jaroslav@597: tab[index] = e.next;
jaroslav@597: else
jaroslav@597: prev.next = e.next;
jaroslav@597: count--;
jaroslav@597: lastReturned = null;
jaroslav@597: return;
jaroslav@597: }
jaroslav@597: }
jaroslav@597: throw new ConcurrentModificationException();
jaroslav@597: }
jaroslav@597: }
jaroslav@597: }
jaroslav@597: }