java Map集合框架之HashMap

Myth丶恋晨 2022-08-20 06:14 220阅读 0赞

package com.my.collection;
 
 import java.util.HashMap;
 import java.util.Iterator;
 import java.util.Map;
 
 /**
 * 关于Map集合框架 特点：该集合存储键值对。一对一对往里存。而且要保证键的唯一性。 Map集合框架子类
 * ：HashTable,HashMap,TreeMap、LinkedHashMap Map接口提供的方法有 V get(Object key);
 * 根据key获取value V put(K key, V value);将数据以键值对的方式存进集合中。 void putAll(Map<? extends
 * K, ? extends V> m);从指定映射中将所有映射关系复制到此映射中 int size(); 获取集合的大小 boolean
 * isEmpty();判断集合是否为空 boolean containsKey(Object key);判断集合中是否包含指定key boolean
 * containsValue(Object value);判断集合中是否包含指定value V remove(Object key);删除某个元素 void
 * clear();清除集合 Set<K> keySet();获取key集合 Collection<V> values();value集合
 * Set<Map.Entry<K, V>> entrySet(); 等
 * 
 * 
 * @author wbw
 * 
 */
 public class MyMap {
 
 	private static Map<String, Object> map = null;
 
 	/**
 	 * 使用put()方法初始化HshMap
 	 */
 	public static void initMap() {
 		System.out.println("初始化Hashmap.......");
 		// HashMap是一个罪常用的Map,它根据键的HashCode
 		// 值存储数据,根据键可以直接获取它的值，具有很快的访问速度。HashMap最多只允许一条记录的键为Null;允许多条记录的值为
 		// Null;HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步，可以用
 		// Collections的synchronizedMap方法使HashMap具有同步的能力.
 		map = new HashMap<String, Object>();
 		map.put("1", "a");
 		map.put("1", "c");// 不允许键重复,允许值重复,如果键重复,最后的key的值将会覆盖第一个key的值
 		map.put("2", "b");
 		map.put("3", "d");
 		map.put("3", null);// 键不为null,值为null
 		map.put(null, "e");// 键为null,值不为null
 
 	}
 
 	/**
 	 * 遍历key和values
 	 */
 	public static void outEelem() {
 		System.out.println("#####遍历key和values######");
 		// 遍历方式一
 		System.out.println("#####map.keySet()遍历key和values######");
 		for (String key : map.keySet()) {
 			System.out.println("key" + key + "and value" + map.get(key));
 		}
 		// 遍历方式二：
 		Iterator<Map.Entry<String, Object>> it = map.entrySet().iterator();
 		System.out
 				.println("#####通过Map.Entry<String, Object>使用Iterator遍历key和values######");
 		while (it.hasNext()) {
 			Map.Entry<String, Object> entry = it.next();
 			System.out.println("key= " + entry.getKey() + " and value= "
 					+ entry.getValue());
 		}
 		// 遍历方式三：
 		System.out
 				.println("##### 通过Map.Entry<String, Object> entry 遍历key和values######");
 		for (Map.Entry<String, Object> entry : map.entrySet()) {
 			System.out.println("key= " + entry.getKey() + " and value= "
 					+ entry.getValue());
 		}
 		// 遍历方式四：
 		System.out.println("#####通过Map.values()遍历所有的value，但不能遍历key######");
 		for (Object value : map.values()) {
 			System.out.println("Values " + value);
 		}
 	}
 
 	/**
 	 * 通过containsKey()方法和containsValue()方法判断key和值是否存在
 	 */
 	public static void judegKeyAndValue(String key, String value) {
 		if (map.containsKey(key)) {
 			System.out.println(key + "存在集合中");
 		}
 		if (map.containsValue(value)) {
 			System.out.println(value + "存在集合中");
 		}
 
 	}
 
 	/**
 	 * 通过size()方法获取map的大小
 	 * 
 	 * @param map
 	 * @return
 	 */
 	public static int size(Map<String, Object> map) {
 		if (!map.isEmpty()) {// 使用map的isEmpty()方法判断集合是否为空
 			return map.size();
 		}
 		return 0;
 
 	}
 
 	/**
 	 * 通过clear()方法清空map
 	 * 
 	 * @param map
 	 */
 	public static void clear(Map<String, Object> map) {
 		if (!map.isEmpty()) {// 使用map的isEmpty()方法判断集合是否为空
 			map.clear();
 		}
 	}
 
 	/**
 	 * 测试
 	 * 
 	 * @param args
 	 */
 	public static void main(String[] args) {
 		initMap();// 初始化map
 		outEelem();// 遍历map
 		judegKeyAndValue("1", "b");// 1存在集合中 b存在集合中
 		judegKeyAndValue("1", "a");// 1存在集合中 但是a 不存在集合中,因为其值已经被覆盖
 		System.out.println(size(map));// 集合大小
 		clear(map);// 清空集合之后再遍历集合
 		outEelem();// 遍历map
 	}
 
 }

**Map接口的源码：**

