HashMap源码学习

/** * Hash table based implementation of theMapinterface. This * implementation provides all of the optional map operations, and permits *nullvalues and thenullkey. (TheHashMap* class is roughly equivalent toHashtable, 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. * *

hash table 基于map 接口的实现。这个实现提供了所有的map操作选项，且允许null 值value和null 键 key。HashMap基本与Hashtable相等，除了非线程安全和允许null。HashMap不能确定map的固定顺序，事实上，HashMap不能保证随着时间推移，map的固定顺序

This implementation provides constant-time performance for the basic * operations (getandput), assuming the hash function * disperses the elements properly among the buckets.  Iteration over * collection views requires time proportional to the "capacity" of the *HashMapinstance (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. * *

如果hash方法将元素适当的置于桶中，实现的类能够使得get和put等基本操作算法的时间复杂度为常量级别。在集合视图上迭代需要的时间与HashMap实例的capacity（桶的数量）加上他的size（mapping中键值对的数量）的数量成正比。因此，如果该对象迭代使用的较多，则对于初始化时的capacity不应设置过大（factor不应设置过小）。

An instance ofHashMap has two parameters that affect its * performance:initial capacityandload factor.  The *capacityis 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 factoris 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 isrehashed(that is, internal data * structures are rebuilt) so that the hash table has approximately twice the * number of buckets. * *

该部分与hashtable一样，意思是初始化时的两个重要参数，capacity和factor

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 *HashMapclass, includinggetandput).  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 aHashMapinstance, * 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, itmustbe * 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:

*  Map m = Collections.synchronizedMap(new HashMap(...));

注意：HashMap不是线程安全的，使用Collection.synchronizedMap在创建时包装该类。

* *

The iterators returned by all of this class's "collection view methods" * arefail-fast: if the map is structurally modified at any time after * the iterator is created, in any way except through the iterator's own *removemethod, 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 * throwConcurrentModificationExceptionon 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 * * Java Collections Framework. * * @paramthe type of keys maintained by this map * @param 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

*/