public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {}
HashMap继承了AbstractMap类,实现Map接口
public abstract class AbstractMap<K,V> implements Map<K,V> {}
其中AbstractMap类又实现了Map接口,此处为作者承认的失误,但影响不大,所以一直没有修改(任性)
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; }
设置默认的加载因子为0.75f,用于之后的扩容计算
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
将输入的参数以及默认的加载因子传入到两个参数的构造函数中
public HashMap(int initialCapacity, float loadFactor) { //此处省略了一些健壮性的代码,增强可读性 this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); }
加载因子并不一直是0.75f,如果调用了两个参数的构造方法,可以选择自己想要的扩容因子。
threshold为阈值(数组到达这个值后开始扩容),但这里是用来占时保存初始容器的大小的。
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; }
看到这些一堆右移(不带符号位)和或(|)的操作直接懵了。此时你可以随便输入一个值带进去计算,尝试几次之后,你会发现,不论你输入的是(X)多少,它都会返回给你一个比X大,并且是2的n次幂-1的数。(输入3返回3,输入6返回的是7,输入14返回15,以此类推)。原理大概就是将一个数转化成二进制后,将最高位的1,不停的向右移动并且或上之前的数,这样的操作保证出来的数的二进制全是1(2的n次幂-1),最后在+1后,就变成2的n次幂。然后将这个值赋给threshold。
看过1.7版本的应该会很疑惑,我也很疑惑,目前就只有给loadFactor 和threshold赋值,容器的初始化大小都没有给,这里应该就是优化的点:当你创建一个HashMap时,你都还没有用(往里面put值),我为什么要给你初始化大小。个人感觉有点懒加载的含义。
都知道HashMap是数组加链表的数据结构,那么问题来了,数组只能放相同的数据类型,那么HashMap的数组是什么类型呢?
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; }
以上代码为简化后的代码,这个就是1.8中数组的元素(1.7中为Entry对象)
transient Node<K,V>[] table;
这个就是HashMap底层的数组,transient好像是为了防止序列化的,暂时可以忽略
个人感觉1.8中,最核心的代码应该就是在put这个方法中了(一个方法解决所有问题),废话不多数了,直接看代码
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
看源码总是会遇到这种情况,一个方法里就一个方法,每次都要再点一层才能看到(套娃),但这里有个hash(key)方法,差点遗漏。。。
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
这个方法的就是计算当前你输入的key的hashcode值(用于后面的数组位置计算)
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. n = (tab = resize()).length;// 步骤 2. if ((p = tab[i = (n - 1) & hash]) == null)// 步骤 3. tab[i] = newNode(hash, key, value, null); // 步骤 4. else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); 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; } } 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; }
上面的一些代码我都会简化,同样这个也是简化完的,只不过是一点都没有简化,每句代码都是精髓
整体流程:当刚创建完一个HashMap后,开始往里放入第一个键值对时,先会通过步骤1进入,然后通过resize() 方法给集合初始化大小,然后通过步骤3,进入步骤4,将Node放入到数组中去。所以应该先看 resize() 方法
resize() 方法也比较长,此处我总结了一下,大概就是3个if选一个,然后再加上一个if。
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 中的代码,此处规定了数组扩容的大小为 <<1,及原始大小乘2,同时新的阈值(threshold)也是 <<1
else if (oldThr > 0) newCap = oldThr;
在三选一的准备中,oldThr就是我们上面一堆右移操作得到的2的n次幂的结果(threshold),此结果在此处用来赋值给newCap(其实就是集合初始化的大小)
else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); }
当new HashMap() 时,如果选择无参的构造函数,就会执行第三个选择,初始化集合大小为
DEFAULT_INITIAL_CAPACITY (1<<4 = 16), 阈值为(16 * 0.75 = 12)
当新放入的键值对的位置已经有其他键值对时:
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;
先比较原来位置的和新加入元素的key的hash值,如果相同,在判断key是否是同一个对象,如果不是,再去比较key的值是否相同。(此处有个隐藏的优化点,当key 是String 类型时,== 比较会覆盖掉后面的equals 比较,提高效率)