亲宝软件园·资讯

展开

解析hashmap Java源码解析HashMap简介

李灿辉 人气:1

本文基于jdk1.8进行分析

HashMap是java开发中可以说必然会用到的一个集合。本文就HashMap的源码实现进行分析。

首先看一下源码中类的javadoc注释对HashMap的解释。如下图。HashMap是对Map接口的基于hash表的实现。这个实现提供了map的所有可选操作,并且允许null值(可以多个)和一个null的key(仅限一个)。HashMap和HashTable十分相似,除了HashMap是非同步的且允许null元素。这个类不保证map里的顺序,更进一步,随着时间的推移,它甚至不保证顺序一直不变。

这个实现为get和put这样的基本操作提供常量级性能,它假设hash函数把元素们比较好的分散到各个桶里。用迭代器遍历集合需要的时间,和HashMap的容量与HashMap里的Entry数量的和成正比。所以,如果遍历性能很重要的话,一定不要把初始容量设置的太大,或者把负载因子设置的太小。

一个hashmap有两个影响它的性能的参数,初始容量和负载因子。容量是哈希表中桶的数量,初始容量就是创建哈希表时桶的数量。负载银子是哈希表的容量自动扩容前哈希表能够达到多满。当哈希表中条目的数量超过当前容量和负载因子的乘积后,哈希表会进行重新哈希(也就是,内部数据结构重建),以使哈希表大约拥有2倍数量的桶。

作为一个通常的规则,默认负载银子(0.75) 提供了一个时间和空间的比较好的平衡。更高的负载因子会降低空间消耗但是会增加查找的消耗。当设置初始容量时,哈希表中期望的条目数量和它的负载因子应该考虑在内,以尽可能的减小重新哈希的次数。如果初始容量比条目最大数量除以负载因子还大,那么重新哈希操作就不会发生。

如果许多entry需要存储在哈希表中,用能够容纳entry的足够大的容量来创建哈希表,比让它在需要的时候自动扩容更有效率。请注意,使用多个hash值相等的key肯定会降低任何哈希表的效率。

请注意这个实现不是同步的。如果多个线程同时访问哈希表,并且至少有一个线程会修改哈希表的结构,那么哈希表外部必须进行同步。

/**
 * 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.
 * <p>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.
 * <p>An instance of <tt>HashMap</tt> has two parameters that affect its
 * performance: <i>initial capacity</i> and <i>load factor</i>. The
 * <i>capacity</i> 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
 * <i>load factor</i> 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 <i>rehashed</i> (that is, internal data
 * structures are rebuilt) so that the hash table has approximately twice the
 * number of buckets.
 * <p>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.
 * <p>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 using
 * many keys with the same {@code hashCode()} is a sure way to slow
 * down performance of any hash table. To ameliorate impact, when keys
 * are {@link Comparable}, this class may use comparison order among
 * keys to help break ties.
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access a hash map concurrently, and at least one of
 * the threads modifies the map structurally, it <i>must</i> 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>
 * <p>The iterators returned by all of this class's "collection view methods"
 * are <i>fail-fast</i>: 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.
 * <p>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: <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i>
 * <p>This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html" rel="external nofollow" >
 * 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
 **/

This is the end。

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对的支持。如果你想了解更多相关内容请查看下面相关链接

加载全部内容

相关教程
猜你喜欢
用户评论