我们再看看构造方法
构造方法
/** * Constructs an empty HashMap with the specified initial * capacity and the default load factor (0.75). * * @param initialCapacity the initial capacity. * @throws IllegalArgumentException if the initial capacity is negative. * 传入初始容量大小,使用默认负载因子值 来初始化HashMap对象 */public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR);}/** * Constructs an empty HashMap with the default initial capacity * (16) and the default load factor (0.75). * 默认容量和负载因子 */public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}/** * Constructs an empty HashMap with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive * 传入初始容量大小和负载因子 来初始化HashMap对象 */public HashMap(int initialCapacity, float loadFactor) { // 初始容量不能小于0,否则报错 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); // 初始容量不能大于最大值,否则为最大值 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; //负载因子不能小于或等于0,不能为非数字 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // 初始化负载因子 this.loadFactor = loadFactor; // 初始化threshold大小 this.threshold = tableSizeFor(initialCapacity);}/** * Returns a power of two size for the given target capacity. * 找到大于或等于 cap 的最小2的整数次幂的数 */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;}
在这源码中,loadFactor负载因子是一个非常重要的参数,因为他能够反映HashMap桶数组的使用情况, 这样的话,HashMap的时间复杂度就会出现不同的改变。
当这个负载因子属于低负载因子的时候,HashMap所能够容纳的键值对数量就是偏少的,扩容后,重新将键值对 存储在桶数组中,键与键之间产生的碰撞会下降,链表的长度也会随之变短。
但是如果增加负载因子当这个负载因子大于1的时候,HashMap所能够容纳的键值对就会变多,这样碰撞就会增加, 这样的话链表的长度也会增加,
一般情况下负载因子我们都不会去修改。都是默认的0.75。
扩容机制
resize()这个方法就是重新计算容量的一个方法,我们看看源码:
/** * 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[] resize() { //引用扩容前的Entry数组 Node[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { // 扩容前的数组大小如果已经达到最大(2^30)了 //在这里去判断是否达到最大的大小 if (oldCap >= MAXIMUM_CAPACITY) { //修改阈值为int的最大值(2^31-1),这样以后就不会扩容了 threshold = Integer.MAX_VALUE; return oldTab; } // 如果扩容后小于最大值 而且 旧数组桶大于初始容量16, 阈值左移1(扩大2倍) else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } // 如果数组桶容量<=0 且 旧阈值 >0 else if (oldThr > 0) // initial capacity was placed in threshold //新的容量就等于旧的阀值 newCap = oldThr; else { // zero initial threshold signifies using defaults // 如果数组桶容量<=0 且 旧阈值 <=0 // 新容量=默认容量 // 新阈值= 负载因子*默认容量 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 如果新阈值为0 if (newThr == 0) { // 重新计算阈值 float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //在这里就会 更新阈值 threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) //创建新的数组 Node[] newTab = (Node[])new Node[newCap]; // 覆盖数组桶 table = newTab; // 如果旧数组桶不是空,则遍历桶数组,并将键值对映射到新的桶数组中 //在这里还有一点诡异的,1.7是不存在后边红黑树的,但是1.8就是有红黑树 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; // 如果是红黑树 else if (e instanceof TreeNode) // 重新映射时,然后对红黑树进行拆分 ((TreeNode)e).split(this, newTab, j, oldCap); else { // preserve order // 如果不是红黑树,那也就是说他链表长度没有超过8,那么还是链表, //那么还是会按照链表处理 Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; // 遍历链表,并将链表节点按原顺序进行分组 do { 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;}
所以说在经过resize这个方法之后,元素的位置要么就是在原来的位置,要么就是在原来的位置移动2次幂的位置上。 源码上的注释也是可以翻译出来的
/** * 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 如果为null,则分配符合字段阈值中保存的初始容量目标。 否则,因为我们使用的是2次幂扩展, 所以每个bin中的元素必须保持相同的索引,或者在新表中以2的偏移量移动。 */ final Node[] resize() .....
所以说他的扩容其实很有意思,就有了三种不同的扩容方式了,
- 在HashMap刚初始化的时候,使用默认的构造初始化,会返回一个空的table,并且 thershold为0,因此第一次扩容的时候默认值就会是16. 同时再去计算thershold = DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY = 16*0.75 = 12.
- 如果说指定初始容量的初始HashMap的时候,那么这时候计算这个threshold的时候就变成了 threshold = DEFAULT_LOAD_FACTOR * threshold(当前的容量)
- 如果HashMap不是第一次扩容,已经扩容过了,那么每次table的容量和threshold也会变成原来的2倍。
之前看1.7的源码的时候,是没有这个红黑树的,而是在1.8 之后做了相应的优化。 使用的是2次幂的扩展(指长度扩为原来2倍)。 而且在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,这样子他就剩下了计算hash的时间了。
看完这个源码,翻译了一节节的英文,算是大致明白了一点源码内容了,有什么讨论的问题咱们可以一起讨论一下,感谢观看。
閱讀更多 科技伍小黑 的文章