2-JDK源码对你最有触动的是哪一段#集合

约定不等于承诺〃 2022-09-11 06:17 95阅读 0赞

**目录**

集合

可变长度数组是如何实现

ArrayList 的 新增元素的 2 个方法

Arrays中的二分查找方法

容器代码中的溢出

集合的fail-fast的机制。

--------------------

## ![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Cm5b2m_size_20_color_FFFFFF_t_70_g_se_x_16][] ##

## 集合 ##

### 可变长度数组是如何实现 ###

数组在初始化阶段就已经限定了其长度，在对数组的元素操作是不能越界处理的。JDK为我们提供的集合处理工具类，很多都是可变长度的。这点在java学习初期没有正视，就忽视了其可变长度数组是如何实现的。

关于可变长度数组的实现，我是从常用的ArrayList.add(E e)去一探究竟的。

/**
         * Appends the specified element to the end of this list.
         *
         * @param e element to be appended to this list
         * @return <tt>true</tt> (as specified by {@link Collection#add})
         */
        public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
    
    
        /**
         * The array buffer into which the elements of the ArrayList are stored.
         * The capacity of the ArrayList is the length of this array buffer. Any
         * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
         * will be expanded to DEFAULT_CAPACITY when the first element is added.
         */
        transient Object[] elementData; // non-private to simplify nested class access

ArrayList 的其实操作的自身元素 Object\[\] elementData，所有的数据都是存储在elementData内。**实现可变数组也是围绕elementData所指向的数组，而展开的。**

ArrayList 初始化后elementData指向的是一个全局空对象 当执行add方法时候，会预判增加一位的长度后是否比elementData现在指向的数组长度长，如果上述判断成立，那么这时候就要执行数组扩展的机制。

扩展首先是预判数组在现有长度上扩展1.5倍长，如果扩展后长度超过MAX\_ARRAY\_SIZE （ Integer.MAX\_VALUE - 8）那么就只能给数组扩展到Integer.MAX\_VALUE的长度，换而言之，数组不能是无限增长的最长也就Integer.MAX\_VALUE的长度

确定好数组要增长的长度后，调用系统的原生方法 System.arraycopy来拷贝elementData指向的旧数组到新的数组。当拷贝完毕后elementData指向新的数组，完成空间的扩展

以上执行完毕后，只需把当前数组最后一位的下一位指向要添加的元素即可。 观后以上代码，不由得感觉，数组一旦执行扩长操作，无疑是个比较的大系统开销，频繁的触发扩长操作无疑给系统带来性能上的损耗。

所以，对可变长数组的使用还是要有所节制。即在使用可变数组前预判该数组在该case下最大能有多长，不要不初始长度就使用，尤其该数组将来装的元素非常多时，一定要初始化一个比较合适的长度，尽量不给数组频繁触发扩长为佳。当然也不要一下定义的过长，以够用为原则。如果能用addall方法最好。

### ArrayList 的 新增元素的 2 个方法 ###

public boolean add(E e) {
      //确保数组大小足够，不够需要扩容
      ensureCapacityInternal(size + 1);  // Increments modCount!!
      //直接赋值，线程不安全的
      elementData[size++] = e;
      return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
      //如果是空数组，就从最小容量和默认容量10之间取最大值
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
      }
      //确保容积足够
      ensureExplicitCapacity(minCapacity);
    }
    private void ensureExplicitCapacity(int minCapacity) {
      //记录数组被修改
      modCount++;
      // 如果我们希望的最小容量大于目前数组的长度，那么就扩容
      if (minCapacity - elementData.length > 0)
        grow(minCapacity);
    }
    //老的数组大小2倍，最后把现有数据拷贝到新的数组里面去
    private void grow(int minCapacity) {
      // overflow-conscious code
      int oldCapacity = elementData.length;
      // oldCapacity >> 1 是把 oldCapacity / 2 的意思
      int newCapacity = oldCapacity + (oldCapacity >> 1);
    
      // 如果扩容后的值 < 我们的期望值，扩容后的值就等于我们的期望值
      if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    
      // 如果扩容后的值 > jvm 所能分配的数组的最大值，那么就取 Integer 的最大值
      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);
    }
    
    //根据数组下标去删除
    public E remove(int index) {
      rangeCheck(index);
    
      modCount++;
      E oldValue = elementData(index);
    
      int numMoved = size - index - 1;
      if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
      elementData[--size] = null; // clear to let GC do its work
    
      return oldValue;
    }

