本文基于jdk1.8進行分析
hashmap是java開發(fā)中可以說必然會用到的一個集合。本文就hashmap的源碼實現(xiàn)進行分析。
首先看一下源碼中類的javadoc注釋對hashmap的解釋。如下圖。hashmap是對map接口的基于hash表的實現(xiàn)。這個實現(xiàn)提供了map的所有可選操作，并且允許null值（可以多個）和一個null的key（僅限一個）。hashmap和hashtable十分相似，除了hashmap是非同步的且允許null元素。這個類不保證map里的順序，更進一步，隨著時間的推移，它甚至不保證順序一直不變。
這個實現(xiàn)為get和put這樣的基本操作提供常量級性能，它假設(shè)hash函數(shù)把元素們比較好的分散到各個桶里。用迭代器遍歷集合需要的時間，和hashmap的容量與hashmap里的entry數(shù)量的和成正比。所以，如果遍歷性能很重要的話，一定不要把初始容量設(shè)置的太大，或者把負載因子設(shè)置的太小。
一個hashmap有兩個影響它的性能的參數(shù)，初始容量和負載因子。容量是哈希表中桶的數(shù)量，初始容量就是創(chuàng)建哈希表時桶的數(shù)量。負載銀子是哈希表的容量自動擴容前哈希表能夠達到多滿。當哈希表中條目的數(shù)量超過當前容量和負載因子的乘積后，哈希表會進行重新哈希（也就是，內(nèi)部數(shù)據(jù)結(jié)構(gòu)重建），以使哈希表大約擁有2倍數(shù)量的桶。
作為一個通常的規(guī)則，默認負載銀子(0.75) 提供了一個時間和空間的比較好的平衡。更高的負載因子會降低空間消耗但是會增加查找的消耗。當設(shè)置初始容量時，哈希表中期望的條目數(shù)量和它的負載因子應該考慮在內(nèi)，以盡可能的減小重新哈希的次數(shù)。如果初始容量比條目最大數(shù)量除以負載因子還大，那么重新哈希操作就不會發(fā)生。
如果許多entry需要存儲在哈希表中，用能夠容納entry的足夠大的容量來創(chuàng)建哈希表，比讓它在需要的時候自動擴容更有效率。請注意，使用多個hash值相等的key肯定會降低任何哈希表的效率。
請注意這個實現(xiàn)不是同步的。如果多個線程同時訪問哈希表，并且至少有一個線程會修改哈希表的結(jié)構(gòu)，那么哈希表外部必須進行同步。
|
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。
總結(jié)
以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對服務(wù)器之家的支持。如果你想了解更多相關(guān)內(nèi)容請查看下面相關(guān)鏈接
原文鏈接：https://blog.csdn.net/li_canhui/article/details/85076521
