集合
可变长度数组是如何实现
数组在初始化阶段就已经限定了其长度，在对数组的元素操作是不能越界处理的。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) ，为什么说是这两个方法呢，
是因为首先根据这两个方法验证了 《Java 开发手册》里说的，初始化 ArrayList 的时候一定要先指定容量大小，
指定容量大小带来的好处是什么？
首先在这两个方法里，都会先确认数组大小，如果没有设置数组大小，就会默认为 10，如果数组大小容量不够，就会扩容原数组大小的 1.5 倍，这里其实就会好奇，为啥是 1.5 倍，在网上查阅资料说的是：因为 1.5 可以充分利用移位操作，减少浮点数或者运算时间和运算次数。看到这个一点就是，移位操作是不是做性能优化的一个极致优化点？这里向下深一点的看就会发现，如果容量大小不够，就会频繁扩容扩容，然后频繁将数组复制到新分配的内存地址，影响效率，这里验证了如果初始化 ArrayList 的时候指定大小的好处。
同时发现扩容的一个点：在扩容的时候，有数组大小溢出意识，扩容后数组的大小不能小于 0，不能大于 Integer 的最大值
添加元素任意位置 add 方法，和添加元素的 add 方法相比，有一个不同点就在于：
前者添加指定位置进去，后面的所有元素都需要重新排列
后者方法，是直接添加到末尾，排除掉扩容的问题，是不会有元素进行重新排列的
这里就会意识到和 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; }
复制代码
#原因 #
面试中基本上都绕不开二分查找，有时候会到网上找一些例子，其实 JDK 中的例子非常标准和规范。
对于中间值的选取，采用了无符号位操作，int mid = (low + high) >>> 1; 常规的写法 (low + high) / 2 会存在运算溢出的可能。low + (high - low) / 2 运算不够高效。 而 JDK 的写法可以完美解决。
上述代码中选取的是 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
#感触 #
掌握必要的计算机知识对看懂源码非常重要
当遇到一些问题的时候，可以尝试看一下 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.方法编写时，尽量让无效/错误的场景放前面，如空值判断，权限校验等。
评论