其实首先自己会说 ArrayList 的 新增元素的 2 个方法：*public boolean* add(E e) 和 *public void* add(*int* index, E element) ，为什么说是这两个方法呢，

> 1.  是因为首先根据这两个方法验证了 《Java 开发手册》里说的，初始化 ArrayList 的时候一定要先指定容量大小，
> 2.  指定容量大小带来的好处是什么？

首先在这两个方法里，都会先确认数组大小，如果没有设置数组大小，就会默认为 10，如果数组大小容量不够，就会扩容原数组大小的 1.5 倍，这里其实就会好奇，为啥是 1.5 倍，在网上查阅资料说的是：因为1.5 可以充分利用移位操作，减少浮点数或者运算时间和运算次数。看到这个一点就是，移位操作是不是做性能优化的一个极致优化点？这里向下深一点的看就会发现，如果容量大小不够，就会频繁扩容扩容，然后频繁将数组复制到新分配的内存地址，影响效率，这里验证了如果初始化 ArrayList 的时候指定大小的好处。

同时发现扩容的一个点：在扩容的时候，有数组大小溢出意识，扩容后数组的大小不能小于0，不能大于Integer 的最大值

添加元素任意位置 add 方法，和添加元素的 add 方法相比，有一个不同点就在于：

> 1.  前者添加指定位置进去，后面的所有元素都需要重新排列
> 2.  后者方法，是直接添加到末尾，排除掉扩容的问题，是不会有元素进行重新排列的
> 3.  这里就会意识到和 LinkedList（链表） 进行比较添加元素任意位置 add 方法，如果当我们的 ArrayList 的大小初始化足够大的时候，ArrayList 的 add 任何方法的花费时间都优于 LinkedList

### Arrays中的二分查找方法 ###

(以double为例)

// Like public version, but without range checks.
        private static int binarySearch0(double[] a, int fromIndex, int toIndex,
                                         double key) {
            int low = fromIndex;
            int high = toIndex - 1;
    
            while (low <= high) {
                int mid = (low + high) >>> 1;
                double midVal = a[mid];
    
                if (midVal < key)
                    low = mid + 1;  // Neither val is NaN, thisVal is smaller
                else if (midVal > key)
                    high = mid - 1; // Neither val is NaN, thisVal is larger
                else {
                    long midBits = Double.doubleToLongBits(midVal);
                    long keyBits = Double.doubleToLongBits(key);
                    if (midBits == keyBits)     // Values are equal
                        return mid;             // Key found
                    else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
                        low = mid + 1;
                    else                        // (0.0, -0.0) or (NaN, !NaN)
                        high = mid - 1;
                }
            }
            return -(low + 1);  // key not found.
        }
    }

// 片段2 Double类中的代码

public static long doubleToLongBits(double value) {
            long result = doubleToRawLongBits(value);
            // Check for NaN based on values of bit fields, maximum
            // exponent and nonzero significand.
            if ( ((result & DoubleConsts.EXP_BIT_MASK) ==
                  DoubleConsts.EXP_BIT_MASK) &&
                 (result & DoubleConsts.SIGNIF_BIT_MASK) != 0L)
                result = 0x7ff8000000000000L;
            return result;
        }

**\#原因\#**

