vlambda博客
学习文章列表

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

目录

  • 两者相似的地方

  • 两者的差别


    • 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;
  • 1

  • 2

  • 3

  • 4

可以看到,两者从代码风格上就有一定差异,HashMap没有使用访问修饰符,ArrayList使用了,很明显是两个不同风格的开发人员进行的开发。至于HashMap为什么使用16,建议看这篇文章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;
  • 1

  • 2

  • 3

  • 4

在ArrayList中:

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

  • 2

可以看到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;
}
  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10

  • 11

  • 12

  • 13

  • 14

  • 15

  • 16

  • 17

  • 18

  • 19

  • 20

  • 21

  • 22

  • 23

  • 24

  • 25

  • 26

  • 27

  • 28

  • 29

  • 30

  • 31

  • 32

  • 33

  • 34

  • 35

  • 36

  • 37

  • 38

  • 39

  • 40

  • 41

  • 42

  • 43

  • 44

  • 45

  • 46

  • 47

  • 48

  • 49

  • 50

  • 51

  • 52

  • 53

  • 54

  • 55

  • 56

  • 57

  • 58

  • 59

  • 60

  • 61

  • 62

  • 63

  • 64

  • 65

  • 66

  • 67

  • 68

  • 69

  • 70

  • 71

  • 72

  • 73

  • 74

  • 75

  • 76

可以看到注释就已经很明确的说明了,该方法"初始化或加倍表大小",代码中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);
}
  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10

  • 11

  • 12

  • 13

  • 14

  • 15

  • 16

  • 17

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。

    • 1

    • 2

    • 3

    • 4

    • 5

    • 6

    • 7

  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);
}
  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

继续

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

  • 2

  • 3

  • 4

再向上查看

    /**
* 添加单个数据元素
*/

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;
}
  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10

  • 11

  • 12

  • 13

  • 14

  • 15

  • 16

  • 17

  • 18

  • 19

可以看到以上两个方法都调用了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);
}
}
}
  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10

  • 11

  • 12

  • 13

  • 14

  • 15

  • 16

  • 17

  • 18

  • 19

  • 20

  • 21

  • 22

  • 23

  • 24

  • 25

  • 26

  • 27

  • 28

  • 29

  • 30

  • 31

  • 32

  • 33

  • 34

  • 35

  • 36

  • 37

  • 38

  • 39

  • 40

  • 41

  • 42

  • 43

  • 44

  • 45

  • 46

  • 47

  • 48

  • 49

  • 50

  • 51

  • 52

  • 53

  • 54

  • 55

  • 56

  • 57

  • 58

  • 59

  • 60

  • 61

  • 62

  • 63

  • 64

  • 65

  • 66

  • 67

  • 68

  • 69

可以看到调用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新容量和新阈值重新设置为默认值。