/*
 * Copyright (c) 1997, 2006, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */
 
 package java.util;
 
 /**
 * An object that maps keys to values. A map cannot contain duplicate keys;
 * each key can map to at most one value.
 *
 * This interface takes the place of the <tt>Dictionary</tt> class, which
 * was a totally abstract class rather than an interface.
 *
 * The <tt>Map</tt> interface provides three collection views, which
 * allow a map's contents to be viewed as a set of keys, collection of values,
 * or set of key-value mappings. The order of a map is defined as
 * the order in which the iterators on the map's collection views return their
 * elements. Some map implementations, like the <tt>TreeMap</tt> class, make
 * specific guarantees as to their order; others, like the <tt>HashMap</tt>
 * class, do not.
 *
 * Note: great care must be exercised if mutable objects are used as map
 * keys. The behavior of a map is not specified if the value of an object is
 * changed in a manner that affects <tt>equals</tt> comparisons while the
 * object is a key in the map. A special case of this prohibition is that it
 * is not permissible for a map to contain itself as a key. While it is
 * permissible for a map to contain itself as a value, extreme caution is
 * advised: the <tt>equals</tt> and <tt>hashCode</tt> methods are no longer
 * well defined on such a map.
 *
 * All general-purpose map implementation classes should provide two
 * "standard" constructors: a void (no arguments) constructor which creates an
 * empty map, and a constructor with a single argument of type <tt>Map</tt>,
 * which creates a new map with the same key-value mappings as its argument.
 * In effect, the latter constructor allows the user to copy any map,
 * producing an equivalent map of the desired class. There is no way to
 * enforce this recommendation (as interfaces cannot contain constructors) but
 * all of the general-purpose map implementations in the JDK comply.
 *
 * The "destructive" methods contained in this interface, that is, the
 * methods that modify the map on which they operate, are specified to throw
 * <tt>UnsupportedOperationException</tt> if this map does not support the
 * operation. If this is the case, these methods may, but are not required
 * to, throw an <tt>UnsupportedOperationException</tt> if the invocation would
 * have no effect on the map. For example, invoking the {@link #putAll(Map)}
 * method on an unmodifiable map may, but is not required to, throw the
 * exception if the map whose mappings are to be "superimposed" is empty.
 *
 * Some map implementations have restrictions on the keys and values they
 * may contain. For example, some implementations prohibit null keys and
 * values, and some have restrictions on the types of their keys. Attempting
 * to insert an ineligible key or value throws an unchecked exception,
 * typically <tt>NullPointerException</tt> or <tt>ClassCastException</tt>.
 * Attempting to query the presence of an ineligible key or value may throw an
 * exception, or it may simply return false; some implementations will exhibit
 * the former behavior and some will exhibit the latter. More generally,
 * attempting an operation on an ineligible key or value whose completion
 * would not result in the insertion of an ineligible element into the map may
 * throw an exception or it may succeed, at the option of the implementation.
 * Such exceptions are marked as "optional" in the specification for this
 * interface.
 *
 * This interface is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * Many methods in Collections Framework interfaces are defined
 * in terms of the {@link Object#equals(Object) equals} method. For
 * example, the specification for the {@link #containsKey(Object)
 * containsKey(Object key)} method says: "returns <tt>true</tt> if and
 * only if this map contains a mapping for a key <tt>k</tt> such that
 * <tt>(key==null ? k==null : key.equals(k))</tt>." This specification should
 * not be construed to imply that invoking <tt>Map.containsKey</tt>
 * with a non-null argument <tt>key</tt> will cause <tt>key.equals(k)</tt> to
 * be invoked for any key <tt>k</tt>. Implementations are free to
 * implement optimizations whereby the <tt>equals</tt> invocation is avoided,
 * for example, by first comparing the hash codes of the two keys. (The
 * {@link Object#hashCode()} specification guarantees that two objects with
 * unequal hash codes cannot be equal.) More generally, implementations of
 * the various Collections Framework interfaces are free to take advantage of
 * the specified behavior of underlying {@link Object} methods wherever the
 * implementor deems it appropriate.
 *
 * @param <K> the type of keys maintained by this map
 * @param <V> the type of mapped values
 *
 * @author Josh Bloch
 * @see HashMap
 * @see TreeMap
 * @see Hashtable
 * @see SortedMap
 * @see Collection
 * @see Set
 * @since 1.2
 */
 public interface Map<K,V> {
 // Query Operations
 
 /**
 * Returns the number of key-value mappings in this map. If the
 * map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
 * <tt>Integer.MAX_VALUE</tt>.
 *
 * @return the number of key-value mappings in this map
 */
 int size();
 
 /**
 * Returns <tt>true</tt> if this map contains no key-value mappings.
 *
 * @return <tt>true</tt> if this map contains no key-value mappings
 */
 boolean isEmpty();
 
 /**
 * Returns <tt>true</tt> if this map contains a mapping for the specified
 * key. More formally, returns <tt>true</tt> if and only if
 * this map contains a mapping for a key <tt>k</tt> such that
 * <tt>(key==null ? k==null : key.equals(k))</tt>. (There can be
 * at most one such mapping.)
 *
 * @param key key whose presence in this map is to be tested
 * @return <tt>true</tt> if this map contains a mapping for the specified
 * key
 * @throws ClassCastException if the key is of an inappropriate type for
 * this map
 * (<a href="Collection.html#optional-restrictions">optional</a>)
 * @throws NullPointerException if the specified key is null and this map
 * does not permit null keys
 * (<a href="Collection.html#optional-restrictions">optional</a>)
 */
 boolean containsKey(Object key);
 
 /**
 * Returns <tt>true</tt> if this map maps one or more keys to the
 * specified value. More formally, returns <tt>true</tt> if and only if
 * this map contains at least one mapping to a value <tt>v</tt> such that
 * <tt>(value==null ? v==null : value.equals(v))</tt>. This operation
 * will probably require time linear in the map size for most
 * implementations of the <tt>Map</tt> interface.
 *
 * @param value value whose presence in this map is to be tested
 * @return <tt>true</tt> if this map maps one or more keys to the
 * specified value
 * @throws ClassCastException if the value is of an inappropriate type for
 * this map
 * (<a href="Collection.html#optional-restrictions">optional</a>)
 * @throws NullPointerException if the specified value is null and this
 * map does not permit null values
 * (<a href="Collection.html#optional-restrictions">optional</a>)
 */
 boolean containsValue(Object value);
 
 /**
 * Returns the value to which the specified key is mapped,
 * or {@code null} if this map contains no mapping for the key.
 *
 * More formally, if this map contains a mapping from a key
 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
 * key.equals(k))}, then this method returns {@code v}; otherwise
 * it returns {@code null}. (There can be at most one such mapping.)
 *
 * If this map permits null values, then a return value of
 * {@code null} does not necessarily indicate that the map
 * contains no mapping for the key; it's also possible that the map
 * explicitly maps the key to {@code null}. The {@link #containsKey
 * containsKey} operation may be used to distinguish these two cases.
 *
 * @param key the key whose associated value is to be returned
 * @return the value to which the specified key is mapped, or
 * {@code null} if this map contains no mapping for the key
 * @throws ClassCastException if the key is of an inappropriate type for
 * this map
 * (<a href="Collection.html#optional-restrictions">optional</a>)
 * @throws NullPointerException if the specified key is null and this map
 * does not permit null keys
 * (<a href="Collection.html#optional-restrictions">optional</a>)
 */
 V get(Object key);
 
 // Modification Operations
 
 /**
 * Associates the specified value with the specified key in this map
 * (optional operation). If the map previously contained a mapping for
 * the key, the old value is replaced by the specified value. (A map
 * <tt>m</tt> is said to contain a mapping for a key <tt>k</tt> if and only
 * if {@link #containsKey(Object) m.containsKey(k)} would return
 * <tt>true</tt>.)
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
 * (A <tt>null</tt> return can also indicate that the map
 * previously associated <tt>null</tt> with <tt>key</tt>,
 * if the implementation supports <tt>null</tt> values.)
 * @throws UnsupportedOperationException if the <tt>put</tt> operation
 * is not supported by this map
 * @throws ClassCastException if the class of the specified key or value
 * prevents it from being stored in this map
 * @throws NullPointerException if the specified key or value is null
 * and this map does not permit null keys or values
 * @throws IllegalArgumentException if some property of the specified key
 * or value prevents it from being stored in this map
 */
 V put(K key, V value);
 
 /**
 * Removes the mapping for a key from this map if it is present
 * (optional operation). More formally, if this map contains a mapping
 * from key <tt>k</tt> to value <tt>v</tt> such that
 * <code>(key==null ? k==null : key.equals(k))</code>, that mapping
 * is removed. (The map can contain at most one such mapping.)
 *
 * Returns the value to which this map previously associated the key,
 * or <tt>null</tt> if the map contained no mapping for the key.
 *
 * If this map permits null values, then a return value of
 * <tt>null</tt> does not necessarily indicate that the map
 * contained no mapping for the key; it's also possible that the map
 * explicitly mapped the key to <tt>null</tt>.
 *
 * The map will not contain a mapping for the specified key once the
 * call returns.
 *
 * @param key key whose mapping is to be removed from the map
 * @return the previous value associated with <tt>key</tt>, or
 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
 * @throws UnsupportedOperationException if the <tt>remove</tt> operation
 * is not supported by this map
 * @throws ClassCastException if the key is of an inappropriate type for
 * this map
 * (<a href="Collection.html#optional-restrictions">optional</a>)
 * @throws NullPointerException if the specified key is null and this
 * map does not permit null keys
 * (<a href="Collection.html#optional-restrictions">optional</a>)
 */
 V remove(Object key);
 
 
 // Bulk Operations
 
 /**
 * Copies all of the mappings from the specified map to this map
 * (optional operation). The effect of this call is equivalent to that
 * of calling {@link #put(Object,Object) put(k, v)} on this map once
 * for each mapping from key <tt>k</tt> to value <tt>v</tt> in the
 * specified map. The behavior of this operation is undefined if the
 * specified map is modified while the operation is in progress.
 *
 * @param m mappings to be stored in this map
 * @throws UnsupportedOperationException if the <tt>putAll</tt> operation
 * is not supported by this map
 * @throws ClassCastException if the class of a key or value in the
 * specified map prevents it from being stored in this map
 * @throws NullPointerException if the specified map is null, or if
 * this map does not permit null keys or values, and the
 * specified map contains null keys or values
 * @throws IllegalArgumentException if some property of a key or value in
 * the specified map prevents it from being stored in this map
 */
 void putAll(Map<? extends K, ? extends V> m);
 
 /**
 * Removes all of the mappings from this map (optional operation).
 * The map will be empty after this call returns.
 *
 * @throws UnsupportedOperationException if the <tt>clear</tt> operation
 * is not supported by this map
 */
 void clear();
 
 
 // Views
 
 /**
 * Returns a {@link Set} view of the keys contained in this map.
 * The set is backed by the map, so changes to the map are
 * reflected in the set, and vice-versa. If the map is modified
 * while an iteration over the set is in progress (except through
 * the iterator's own <tt>remove</tt> operation), the results of
 * the iteration are undefined. The set supports element removal,
 * which removes the corresponding mapping from the map, via the
 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
 * operations.
 *
 * @return a set view of the keys contained in this map
 */
 Set<K> keySet();
 
 /**
 * Returns a {@link Collection} view of the values contained in this map.
 * The collection is backed by the map, so changes to the map are
 * reflected in the collection, and vice-versa. If the map is
 * modified while an iteration over the collection is in progress
 * (except through the iterator's own <tt>remove</tt> operation),
 * the results of the iteration are undefined. The collection
 * supports element removal, which removes the corresponding
 * mapping from the map, via the <tt>Iterator.remove</tt>,
 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
 * support the <tt>add</tt> or <tt>addAll</tt> operations.
 *
 * @return a collection view of the values contained in this map
 */
 Collection<V> values();
 
 /**
 * Returns a {@link Set} view of the mappings contained in this map.
 * The set is backed by the map, so changes to the map are
 * reflected in the set, and vice-versa. If the map is modified
 * while an iteration over the set is in progress (except through
 * the iterator's own <tt>remove</tt> operation, or through the
 * <tt>setValue</tt> operation on a map entry returned by the
 * iterator) the results of the iteration are undefined. The set
 * supports element removal, which removes the corresponding
 * mapping from the map, via the <tt>Iterator.remove</tt>,
 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
 * <tt>clear</tt> operations. It does not support the
 * <tt>add</tt> or <tt>addAll</tt> operations.
 *
 * @return a set view of the mappings contained in this map
 */
 Set<Map.Entry<K, V>> entrySet();
 
 /**
 * A map entry (key-value pair). The <tt>Map.entrySet</tt> method returns
 * a collection-view of the map, whose elements are of this class. The
 * only way to obtain a reference to a map entry is from the
 * iterator of this collection-view. These <tt>Map.Entry</tt> objects are
 * valid only for the duration of the iteration; more formally,
 * the behavior of a map entry is undefined if the backing map has been
 * modified after the entry was returned by the iterator, except through
 * the <tt>setValue</tt> operation on the map entry.
 *
 * @see Map#entrySet()
 * @since 1.2
 */
 interface Entry<K,V> {
 /**
 * Returns the key corresponding to this entry.
 *
 * @return the key corresponding to this entry
 * @throws IllegalStateException implementations may, but are not
 * required to, throw this exception if the entry has been
 * removed from the backing map.
 */
 K getKey();
 
 /**
 * Returns the value corresponding to this entry. If the mapping
 * has been removed from the backing map (by the iterator's
 * <tt>remove</tt> operation), the results of this call are undefined.
 *
 * @return the value corresponding to this entry
 * @throws IllegalStateException implementations may, but are not
 * required to, throw this exception if the entry has been
 * removed from the backing map.
 */
 V getValue();
 
 /**
 * Replaces the value corresponding to this entry with the specified
 * value (optional operation). (Writes through to the map.) The
 * behavior of this call is undefined if the mapping has already been
 * removed from the map (by the iterator's <tt>remove</tt> operation).
 *
 * @param value new value to be stored in this entry
 * @return old value corresponding to the entry
 * @throws UnsupportedOperationException if the <tt>put</tt> operation
 * is not supported by the backing map
 * @throws ClassCastException if the class of the specified value
 * prevents it from being stored in the backing map
 * @throws NullPointerException if the backing map does not permit
 * null values, and the specified value is null
 * @throws IllegalArgumentException if some property of this value
 * prevents it from being stored in the backing map
 * @throws IllegalStateException implementations may, but are not
 * required to, throw this exception if the entry has been
 * removed from the backing map.
 */
 V setValue(V value);
 
 /**
 * Compares the specified object with this entry for equality.
 * Returns <tt>true</tt> if the given object is also a map entry and
 * the two entries represent the same mapping. More formally, two
 * entries <tt>e1</tt> and <tt>e2</tt> represent the same mapping
 * if<pre>
 * (e1.getKey()==null ?
 * e2.getKey()==null : e1.getKey().equals(e2.getKey())) &&
 * (e1.getValue()==null ?
 * e2.getValue()==null : e1.getValue().equals(e2.getValue()))
 * </pre>
 * This ensures that the <tt>equals</tt> method works properly across
 * different implementations of the <tt>Map.Entry</tt> interface.
 *
 * @param o object to be compared for equality with this map entry
 * @return <tt>true</tt> if the specified object is equal to this map
 * entry
 */
 boolean equals(Object o);
 
 /**
 * Returns the hash code value for this map entry. The hash code
 * of a map entry <tt>e</tt> is defined to be: <pre>
 * (e.getKey()==null ? 0 : e.getKey().hashCode()) ^
 * (e.getValue()==null ? 0 : e.getValue().hashCode())
 * </pre>
 * This ensures that <tt>e1.equals(e2)</tt> implies that
 * <tt>e1.hashCode()==e2.hashCode()</tt> for any two Entries
 * <tt>e1</tt> and <tt>e2</tt>, as required by the general
 * contract of <tt>Object.hashCode</tt>.
 *
 * @return the hash code value for this map entry
 * @see Object#hashCode()
 * @see Object#equals(Object)
 * @see #equals(Object)
 */
 int hashCode();
 }
 
 // Comparison and hashing
 
 /**
 * Compares the specified object with this map for equality. Returns
 * <tt>true</tt> if the given object is also a map and the two maps
 * represent the same mappings. More formally, two maps <tt>m1</tt> and
 * <tt>m2</tt> represent the same mappings if
 * <tt>m1.entrySet().equals(m2.entrySet())</tt>. This ensures that the
 * <tt>equals</tt> method works properly across different implementations
 * of the <tt>Map</tt> interface.
 *
 * @param o object to be compared for equality with this map
 * @return <tt>true</tt> if the specified object is equal to this map
 */
 boolean equals(Object o);
 
 /**
 * Returns the hash code value for this map. The hash code of a map is
 * defined to be the sum of the hash codes of each entry in the map's
 * <tt>entrySet()</tt> view. This ensures that <tt>m1.equals(m2)</tt>
 * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two maps
 * <tt>m1</tt> and <tt>m2</tt>, as required by the general contract of
 * {@link Object#hashCode}.
 *
 * @return the hash code value for this map
 * @see Map.Entry#hashCode()
 * @see Object#equals(Object)
 * @see #equals(Object)
 */
 int hashCode();
 
 }