1.  面试中基本上都绕不开二分查找，有时候会到网上找一些例子，其实JDK中的例子非常标准和规范。
2.  对于中间值的选取，采用了无符号位操作，int mid = (low + high) >>> 1; 常规的写法 (low + high) / 2会存在运算溢出的可能。low + (high - low) / 2 运算不够高效。 而JDK的写法可以完美解决。
3.  上述代码中选取的是double的比较，由于浮点数的精度问题，对于double的比较，也是我们经常遇到的问题 对于片段2中的代码注释中，详细解释了IEEE 754 floating-point双精度浮点数的存储格式。 Bit 63(符号位): represents the sign of the floating-point number Bits 62-52(指数位): represent the exponent. Bits 51-0(有效数字位): represent the significand (sometimes called the mantissa) of the floating-point number

**\#感触\#**

1.  掌握必要的计算机知识对看懂源码非常重要
2.  当遇到一些问题的时候，可以尝试看一下JDK的实现思路

### 容器代码中的溢出 ###

JDK 中对我触动最大的地方是一些常见**容器代码中的溢出意识**。ArrayList，Vector，HashTable，AbstrctStringBuilder 等类中都有这样的考虑，下面用 ArrayList 做例子。

ArrayList 主要依赖 newCapacity() 和 hugeCapacity() 等方法做扩容，扩容时，JDK 对于新的容量进行了严格的控制：

*  对于下界，JDK 中多次判断 minCapacity < 0，防止返回负数容量
 *  对于上界，根据容量需求，JDK 依次将其限制为：
    
     *  扩容 1.5 倍后的 newCapacity
     *  MAX\_ARRAY\_SIZE 常量（值为 Integer.MAX\_VALUE - 8）
     *  Integer.MAX\_VALUE 最终拦在 Integer.MAX\_VALUE 的范围之内，防止超出 Integer 表示的范围。

从中感受到 JDK 对于边界条件和特殊情况的周密处理，值得学习。

附之前阅读源码时做的注释：

private int newCapacity(int minCapacity) {
        // 以下的代码是有溢出意识的
        // oldCapacity为旧容量 newCapacity为新容量
        int oldCapacity = elementData.length;
        // 运用位运算，实现扩容50%（右移1位即除以2）
        // JDK6 之前取 ceil，之后的版本取 floor
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 检查扩容50%后容量是否足够，如果不够，进行如下判断
        if (newCapacity - minCapacity <= 0) {
            // 第一种特殊情况：使用无参构造方法带来的容量更新（更新为10）
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            // 第二种特殊情况：溢出
            if (minCapacity < 0)
                throw new OutOfMemoryError();
            // 否则是真的容量还不够，直接返回所需的最小容量
            return minCapacity;
        }
        // 如果扩容50%后容量newCapacity够了，还需要进行如下判断
        // 对理想的newCapacity与MAX_ARRAY_SIZE进行比较
        // 如果newCapacity在MAX_ARRAY_SIZE的承受范围之内，则直接返回
        // 否则调用hugeCapacity方法申请大容量，以minCapacity为参数
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }
    
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        // 如果minCapacity不在MAX_ARRAY_SIZE的承受范围之内，则以Integer.MAX_VALUE为容量
        // 否则以MAX_ARRAY_SIZE为容量
        return (minCapacity > MAX_ARRAY_SIZE)
            ? Integer.MAX_VALUE
            : MAX_ARRAY_SIZE;
    }

### 集合的fail-fast的机制。 ###

记得刚入行的时候，对集合操作经常碰到ConcurrentModificationException。后来看了list源码，才知道通过**维护一个modCount去避免并发修改的操作**。

这种fail-fast思路很适合日常开发，尽可能保证失败/不满足的时候 尽早停止系统资源的开销。也可以提高代码的可读性，健壮性

比如

> 1.客户端发了一个业务无效的请求，服务端可以通过校验手段让请求失败，而不是让请求继续往业务层走，造成一些必要的服务开销 2.方法编写时，尽量让无效/错误的场景放前面，如空值判断，权限校验等。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA55Cm5b2m_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/5f8f90d173d448fd84311fdb94fe5ffe.png