由浅入深解析HashMap系列二---扩容

前面简单的实现了hashmap的增删查功能，这一章节主要是介绍扩容（不考虑冲突），当数组元素达到一定阈值时，需要扩容，扩容之后，需要对原来的数组中的元素进行再次hash。在开始之前先介绍几个概念：

基本概念

初始容量：DEFAULT_INITIAL_CAPACITY = 1 << 4。在JDK1.8中，默认的容量为16。在初始化HashMap时,并不会按照这个初始容量初始化数组，而是在第一个put元素时，才初始化数组。

加载因子：DEFAULT_LOAD_FACTOR = 0.75f ，哈希表在其容量自动增加之前可以达到多满的一种尺度。

阈值：threshold，等于capacity * load factor。比如说：初始时，初始容量为16，加载因子为0.75，则阈值为12。当哈希表中的节点个数为12个时，就需要扩容。也许按照我们的思维习惯，当节点个数达到16时，才扩容。加载因子过低，如果扩容之后，不再有数据增加，增加了空间开销；加载因子过高虽然减少了空间开销，但同时也增加了查询成本，所以需要对其有这个折中。

扩容操作

具体步骤如下：

1)获取新的容量和阈值。根据old capacity，经过扩容算法，获取new capacity和threshold。扩容算法：新的容量=原来的容量*2；新的阈值=原来的阈值*2；初始容量=16；初始阈值=初始容量*加载因子=16*0.75。
2)对原有数组元素重新分布。前一章节提到过，下标index的获取与数组长度也就是capacity有关，通过上面获取的新的capacity,重新计算节点下标，也就是对原有哈希表中的元素再散列到新的哈希表中。
注意：当原有容量已经达到最大容量时，就不允许再扩容，而是返回初始数组。

 1  /**
 2      * 1)获取新的容量和阈值。
 3      * 2)对原有数组进行再散列。
 4      * 注意：当原有容量已经达到最大容量时，就不允许再扩容，而是返回初始数组。
 5      * 新的容量=原来的容量*2；新的阈值=原来的阈值*2；初始容量=16；初始阈值=初始容量*加载因子=16*0.75
 6      * @return
 7      */
 8     final Node<K,V>[] resize() {
 9         Node<K,V>[] oldTab = table;//oldTab保存扩容前的数组
10         int oldCap = (oldTab == null) ? 0 : oldTab.length;//如果扩容前数组为Null则oldCap为0,否则为扩容前数组长度
11       //旧的扩容大小，一般等于容量*loadfactor。当数组大小达到阈值threshold时，就扩容。注意并不是数组满了才扩容
12         int oldThr = threshold; 
13         //初始化新的容量和阈值
14         int newCap, newThr = 0;
15         //旧的容量大于0
16         if (oldCap > 0) {
17             //这样设计应该是不允许扩容了，已经达到极限了。
18             if (oldCap >= MAXIMUM_CAPACITY) {//旧的容量达到最大容量时，阈值设置为最大整数。返回原来的数组。
19                 threshold = Integer.MAX_VALUE;
20                 return oldTab;
21             }
22             //新的容量=旧的容量*2。新的阈值=旧的阈值*2
23             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
24                      oldCap >= DEFAULT_INITIAL_CAPACITY)
25                 newThr = oldThr << 1; // double threshold
26         }//旧的容量小于等于0时，若旧的阈值大于0，新的阈值旧等于旧的阈值。
27         else if (oldThr > 0) // initial capacity was placed in threshold
28             newCap = oldThr;
29         //旧的容量小于等于0，旧的阈值小于等于0，新的容量和阈值都等于默认值。这一般是初次调用hashmap时触发
30         //阈值=加载因子*初始容量=0.75*16=12。也就是当初次添加元素达到12个时，就扩容。
31         else {               // zero initial threshold signifies using defaults
32             newCap = DEFAULT_INITIAL_CAPACITY;
33             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
34         }
35         //对阈值进行设计，临界条件的判断，不明白到这一步阈值为啥还会为0
36         if (newThr == 0) {
37             float ft = (float)newCap * loadFactor;
38             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
39                       (int)ft : Integer.MAX_VALUE);
40         }
41         //设置阈值
42         threshold = newThr; 
43         //初始化新的数组，对原有的数组进行再散列
44             Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
45         table = newTab;
46         if (oldTab != null) {
47             for (int j = 0; j < oldCap; ++j) {
48                 Node<K,V> e;
49                 if ((e = oldTab[j]) != null) {
50                     oldTab[j] = null;
51                     if (e.next == null)
52                         newTab[e.hash & (newCap - 1)] = e;
53                 }
54             }
55         }
56         return newTab;
57     }

View Code

put操作

put操作在上一节的基础上会添加一些功能，如下：

1）判断数组(Node<K,V>[] table)是否为null或者长度为0。上节为了简便在初始化HashMap时，构建一个长度为100的数组，而在这一章节中，初始化数组的操作延迟到第一次添加元素的时候。故在put操作时，要判断数组的长度是不是为0或者为Null。

2）当数组中元素的个数达到给定阈值时，调用resize函数扩容。

 1 /**
 2      * 添加。
 3      * 考虑扩容，但是不考虑冲突
 4      * @param key
 5      * @param value
 6      * @return
 7      */
 8     public V put(K key, V value)
 9     {
10         //创建新节点
11         Node<K,V>[] tab;Node<K,V> p; int n, i;
12         //一般初次才会走这个步骤
13         if ((tab = table) == null || (n = tab.length) == 0)
14             n = (tab = resize()).length;
15         //对key值进行hash
16         int hash=hash(key);
17         //目前没有考虑hash冲突
18         table[i = (n - 1) & hash]=newNode(hash,key,value,null);
19         if(++size>threshold)//当达到阈值时，需要扩容
20             resize();
21         //返回原来的值
22         return value;
23         
24     }

View Code

只有在添加元素的时候，才需要考虑resize，在删除、查询时，不需要考虑，所以remove、get函数和上一章节是一样的。

个人观点：因resize导致重新hash，节点重新散列，故初始容量和加载因子的设置还是很重要的。