1. ArrayList的扩容机制

• ArrayList的默认初始化容量是10，底层是使用一个Objcet[]来存放元素，向ArrayList添加元素的时候，先让Size（集合所包含元素个数）+1，如果Size+1大于底层Object[]的长度的话就触发扩容（扩容使得新数组容量是旧数组容量的1.5倍，如果新容量大于Integer.MAX_VALUE-8，就让新容量指向 Integer.MAX_VALUE），最后调用 Arrays.copyOf(elementData, newCapacity)在旧数组的基础上复制出一个以新容量为长度的新数组作为ArrayList的底层数组。

    //默认初始化容量
    private static final int DEFAULT_CAPACITY = 10;

   //添加元素有可能会触发扩容，效率较低
    public boolean add(E e) {
        //进行写操作之前让Size+1再检查底层数组容量是否可用,同时modCount++
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;//检查通过后，再添加元素到数组
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    } 

    private static int calculateCapacity(Object[] elementData, int minCapacity)     {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//该集合被修改得次数加1
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);//如果给定得容量大于底层数组的容量，就进行扩容
    }
    //扩容方法
    private void grow(int minCapacity) {
        // overflow-conscious code
        //先拿旧数组容量
        int oldCapacity = elementData.length;
        //在旧容量的基础上扩容百分之50，得到新容量
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            //计算出来的新容量如果小于给定容量就让新容量指向给定容量
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            //如果新容量大于Integer.MAX_VALUE-8，就让新容量指向 Integer.MAX_VALUE
            newCapacity = hugeCapacity(minCapacity); 
        elementData = Arrays.copyOf(elementData, newCapacity);
      }
    
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

2. 为什么HashMap的加载因子是0.75？

• 加载因子的作用在于判断map是否需要扩容，而扩容是一个比较耗时的操作。

  • 如果加载因子过小，比如 loadFactor=0.5f，初始容量=16的情况下，那么元素超过16*0.5=8个就会扩容到32，假设添加第9个元素成功，那么就会有23个数组位置空闲，空间利用率大概为9/23=39%，因此频繁的扩容不仅耗时而且浪费空间。
  • 如果加载因子过大，比如loadFactor=1.0f，初始容量=16的情况下，那么元素超过16个才会触发扩容，虽然空间利用率大，但是桶中元素的冲突肯定会变多，元素越来越多之后会影响到map的查询时间效率。
  • 总结：loadFactor=0.75f 是空间和时间成本的一种折中（1+0.5）/ 2 = 0.75

• HashMap相关源码分析