面试重点之从源码分析HashMap和ArrayList在存储、扩容等方面的区别

小灰灰 2022-10-25 12:46 134阅读 0赞

### 目录 ###

*  两者相似的地方
 *  两者的差别
 *   *  1. 默认容量大小及其他参数的区别
     *  2. 扩容时的区别
     *  3. 存入数据时的区别
     *  4. 重点汇总

HashMap和ArrayList这两个类由于在日常开发中会经常使用，所以是比较常见的面试考查点，面试官也会通过询问该部分内容了解对这部分的熟悉程度。

# 两者相似的地方 #

两者是有一定的相似性的，例如：

*  都有默认初始容量及最大值
 *  都会进行扩容操作
 *  底层实现都是数组（HashMap为链表数组，JDK8之后为链表-红黑树数组，本质上依然是数组结构）

但是两者又是有很大差别，最大的差别就是HashMap会进行Hash运算，ArrayList则不会，具体容量默认值和负载因子，以及扩容策略也是有很大区别，下面就进行一个对比，以便于更清晰地展示这两个数据集合的特点和差别。

\**说明: 以下均基于JDK1.8源码*

# 两者的差别 #

## 1. 默认容量大小及其他参数的区别 ##

首先，HashMap和ArrayList中均设置了默认的容量值，如下：

//HashMap的默认容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    //ArrayList的默认容量
    private static final int DEFAULT_CAPACITY = 10;