HashMap源码

/*
 * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */
 
 package java.util;
 import java.io.*;
 
 /**
 * Hash table based implementation of the <tt>Map</tt> interface. This
 * implementation provides all of the optional map operations, and permits
 * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
 * unsynchronized and permits nulls.) This class makes no guarantees as to
 * the order of the map; in particular, it does not guarantee that the order
 * will remain constant over time.
 *
 * This implementation provides constant-time performance for the basic
 * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
 * disperses the elements properly among the buckets. Iteration over
 * collection views requires time proportional to the "capacity" of the
 * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
 * of key-value mappings). Thus, it's very important not to set the initial
 * capacity too high (or the load factor too low) if iteration performance is
 * important.
 *
 * An instance of <tt>HashMap</tt> has two parameters that affect its
 * performance: initial capacity and load factor. The
 * capacity is the number of buckets in the hash table, and the initial
 * capacity is simply the capacity at the time the hash table is created. The
 * load factor is a measure of how full the hash table is allowed to
 * get before its capacity is automatically increased. When the number of
 * entries in the hash table exceeds the product of the load factor and the
 * current capacity, the hash table is rehashed (that is, internal data
 * structures are rebuilt) so that the hash table has approximately twice the
 * number of buckets.
 *
 * As a general rule, the default load factor (.75) offers a good tradeoff
 * between time and space costs. Higher values decrease the space overhead
 * but increase the lookup cost (reflected in most of the operations of the
 * <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>). The
 * expected number of entries in the map and its load factor should be taken
 * into account when setting its initial capacity, so as to minimize the
 * number of rehash operations. If the initial capacity is greater
 * than the maximum number of entries divided by the load factor, no
 * rehash operations will ever occur.
 *
 * If many mappings are to be stored in a <tt>HashMap</tt> instance,
 * creating it with a sufficiently large capacity will allow the mappings to
 * be stored more efficiently than letting it perform automatic rehashing as
 * needed to grow the table.
 *
 * Note that this implementation is not synchronized.
 * If multiple threads access a hash map concurrently, and at least one of
 * the threads modifies the map structurally, it must be
 * synchronized externally. (A structural modification is any operation
 * that adds or deletes one or more mappings; merely changing the value
 * associated with a key that an instance already contains is not a
 * structural modification.) This is typically accomplished by
 * synchronizing on some object that naturally encapsulates the map.
 *
 * If no such object exists, the map should be "wrapped" using the
 * {@link Collections#synchronizedMap Collections.synchronizedMap}
 * method. This is best done at creation time, to prevent accidental
 * unsynchronized access to the map:<pre>
 * Map m = Collections.synchronizedMap(new HashMap(...));</pre>
 *
 * The iterators returned by all of this class's "collection view methods"
 * are fail-fast: if the map is structurally modified at any time after
 * the iterator is created, in any way except through the iterator's own
 * <tt>remove</tt> method, the iterator will throw a
 * {@link ConcurrentModificationException}. Thus, in the face of concurrent
 * modification, the iterator fails quickly and cleanly, rather than risking
 * arbitrary, non-deterministic behavior at an undetermined time in the
 * future.
 *
 * Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification. Fail-fast iterators
 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness: the fail-fast behavior of iterators
 * should be used only to detect bugs.
 *
 * This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @param <K> the type of keys maintained by this map
 * @param <V> the type of mapped values
 *
 * @author Doug Lea
 * @author Josh Bloch
 * @author Arthur van Hoff
 * @author Neal Gafter
 * @see Object#hashCode()
 * @see Collection
 * @see Map
 * @see TreeMap
 * @see Hashtable
 * @since 1.2
 */
 
 public class HashMap<K,V>
 extends AbstractMap<K,V>
 implements Map<K,V>, Cloneable, Serializable
 {
 
 /**
 * The default initial capacity - MUST be a power of two.
 */
 static final int DEFAULT_INITIAL_CAPACITY = 16;
 
 /**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 */
 static final int MAXIMUM_CAPACITY = 1 << 30;
 
 /**
 * The load factor used when none specified in constructor.
 */
 static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
 /**
 * The table, resized as necessary. Length MUST Always be a power of two.
 */
 transient Entry[] table;
 
 /**
 * The number of key-value mappings contained in this map.
 */
 transient int size;
 
 /**
 * The next size value at which to resize (capacity * load factor).
 * @serial
 */
 int threshold;
 
 /**
 * The load factor for the hash table.
 *
 * @serial
 */
 final float loadFactor;
 
 /**
 * The number of times this HashMap has been structurally modified
 * Structural modifications are those that change the number of mappings in
 * the HashMap or otherwise modify its internal structure (e.g.,
 * rehash). This field is used to make iterators on Collection-views of
 * the HashMap fail-fast. (See ConcurrentModificationException).
 */
 transient int modCount;
 
 /**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and load factor.
 *
 * @param initialCapacity the initial capacity
 * @param loadFactor the load factor
 * @throws IllegalArgumentException if the initial capacity is negative
 * or the load factor is nonpositive
 */
 public HashMap(int initialCapacity, float loadFactor) {
 if (initialCapacity < 0)
 throw new IllegalArgumentException("Illegal initial capacity: " +
 initialCapacity);
 if (initialCapacity > MAXIMUM_CAPACITY)
 initialCapacity = MAXIMUM_CAPACITY;
 if (loadFactor <= 0 || Float.isNaN(loadFactor))
 throw new IllegalArgumentException("Illegal load factor: " +
 loadFactor);
 
 // Find a power of 2 >= initialCapacity
 int capacity = 1;
 while (capacity < initialCapacity)
 capacity <<= 1;
 
 this.loadFactor = loadFactor;
 threshold = (int)(capacity * loadFactor);
 table = new Entry[capacity];
 init();
 }
 
 /**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and the default load factor (0.75).
 *
 * @param initialCapacity the initial capacity.
 * @throws IllegalArgumentException if the initial capacity is negative.
 */
 public HashMap(int initialCapacity) {
 this(initialCapacity, DEFAULT_LOAD_FACTOR);
 }
 
 /**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
 public HashMap() {
 this.loadFactor = DEFAULT_LOAD_FACTOR;
 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
 table = new Entry[DEFAULT_INITIAL_CAPACITY];
 init();
 }
 
 /**
 * Constructs a new <tt>HashMap</tt> with the same mappings as the
 * specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
 * default load factor (0.75) and an initial capacity sufficient to
 * hold the mappings in the specified <tt>Map</tt>.
 *
 * @param m the map whose mappings are to be placed in this map
 * @throws NullPointerException if the specified map is null
 */
 public HashMap(Map<? extends K, ? extends V> m) {
 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
 putAllForCreate(m);
 }
 
 // internal utilities
 
 /**
 * Initialization hook for subclasses. This method is called
 * in all constructors and pseudo-constructors (clone, readObject)
 * after HashMap has been initialized but before any entries have
 * been inserted. (In the absence of this method, readObject would
 * require explicit knowledge of subclasses.)
 */
 void init() {
 }
 
 /**
 * Applies a supplemental hash function to a given hashCode, which
 * defends against poor quality hash functions. This is critical
 * because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
 static int hash(int h) {
 // This function ensures that hashCodes that differ only by
 // constant multiples at each bit position have a bounded
 // number of collisions (approximately 8 at default load factor).
 h ^= (h >>> 20) ^ (h >>> 12);
 return h ^ (h >>> 7) ^ (h >>> 4);
 }
 
 /**
 * Returns index for hash code h.
 */
 static int indexFor(int h, int length) {
 return h & (length-1);
 }
 
 /**
 * Returns the number of key-value mappings in this map.
 *
 * @return the number of key-value mappings in this map
 */
 public int size() {
 return size;
 }
 
 /**
 * Returns <tt>true</tt> if this map contains no key-value mappings.
 *
 * @return <tt>true</tt> if this map contains no key-value mappings
 */
 public boolean isEmpty() {
 return size == 0;
 }
 
 /**
 * Returns the value to which the specified key is mapped,
 * or {@code null} if this map contains no mapping for the key.
 *
 * More formally, if this map contains a mapping from a key
 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
 * key.equals(k))}, then this method returns {@code v}; otherwise
 * it returns {@code null}. (There can be at most one such mapping.)
 *
 * A return value of {@code null} does not necessarily
 * indicate that the map contains no mapping for the key; it's also
 * possible that the map explicitly maps the key to {@code null}.
 * The {@link #containsKey containsKey} operation may be used to
 * distinguish these two cases.
 *
 * @see #put(Object, Object)
 */
 public V get(Object key) {
 if (key == null)
 return getForNullKey();
 int hash = hash(key.hashCode());
 for (Entry<K,V> e = table[indexFor(hash, table.length)];
 e != null;
 e = e.next) {
 Object k;
 if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
 return e.value;
 }
 return null;
 }
 
 /**
 * Offloaded version of get() to look up null keys. Null keys map
 * to index 0. This null case is split out into separate methods
 * for the sake of performance in the two most commonly used
 * operations (get and put), but incorporated with conditionals in
 * others.
 */
 private V getForNullKey() {
 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
 if (e.key == null)
 return e.value;
 }
 return null;
 }
 
 /**
 * Returns <tt>true</tt> if this map contains a mapping for the
 * specified key.
 *
 * @param key The key whose presence in this map is to be tested
 * @return <tt>true</tt> if this map contains a mapping for the specified
 * key.
 */
 public boolean containsKey(Object key) {
 return getEntry(key) != null;
 }
 
 /**
 * Returns the entry associated with the specified key in the
 * HashMap. Returns null if the HashMap contains no mapping
 * for the key.
 */
 final Entry<K,V> getEntry(Object key) {
 int hash = (key == null) ? 0 : hash(key.hashCode());
 for (Entry<K,V> e = table[indexFor(hash, table.length)];
 e != null;
 e = e.next) {
 Object k;
 if (e.hash == hash &&
 ((k = e.key) == key || (key != null && key.equals(k))))
 return e;
 }
 return null;
 }
 
 
 /**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
 * (A <tt>null</tt> return can also indicate that the map
 * previously associated <tt>null</tt> with <tt>key</tt>.)
 */
 public V put(K key, V value) {
 if (key == null)
 return putForNullKey(value);
 int hash = hash(key.hashCode());
 int i = indexFor(hash, table.length);
 for (Entry<K,V> e = table[i]; e != null; e = e.next) {
 Object k;
 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
 V oldValue = e.value;
 e.value = value;
 e.recordAccess(this);
 return oldValue;
 }
 }
 
 modCount++;
 addEntry(hash, key, value, i);
 return null;
 }
 
 /**
 * Offloaded version of put for null keys
 */
 private V putForNullKey(V value) {
 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
 if (e.key == null) {
 V oldValue = e.value;
 e.value = value;
 e.recordAccess(this);
 return oldValue;
 }
 }
 modCount++;
 addEntry(0, null, value, 0);
 return null;
 }
 
 /**
 * This method is used instead of put by constructors and
 * pseudoconstructors (clone, readObject). It does not resize the table,
 * check for comodification, etc. It calls createEntry rather than
 * addEntry.
 */
 private void putForCreate(K key, V value) {
 int hash = (key == null) ? 0 : hash(key.hashCode());
 int i = indexFor(hash, table.length);
 
 /**
 * Look for preexisting entry for key. This will never happen for
 * clone or deserialize. It will only happen for construction if the
 * input Map is a sorted map whose ordering is inconsistent w/ equals.
 */
 for (Entry<K,V> e = table[i]; e != null; e = e.next) {
 Object k;
 if (e.hash == hash &&
 ((k = e.key) == key || (key != null && key.equals(k)))) {
 e.value = value;
 return;
 }
 }
 
 createEntry(hash, key, value, i);
 }
 
 private void putAllForCreate(Map<? extends K, ? extends V> m) {
 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
 putForCreate(e.getKey(), e.getValue());
 }
 
 /**
 * Rehashes the contents of this map into a new array with a
 * larger capacity. This method is called automatically when the
 * number of keys in this map reaches its threshold.
 *
 * If current capacity is MAXIMUM_CAPACITY, this method does not
 * resize the map, but sets threshold to Integer.MAX_VALUE.
 * This has the effect of preventing future calls.
 *
 * @param newCapacity the new capacity, MUST be a power of two;
 * must be greater than current capacity unless current
 * capacity is MAXIMUM_CAPACITY (in which case value
 * is irrelevant).
 */
 void resize(int newCapacity) {
 Entry[] oldTable = table;
 int oldCapacity = oldTable.length;
 if (oldCapacity == MAXIMUM_CAPACITY) {
 threshold = Integer.MAX_VALUE;
 return;
 }
 
 Entry[] newTable = new Entry[newCapacity];
 transfer(newTable);
 table = newTable;
 threshold = (int)(newCapacity * loadFactor);
 }
 
 /**
 * Transfers all entries from current table to newTable.
 */
 void transfer(Entry[] newTable) {
 Entry[] src = table;
 int newCapacity = newTable.length;
 for (int j = 0; j < src.length; j++) {
 Entry<K,V> e = src[j];
 if (e != null) {
 src[j] = null;
 do {
 Entry<K,V> next = e.next;
 int i = indexFor(e.hash, newCapacity);
 e.next = newTable[i];
 newTable[i] = e;
 e = next;
 } while (e != null);
 }
 }
 }
 
 /**
 * Copies all of the mappings from the specified map to this map.
 * These mappings will replace any mappings that this map had for
 * any of the keys currently in the specified map.
 *
 * @param m mappings to be stored in this map
 * @throws NullPointerException if the specified map is null
 */
 public void putAll(Map<? extends K, ? extends V> m) {
 int numKeysToBeAdded = m.size();
 if (numKeysToBeAdded == 0)
 return;
 
 /*
 * Expand the map if the map if the number of mappings to be added
 * is greater than or equal to threshold. This is conservative; the
 * obvious condition is (m.size() + size) >= threshold, but this
 * condition could result in a map with twice the appropriate capacity,
 * if the keys to be added overlap with the keys already in this map.
 * By using the conservative calculation, we subject ourself
 * to at most one extra resize.
 */
 if (numKeysToBeAdded > threshold) {
 int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
 if (targetCapacity > MAXIMUM_CAPACITY)
 targetCapacity = MAXIMUM_CAPACITY;
 int newCapacity = table.length;
 while (newCapacity < targetCapacity)
 newCapacity <<= 1;
 if (newCapacity > table.length)
 resize(newCapacity);
 }
 
 for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
 put(e.getKey(), e.getValue());
 }
 
 /**
 * Removes the mapping for the specified key from this map if present.
 *
 * @param key key whose mapping is to be removed from the map
 * @return the previous value associated with <tt>key</tt>, or
 * <tt>null</tt> if there was no mapping for <tt>key</tt>.
 * (A <tt>null</tt> return can also indicate that the map
 * previously associated <tt>null</tt> with <tt>key</tt>.)
 */
 public V remove(Object key) {
 Entry<K,V> e = removeEntryForKey(key);
 return (e == null ? null : e.value);
 }
 
 /**
 * Removes and returns the entry associated with the specified key
 * in the HashMap. Returns null if the HashMap contains no mapping
 * for this key.
 */
 final Entry<K,V> removeEntryForKey(Object key) {
 int hash = (key == null) ? 0 : hash(key.hashCode());
 int i = indexFor(hash, table.length);
 Entry<K,V> prev = table[i];
 Entry<K,V> e = prev;
 
 while (e != null) {
 Entry<K,V> next = e.next;
 Object k;
 if (e.hash == hash &&
 ((k = e.key) == key || (key != null && key.equals(k)))) {
 modCount++;
 size--;
 if (prev == e)
 table[i] = next;
 else
 prev.next = next;
 e.recordRemoval(this);
 return e;
 }
 prev = e;
 e = next;
 }
 
 return e;
 }
 
 /**
 * Special version of remove for EntrySet.
 */
 final Entry<K,V> removeMapping(Object o) {
 if (!(o instanceof Map.Entry))
 return null;
 
 Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
 Object key = entry.getKey();
 int hash = (key == null) ? 0 : hash(key.hashCode());
 int i = indexFor(hash, table.length);
 Entry<K,V> prev = table[i];
 Entry<K,V> e = prev;
 
 while (e != null) {
 Entry<K,V> next = e.next;
 if (e.hash == hash && e.equals(entry)) {
 modCount++;
 size--;
 if (prev == e)
 table[i] = next;
 else
 prev.next = next;
 e.recordRemoval(this);
 return e;
 }
 prev = e;
 e = next;
 }
 
 return e;
 }
 
 /**
 * Removes all of the mappings from this map.
 * The map will be empty after this call returns.
 */
 public void clear() {
 modCount++;
 Entry[] tab = table;
 for (int i = 0; i < tab.length; i++)
 tab[i] = null;
 size = 0;
 }
 
 /**
 * Returns <tt>true</tt> if this map maps one or more keys to the
 * specified value.
 *
 * @param value value whose presence in this map is to be tested
 * @return <tt>true</tt> if this map maps one or more keys to the
 * specified value
 */
 public boolean containsValue(Object value) {
 if (value == null)
 return containsNullValue();
 
 Entry[] tab = table;
 for (int i = 0; i < tab.length ; i++)
 for (Entry e = tab[i] ; e != null ; e = e.next)
 if (value.equals(e.value))
 return true;
 return false;
 }
 
 /**
 * Special-case code for containsValue with null argument
 */
 private boolean containsNullValue() {
 Entry[] tab = table;
 for (int i = 0; i < tab.length ; i++)
 for (Entry e = tab[i] ; e != null ; e = e.next)
 if (e.value == null)
 return true;
 return false;
 }
 
 /**
 * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
 * values themselves are not cloned.
 *
 * @return a shallow copy of this map
 */
 public Object clone() {
 HashMap<K,V> result = null;
 try {
 result = (HashMap<K,V>)super.clone();
 } catch (CloneNotSupportedException e) {
 // assert false;
 }
 result.table = new Entry[table.length];
 result.entrySet = null;
 result.modCount = 0;
 result.size = 0;
 result.init();
 result.putAllForCreate(this);
 
 return result;
 }
 
 static class Entry<K,V> implements Map.Entry<K,V> {
 final K key;
 V value;
 Entry<K,V> next;
 final int hash;
 
 /**
 * Creates new entry.
 */
 Entry(int h, K k, V v, Entry<K,V> n) {
 value = v;
 next = n;
 key = k;
 hash = h;
 }
 
 public final K getKey() {
 return key;
 }
 
 public final V getValue() {
 return value;
 }
 
 public final V setValue(V newValue) {
 V oldValue = value;
 value = newValue;
 return oldValue;
 }
 
 public final boolean equals(Object o) {
 if (!(o instanceof Map.Entry))
 return false;
 Map.Entry e = (Map.Entry)o;
 Object k1 = getKey();
 Object k2 = e.getKey();
 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
 Object v1 = getValue();
 Object v2 = e.getValue();
 if (v1 == v2 || (v1 != null && v1.equals(v2)))
 return true;
 }
 return false;
 }
 
 public final int hashCode() {
 return (key==null ? 0 : key.hashCode()) ^
 (value==null ? 0 : value.hashCode());
 }
 
 public final String toString() {
 return getKey() + "=" + getValue();
 }
 
 /**
 * This method is invoked whenever the value in an entry is
 * overwritten by an invocation of put(k,v) for a key k that's already
 * in the HashMap.
 */
 void recordAccess(HashMap<K,V> m) {
 }
 
 /**
 * This method is invoked whenever the entry is
 * removed from the table.
 */
 void recordRemoval(HashMap<K,V> m) {
 }
 }
 
 /**
 * Adds a new entry with the specified key, value and hash code to
 * the specified bucket. It is the responsibility of this
 * method to resize the table if appropriate.
 *
 * Subclass overrides this to alter the behavior of put method.
 */
 void addEntry(int hash, K key, V value, int bucketIndex) {
 Entry<K,V> e = table[bucketIndex];
 table[bucketIndex] = new Entry<>(hash, key, value, e);
 if (size++ >= threshold)
 resize(2 * table.length);
 }
 
 /**
 * Like addEntry except that this version is used when creating entries
 * as part of Map construction or "pseudo-construction" (cloning,
 * deserialization). This version needn't worry about resizing the table.
 *
 * Subclass overrides this to alter the behavior of HashMap(Map),
 * clone, and readObject.
 */
 void createEntry(int hash, K key, V value, int bucketIndex) {
 Entry<K,V> e = table[bucketIndex];
 table[bucketIndex] = new Entry<>(hash, key, value, e);
 size++;
 }
 
 private abstract class HashIterator<E> implements Iterator<E> {
 Entry<K,V> next; // next entry to return
 int expectedModCount; // For fast-fail
 int index; // current slot
 Entry<K,V> current; // current entry
 
 HashIterator() {
 expectedModCount = modCount;
 if (size > 0) { // advance to first entry
 Entry[] t = table;
 while (index < t.length && (next = t[index++]) == null)
 ;
 }
 }
 
 public final boolean hasNext() {
 return next != null;
 }
 
 final Entry<K,V> nextEntry() {
 if (modCount != expectedModCount)
 throw new ConcurrentModificationException();
 Entry<K,V> e = next;
 if (e == null)
 throw new NoSuchElementException();
 
 if ((next = e.next) == null) {
 Entry[] t = table;
 while (index < t.length && (next = t[index++]) == null)
 ;
 }
 current = e;
 return e;
 }
 
 public void remove() {
 if (current == null)
 throw new IllegalStateException();
 if (modCount != expectedModCount)
 throw new ConcurrentModificationException();
 Object k = current.key;
 current = null;
 HashMap.this.removeEntryForKey(k);
 expectedModCount = modCount;
 }
 
 }
 
 private final class ValueIterator extends HashIterator<V> {
 public V next() {
 return nextEntry().value;
 }
 }
 
 private final class KeyIterator extends HashIterator<K> {
 public K next() {
 return nextEntry().getKey();
 }
 }
 
 private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
 public Map.Entry<K,V> next() {
 return nextEntry();
 }
 }
 
 // Subclass overrides these to alter behavior of views' iterator() method
 Iterator<K> newKeyIterator() {
 return new KeyIterator();
 }
 Iterator<V> newValueIterator() {
 return new ValueIterator();
 }
 Iterator<Map.Entry<K,V>> newEntryIterator() {
 return new EntryIterator();
 }
 
 
 // Views
 
 private transient Set<Map.Entry<K,V>> entrySet = null;
 
 /**
 * Returns a {@link Set} view of the keys contained in this map.
 * The set is backed by the map, so changes to the map are
 * reflected in the set, and vice-versa. If the map is modified
 * while an iteration over the set is in progress (except through
 * the iterator's own <tt>remove</tt> operation), the results of
 * the iteration are undefined. The set supports element removal,
 * which removes the corresponding mapping from the map, via the
 * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
 * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
 * operations. It does not support the <tt>add</tt> or <tt>addAll</tt>
 * operations.
 */
 public Set<K> keySet() {
 Set<K> ks = keySet;
 return (ks != null ? ks : (keySet = new KeySet()));
 }
 
 private final class KeySet extends AbstractSet<K> {
 public Iterator<K> iterator() {
 return newKeyIterator();
 }
 public int size() {
 return size;
 }
 public boolean contains(Object o) {
 return containsKey(o);
 }
 public boolean remove(Object o) {
 return HashMap.this.removeEntryForKey(o) != null;
 }
 public void clear() {
 HashMap.this.clear();
 }
 }
 
 /**
 * Returns a {@link Collection} view of the values contained in this map.
 * The collection is backed by the map, so changes to the map are
 * reflected in the collection, and vice-versa. If the map is
 * modified while an iteration over the collection is in progress
 * (except through the iterator's own <tt>remove</tt> operation),
 * the results of the iteration are undefined. The collection
 * supports element removal, which removes the corresponding
 * mapping from the map, via the <tt>Iterator.remove</tt>,
 * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
 * <tt>retainAll</tt> and <tt>clear</tt> operations. It does not
 * support the <tt>add</tt> or <tt>addAll</tt> operations.
 */
 public Collection<V> values() {
 Collection<V> vs = values;
 return (vs != null ? vs : (values = new Values()));
 }
 
 private final class Values extends AbstractCollection<V> {
 public Iterator<V> iterator() {
 return newValueIterator();
 }
 public int size() {
 return size;
 }
 public boolean contains(Object o) {
 return containsValue(o);
 }
 public void clear() {
 HashMap.this.clear();
 }
 }
 
 /**
 * Returns a {@link Set} view of the mappings contained in this map.
 * The set is backed by the map, so changes to the map are
 * reflected in the set, and vice-versa. If the map is modified
 * while an iteration over the set is in progress (except through
 * the iterator's own <tt>remove</tt> operation, or through the
 * <tt>setValue</tt> operation on a map entry returned by the
 * iterator) the results of the iteration are undefined. The set
 * supports element removal, which removes the corresponding
 * mapping from the map, via the <tt>Iterator.remove</tt>,
 * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
 * <tt>clear</tt> operations. It does not support the
 * <tt>add</tt> or <tt>addAll</tt> operations.
 *
 * @return a set view of the mappings contained in this map
 */
 public Set<Map.Entry<K,V>> entrySet() {
 return entrySet0();
 }
 
 private Set<Map.Entry<K,V>> entrySet0() {
 Set<Map.Entry<K,V>> es = entrySet;
 return es != null ? es : (entrySet = new EntrySet());
 }
 
 private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
 public Iterator<Map.Entry<K,V>> iterator() {
 return newEntryIterator();
 }
 public boolean contains(Object o) {
 if (!(o instanceof Map.Entry))
 return false;
 Map.Entry<K,V> e = (Map.Entry<K,V>) o;
 Entry<K,V> candidate = getEntry(e.getKey());
 return candidate != null && candidate.equals(e);
 }
 public boolean remove(Object o) {
 return removeMapping(o) != null;
 }
 public int size() {
 return size;
 }
 public void clear() {
 HashMap.this.clear();
 }
 }
 
 /**
 * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
 * serialize it).
 *
 * @serialData The capacity of the HashMap (the length of the
 * bucket array) is emitted (int), followed by the
 * size (an int, the number of key-value
 * mappings), followed by the key (Object) and value (Object)
 * for each key-value mapping. The key-value mappings are
 * emitted in no particular order.
 */
 private void writeObject(java.io.ObjectOutputStream s)
 throws IOException
 {
 Iterator<Map.Entry<K,V>> i =
 (size > 0) ? entrySet0().iterator() : null;
 
 // Write out the threshold, loadfactor, and any hidden stuff
 s.defaultWriteObject();
 
 // Write out number of buckets
 s.writeInt(table.length);
 
 // Write out size (number of Mappings)
 s.writeInt(size);
 
 // Write out keys and values (alternating)
 if (i != null) {
 while (i.hasNext()) {
 Map.Entry<K,V> e = i.next();
 s.writeObject(e.getKey());
 s.writeObject(e.getValue());
 }
 }
 }
 
 private static final long serialVersionUID = 362498820763181265L;
 
 /**
 * Reconstitute the <tt>HashMap</tt> instance from a stream (i.e.,
 * deserialize it).
 */
 private void readObject(java.io.ObjectInputStream s)
 throws IOException, ClassNotFoundException
 {
 // Read in the threshold, loadfactor, and any hidden stuff
 s.defaultReadObject();
 
 // Read in number of buckets and allocate the bucket array;
 int numBuckets = s.readInt();
 table = new Entry[numBuckets];
 
 init(); // Give subclass a chance to do its thing.
 
 // Read in size (number of Mappings)
 int size = s.readInt();
 
 // Read the keys and values, and put the mappings in the HashMap
 for (int i=0; i<size; i++) {
 K key = (K) s.readObject();
 V value = (V) s.readObject();
 putForCreate(key, value);
 }
 }
 
 // These methods are used when serializing HashSets
 int capacity() { return table.length; }
 float loadFactor() { return loadFactor; }
 }