本文基于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肯定会降低任何哈希表的效率。
请注意这个实现不是同步的。如果多个线程同时访问哈希表，并且至少有一个线程会修改哈希表的结构，那么哈希表外部必须进行同步。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
/**
* 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。
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对服务器之家的支持。如果你想了解更多相关内容请查看下面相关链接
原文链接：https://blog.csdn.net/li_canhui/article/details/85076521