可以看到，两者从代码风格上就有一定差异，HashMap没有使用访问修饰符，ArrayList使用了，很明显是两个不同风格的开发人员进行的开发。至于HashMap为什么使用16，建议看这篇文章[https://www.iteye.com/topic/539465][https_www.iteye.com_topic_539465]。ArrayList为什么默认为10呢？看网上说的，认为这是一个比较折中的方式，设置为1的话太小，设置为100的话又会太多，所以就设置为10。其实从日常生活经验也可以感觉到，10就是日常事务中的一个分界线，10以内是少，10以上就算多了，我想这就是设置默认10的原因。

除了默认容量之外，HashMap和ArrayList在进行数据扩容的时候，都设定了一些标准，具体来说就是三个方面：

1.  **达到什么条件时扩容**
2.  **扩容多少**
3.  **最大值是多少**

看源码，在HashMap中：

//HashMap的负载因子，默认值0.75
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //HashMap容量的最大值，默认值2的30次方
    static final int MAXIMUM_CAPACITY = 1 << 30;

在ArrayList中：

//ArrayList默认最大数组值，默认值2的31次方-8
     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

可以看到HashMap和ArrayList中都规定了默认最大容量值，且不一致，HashMap最大容量值为2的30次方，即Integer.MAX\_VALUE的一半，ArrayList则是接近Integer.MAX\_VALUE，为Integer.MAX\_VALUE - 8;

同时，HashMap包含DEFAULT\_LOAD\_FACTOR，而ArrayList则没有，该值为负载因子，用于决定HashMap中元素数据达到多少时进行扩容，默认为0.75，则达到现有容量的0.75即会对容量进行扩容。

到这里，依然还有两个问题：

*  **HashMap是达到0.75时扩容，ArrayList达到多少呢？**
 *  **HashMap和ArrayList扩容是分别扩容多少呢？**

来看扩容的源码：

## 2. 扩容时的区别 ##

先看HashMap扩容的源码：

/** * 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. * 初始化或加倍表大小。如果为空，则根据字段threshold中的initialcapacity目标进行分配。否则，因为 * 我们使用的是二次幂展开，所以每个bin中的元素要么保持在相同的下标，要么在新表中以二次幂偏移量移动。 * @return the table */
    	final Node<K, V>[] resize() { 
    		Node<K, V>[] oldTab = table;//原table
    		int oldCap = (oldTab == null) ? 0 : oldTab.length;//原容量
    		int oldThr = threshold;//原阈值
    		int newCap, newThr = 0;//新容量、新阈值
    		if (oldCap > 0) { //原容量大于0
    			if (oldCap >= MAXIMUM_CAPACITY) { //原容量大于等于最大容量
    				threshold = Integer.MAX_VALUE;//Integer.MAX_VALUE作为阈值
    				return oldTab;
    			} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)//原容量的2倍小于最大容量，且原容量大于默认初始化容量
    				newThr = oldThr << 1; //新阈值为原阈值的2倍（即原容量扩容，阈值也跟着扩容）
    		} else if (oldThr > 0) // 原阈值大于0
    			newCap = oldThr;//将原阈值作为新容量
    		else {  // 初始化容量为0，使用默认容量和默认阈值
    			newCap = DEFAULT_INITIAL_CAPACITY;
    			newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    		}
    		if (newThr == 0) { //新阈值为0
    			float ft = (float) newCap * loadFactor;//新容量乘以负载因子获得临时变量ft
    			newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);//新容量小于最大容量并且临时变量ft也小于最大容量，将ft作为新阈值，否则将Integer.MAX_VALUE作为新阈值
    		}
    		threshold = newThr;//新阈值作为阈值
    		@SuppressWarnings({  "rawtypes", "unchecked" })
    		Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];//根据新容量创建新数组
    		table = newTab;//新数组作为HashMap的数组
    		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)
    						((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 { 
    							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;
    	}

可以看到注释就已经很明确的说明了，该方法"初始化或加倍表大小"，代码中table即HashMap中用于存放key的hash值的数组。所以，HashMap是进行2倍扩容，至于为什么是2倍扩容，这就和之前说的HashMap默认值为16一样，都是为了减少Hash的冲突，使数组各项能够比较均匀地分配数据。

再看ArrayList的扩容源码：

/** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. *增加容量，以确保它至少可以容纳由最小容量参数指定的元素数。 * @param minCapacity the desired minimum capacity */
        private void grow(int minCapacity) { 
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);//相当于oldCapacity*1.5
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;//最小容量值作为新容量值
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

ArrayList的注释就和HashMap不一样了，ArrayList说的是“增加容量，以确保它至少可以容纳由最小容量参数指定的元素数”。虽然到这我们还并不能了解扩容的条件，但是我们却可以知道扩容的策略是如何的。

1.  根据`int newCapacity = oldCapacity + (oldCapacity >> 1);`可知，是将原容量的1.5倍作为新容量的值newCapacity
2.  若新分配的容量依然小于minCapacity，则将minCapacity作为新的容量值
3.  若新分配的容量值大于ArrayList的最大容量值MAX\_ARRAY\_SIZE，调用hugeCapacity()方法，该方法源码如下：
    
        private static int hugeCapacity(int minCapacity) { 
            if (minCapacity < 0) // 超过Integer.MAX_VALUE，min会为负数
                throw new OutOfMemoryError();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }
    
    源码中，minCapacity < 0的情况即是minCapacity 超出Integer.MAX\_VALUE的情况，该情况下抛出内存溢出错误；否则会将最大容量设置为为Integer.MAX\_VALUE。
4.  调用Arrays.copyOf()方法对把数组元素进行转移，并将数组大小设置为newCapacity

总结一下这两者的差别：

1.  HashMap普通情况下是以2倍的容量进行扩容的，ArrayList则是以1.5倍进行扩容的；
2.  ArrayList扩容1.5倍后的容量依然小于传入的minCapacity时，将minCapacity作为扩容的容量
3.  HashMap和ArrayList最大可设置的容量值都是Integer.MAX\_VALUE,容量超过时ArrayList会抛出内存溢出错误，HashMap则是判断原阈值是否大于0，阈值大于0则将原阈值作为新容量，否则重新将HashMap的容量和阈值设置为默认值；
4.  HashMap设置阈值为0时，会自动转换为容量与负载因子的乘积（newCap \* loadFactor）；

综上，已经解答了如何扩容的问题，但是ArrayList什么情况下扩容还是个问题；另外，如果将另一个ArrayList的元素存入或者另一个HashMap的元素存入，和单个元素存放有什么不同，这些依然是个问题。

## 3. 存入数据时的区别 ##

接着分析源码，可以看到ArrayList中调用`grow(minCapacity)` 的代码如下

private void ensureExplicitCapacity(int minCapacity) { 
            modCount++;
    
     // 当minCapacity大于当前数组容量长度（elementData.length）时，调用扩容方法grow(minCapacity);
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }

继续

private void ensureCapacityInternal(int minCapacity) { 
        //传入当前HashMap的数组和minCapacity作为参数
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

再向上查看

/** * 添加单个数据元素 */
        public boolean add(E e) { 
            ensureCapacityInternal(size + 1);  // 此处为调用ensureCapacityInternal(int minCapacity)方法，minCapacity为size+1
            elementData[size++] = e;
            return true;
        }
        /** * 将一个集合内的数据元素都添加到ArrayList中 */
        public boolean addAll(Collection<? extends E> c) { 
            Object[] a = c.toArray();
            int numNew = a.length;
            ensureCapacityInternal(size + numNew);  // 此处为调用ensureCapacityInternal(int minCapacity)方法，minCapacity为size+numNew
            System.arraycopy(a, 0, elementData, size, numNew);
            size += numNew;
            return numNew != 0;
        }

可以看到以上两个方法都调用了ensureCapacityInternal，不难理解，由于add()方法每次都只添加一个元素所以minCapacity为size + 1；addAll()方法每次需要添加多个元素，所以minCapacity为size+numNew，而并不是循环调用add()进行添加。此时，也就可以解答一个问题，”ArrayList什么时候进行扩容“，答案就是根据传入的minCapacity的大小判断是否需要扩容，minCapacity小于当前容量则不需要扩容，大于当前容量才会开始扩容，扩容后的容量大于minCapacity则扩容为原来的1.5倍，否则扩容到minCapacity。

举个例子：当当前容量为10并调用add()方法存入1个元素时，容量会扩容到10+10\*0.5=15;

当当前容量为10并调用addAll()方法存入6个元素时，由于10+6是大于15的，所以容量会直接扩容至16。

此时，再对比HashMap的存入数据的源码

/** * 存入一个数据元素 */
    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)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        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;
        //当++size大于threshold时候，进行扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
    	/** * * 将另一个Map中的元素存入 * */
    	final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { 
    		int s = m.size();
    		if (s > 0) { 
    			if (table == null) {  // pre-size
    				float ft = ((float) s / loadFactor) + 1.0F;
    				int t = ((ft < (float) MAXIMUM_CAPACITY) ? (int) ft : MAXIMUM_CAPACITY);
    				if (t > threshold)
    					threshold = tableSizeFor(t);
    			} else if (s > threshold)
    			 //当s大于threshold时候，进行扩容
    				resize();
    			for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { 
    				K key = e.getKey();
    				V value = e.getValue();
    				putVal(hash(key), key, value, false, evict);
    			}
    		}
    	}

可以看到调用putVal()方法存入一个数据元素时，`if (++size > threshold) resize();` ，存入多个数据元素时候，`if (s > threshold) resize();`

这里可以看到和ArrayList一样，存放单个数据元素和多个数据元素时，扩容的判断都不是一个个添加的，但具体实现上又是完全不同的：

1.  **HashMap是与阈值对比，而非ArrayList的与当前数组容量进行对比**
2.  **HashMap存入单个数据元素时，将当前已存数据量 size 与阈值 TREEIFY\_THRESHOLD 进行对比，存入多个数据元素时并没有像ArrayList一样使用（size+存入的map的size）与阈值进行对比，而是直接将存入的map的size只 s 与阈值进行对比**
3.  **HashMap存入多个是调用了putVal()方法，而ArrayList并不是**

从以上这些可以看到，HashMap和ArrayList虽然都是一个会自动扩容的结构，但无论从设计思想和具体代码实现上都有着不小的差别，对两者进行对比可以比较清晰的看到两者的差异，从而更方便地进行区别记忆。

另外需要注意的一点是，HashMap中是链表转换为红黑树的标准是链表中的元素个数为8，红黑树退化为链表标准则为元素个数为6，并不不一致！

## 4. 重点汇总 ##

包括以下几点：

1.  默认容量大小，ArrayList是10，HashMap是16
2.  进行扩容时，ArrayList是和当前容量进行对比，HashMap是和当前容量\*负载因子（默认为0.75）得到的阈值进行对比
3.  进行扩容时，ArrayList扩容到原来的1.5倍，HashMap扩容到原来的2倍
4.  进行扩容时，扩容的数值大于最大容量时候，判断是否大于Integer.MAX\_VALUE，ArrayList大于的话直接抛出内存溢出错误；HashMap判断原阈值是否大于Integer.MAX\_VALUE，原阈值不大于则将新容量设置为原阈值，新阈值设置为新容量的0.75；原阈值大于则将HashMap新容量和新阈值重新设置为默认值。

[https_www.iteye.com_topic_539465]: https://www.iteye.com/topic/539465