03_HashMap源码分析
2020-12-16 本文已影响0人
Mr_Qiang
存储结构
DbDYjO.png
Dbr8aj.png
默认初始化一个长度为16的数组,加载因子是3/4,每次存入的数据达到原数组的3/4的时候,就扩容,扩容为原来的两倍.当hash冲突的时候就把元素挂在数组下面,每个角标下的就是一个链表结构.如果链表长度大于8且数组长度大于64,就把链表转成红黑树.反之如果移除元素后树的元素个数小于6,则把树转成链表.
需要存入的数据会封装成一个Node节点,先是对要存入的数据的key进行hash计算,求出在数组中的下标,如果数组中的下表有元素了,且key不相等,在看已有的元素是不是树类型,如果不是,遍历链表查看key是不是等于链表中的key,如果都不相等,就把当前元素挂在链表的最后一个节点.
如果数组的第一个元素为树结构,就把当前元素挂在树下.
主要字段
默认的容量
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
默认的初始容量为16,可以设置,但是必须是2^n
最大的容量
* 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;
最大容量2^30
默认的加载因子
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
默认是3/4,当超过3/4的时候进行扩容.
树化的阈值
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
当桶的深度达到8的时候,考虑由链表转成树结构.
不树化的阈值
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
桶的深读小于6时,考虑由树结构转链表
最小的树化容量
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
可进行树型化的最小表容量。
Node节点
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
一个由hash值,key,value和nextNode组成的节点.
主要方法
计算key的哈希值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
计算数组长度的方法
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
构造方法
- public HashMap(int initialCapacity, float loadFactor);
- public HashMap(int initialCapacity);
- public HashMap();
put(K k,V v)方法
- Node[]是否为空,如果为空,初始一个长度为16,加载因子为16*0.75的数组,n为数组的长度.
- (n-1)&key的hash值寻找在数组中的角标.
- 如果p角标上的元素为Null,则这是第一个元素,直接放在该位置.
- 如果p角标的元素不为null:
- 如果p角标的元素的key和本次需要添加的key相同,则把Node[]p赋值为e
- 如果p角标的元素key和本次添加的key不同,且Node[p]为树结构.把本次元素添加到树上,e=null
- 且Node[p]不为树结构,链表结构,把当前元素挂在链表的尾部.如果链表的深度超过了树化阈值(8),把链表转成树.e=null
- 如果e==null,就是之前发现的已经存在的key相同的元素了.根据onlyIfAbsent(默认false),是替换之前的value还是使用之前的value放弃现在的value.
- 数组++size,如果size>threshold(16),进行扩容.
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//1. 初始化一个2^n次方的数组,n为数组的长度
n = (tab = resize()).length;
//2. 用数组长度-1与上key的hash值,如果为null,说明这是这个数组链表上的第一个元素,就把这个元素封装成Node放在这个数组角标下,且这个node的next=null.
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//2.2如果这个数组下面有元素了
//2.2.1 如果hash相同,且key相同,就把之前的元素作为现在的
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//2.2.2 如果key不相同且数组角标上的这个元素为ThreeNode类型,就把这个节点添加到树上.
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//2.2.3 如果不是树类型,是链表类型,遍历把当前的元素放到这个链表的尾部.
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//2.2.3.1 如果链表的深读>8了,就树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//2.3 如果当前元素不为null,就是之前已经存在key相同的了.
//2.3.1根据条件替换之前的或者用之前的元素.
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果长度超过了阈值,进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
get(Object obj)方法
- 根据Key&n-1找到它在数组中位置的角标.如果数组中这个角标的元素不为null
- 如果当前数组角标的这个元素的key和要查找的key相同,就直接返回该元素.
- 如果数组该角标下的元素的key和我要找的key不相等,如果数组中该角标的第一个元素为树类型,就则行树的查找,反之进行链表查找.
- 如果数组中该角标的元素为null,则放回null
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
resize() 扩容的方法
- 计算数组的长度和扩容阈值
- 进行扩容后，重新计算角标位置，搬迁之前的元素。搬迁元素的规则是key.hash&oldCap，看结果是否为0，如果为0,则保留在新数组的原来角标位置。如果不为0，则放在新数组的[j+oldCap]的位置，j为在之前的角标位置，oldCap为之前的数组长度。
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
// 1. 获取当前数组的长度，如果长度>0，则进行扩容，计算新的容量为原来的2倍。扩容阈值为原来的2倍。
// 1.1 如果当前数组容量为0，扩容阈值为0，则说明是第一次，使用默认容量16，扩容阈值为16*0.75
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//3. 根据上面计算的容量，创建新的数组。以下是把旧的数组元素搬迁到新的数组。
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果之前的数组角标上就一个元素，不是长链表，就重新根据现在的数组长度计算新的角标，把之前的元素放在新的位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//如果之前角标上不止一个元素，且元素为Three类型
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
/* e:为之前角标下的第一个元素。以下为挪元素的过程。
以下简之：把之前链表超过8的元素，通过（(e.hash & oldCap) == 0）分成两组，
一组是hiNode,一组是loNode，lo的放在新的数组的原来的角标下,hiNode放在新的数组[j+oldCap]上，j为原来的角标，oldCap为原来的长
度*/
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
测试HashMap的扩容机制.
==默认的数组初始容量为16,加载因子是3/4=0.75,每次扩容长度为之前的两倍.==
import java.lang.reflect.Field;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.HashMap;
/**
* @Author: yaoqiang
* @Date: 2020/12/4 9:37
* @Description:
*/
@Slf4j
public class HashMapDemo {
public static void main(String[] args) throws IllegalAccessException, NoSuchFieldException, InvocationTargetException, NoSuchMethodException {
HashMap<Integer, Object> map = new HashMap<>();
Field thresholdField = map.getClass().getDeclaredField("threshold");
Method capacityMethod = map.getClass().getDeclaredMethod("capacity", null);
thresholdField.setAccessible(true);
capacityMethod.setAccessible(true);
for (int i = 0; i < 100; i++) {
map.put(i, null);
int thre = (int) thresholdField.get(map);
int invoke = (int) capacityMethod.invoke(map, null);
log.debug("table size: {},put key-{} ,threshold: {}", invoke, i, thre);
}
}
}
Db3YdO.png
文档注释
/**
* 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.
* 基于Hash表的Map实现接口.实现了所有的map操作，允许null 值和key,HashMap和Hashtable大致等价，除了他是不同步和允许Null。这个类不保证map的有序；特别，不保证随着时间的推移，保持不变。
*
* <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.
* 这个实现的基本操作为get()和put(),假设hash方法分散节点在适当的桶上。迭代集合需要的时间和HashMap桶上的元素加上HashMap的长度（capacity）成比例。因此，对于迭代器不要设置HashMap初始长度太高或者扩容因此态度，这是非超重要的。
*
*
* <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.
*
一个HashMap实例有两个参数影响性能：初始容量和加载因子。初始容量是Hash表上桶数（数组长度），Hash表创建的时候就简单的设置了他的容量。加载因子是一个测量hash表多满后就允许去自动扩容。当hash表容量超过加载因子和当前的容量，hash表会重新hash计算（内部数据结构会重建），所以Hash表的桶有大约这两个参数。
*
* <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.
* 默认情况下，加载因子是0.75影响一个好的权衡时间和空间消费。加载因子值较高会减少了空间的开销，但是增加了查找的成本（比如100%满的时候才扩容，减少了空间，但是每个桶上挂的元素就更多）。根据预期要放入map的键值对数量和加载因子去设置初始容量,以便去健身rehash的次数。如果初始容量高于最大的键值对数量除以加载因子，rehash将不会发生。
*
* <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.
* 如果一些映射需要存在HashMap实例，创建一个相当大的初始容量去允许存储映射 比让它自动根据需要去扩容要更高效。注意使用一些相同hash码的key是一个降低hash表的性能。去改善影响，当keys去Comparable（）.这个类可能去使用比较排序让大部分的key打破关系.
*
* <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>
* *注意这是线程不安全的,如果多线程并发的去访问hashmap,且有至少有一个线程去修改这个map结构,者必须在外边加synchronized.(结构改变是一些添加或者删除一个或者多个映射,仅仅改变值线管的已经存在的key不是一个结构的修改.) 这是典型的在封装map的对象上通过同步锁完成.
* 如果这类对象不存在,必须使用包装过的synchronizedMap.这是最好是在创建时期进行,去防止在意外不安全的访问map.
* <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.
*
*iterators返回通过所有这个类的""集合视图方法"快速的失败:如果在这个迭代器创建后的修改map结构,除了是通过迭代器去移除元素,迭代器会报"ConcurrentModificationException".因此面对并发的修改,迭代器的快速失败和清除,而不是冒险武断的,不确定的行为在未来一个不确定的时间.
* <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>
*
*注意这个快速失败的行为迭代器不能保证,通常讲,不可能的保证在没有同步的并发修改下.快速失败迭代器抛出"ConcurrentModificationException"在一个尽最大努力的基准.
因此,这可能错误的去写一些程序依靠这个异常去正确性:迭代器的快速的失败行为可以使用仅仅在发现bug.
