数组、越界及遍历

数组越界检查

在 C 语言里遇到数组访问越界时，虽然编译可能会有警告，但代码是能成功运行的：

1
2
3

int arr[3];
arr[2] = 1;
printf("%d", arr[3]);

因为一个数组在计算机内表现为一段内存地址，当我们尝试越界访问数组时，实际上是在尝试越过那一段内存地址去访问别的内存地址上的数据——倘若我们尝试访问的地址是合法的，且又没做任何控制，那么自然也能访问到数据。

而在 Java 中类似逻辑的代码虽然能正常编译，但当 Java 虚拟机执行 class 文件时却会抛错 ArrayIndexOutOfBoundsException：

1
2
3

int[] arr = new int[4];
System.out.println(arr[5]);
System.out.println(arr[-1]);

很容易想到是不是 JVM 层面做了什么控制——确实如此，比方说 hotspot 虚拟机里相关的控制实现如下：

jdk8/jdk8/hotspot: 87ee5ee27509 src/share/vm/interpreter/bytecodeInterpreter.cpp

// hotspot\src\share\vm\interpreter\bytecodeInterpreter.cpp
#define ARRAY_INTRO(arrayOff)                                                  \
      arrayOop arrObj = (arrayOop)STACK_OBJECT(arrayOff);                      \
      jint     index  = STACK_INT(arrayOff + 1);                               \
      char message[jintAsStringSize];                                          \
      CHECK_NULL(arrObj);                                                      \
      if ((uint32_t)index >= (uint32_t)arrObj->length()) {                     \
          sprintf(message, "%d", index);                                       \
          VM_JAVA_ERROR(vmSymbols::java_lang_ArrayIndexOutOfBoundsException(), \
                        message);                                              \
      }

hotspot 将会判断访问数组的索引是否超过了数组的长度限制，若是，则抛出数组访问越界异常。

注意索引被转换成了 uint32_t 类型（无符号类型），因此当索引为负数时会被转换为相应的无符号类型数。Java 中数组的大小和 int 的取值范围有关，int 占 32 byte 大小，取值范围是 -2147483648 至 2147483647，因此负数的取值范围为 -2147483648 至 -1，相应的补码（用补码表示负数）的取值范围是 2147483648 至 4294967295。

显然为负数的索引在这会被判断超过限制从而抛出异常。

但比如说在遍历一个大号数组的场景下：

int[] arr = new int[999999];
for (int i = 0; i < arr.length; i++) {
  System.out.println(arr[i]);
}

既然数组的访问索引 i 的取值显然不会越界，那其实没必要每次访问数组的值时都进行一次越界检查——实际上 JVM 判断出这种情况后会进行「数组边界检查消除」的优化来减少性能浪费。

JDK 层面的越界检查

Java 是在 JVM 层面对数组是否越界进行判断的，而对于集合对象来说，则在 JDK 层面进行越界检查。比方说 LinkedList 的 get() 中的越界检查实现：

public E get(int index) {
  checkElementIndex(index);
  return node(index).item;
}

private void checkElementIndex(int index) {
  if (!isElementIndex(index))
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isElementIndex(int index) {
  return index >= 0 && index < size;
}

遍历数组

就简来说，Java 中有三种 for 循环用于遍历集合对象。（下面的 two 和 three 一般统称为 foreach 或增强 for 循环，我做下区分方便讨论。）

// one 经典 for
for(int i = 0; i < arr.size; i++)
  System.out.println(arr.get(i))
// two 增强 for
for(T a : arr)
  System.out.println(a)
// three foreach
arr.forEach(System.out::println);

比方说 Iterable.java 提供的 foreach() 的实现简单好懂，其实是在 JDK 层面利用 Lambda 表达式做参数，封装了增强 for：

// java/lang/Iterable.java
default void forEach(Consumer<? super T> action) {
    Objects.requireNonNull(action);
    for (T t : this) {
        action.accept(t);
    }
}

增强 for 仍然是个语法糖，遍历集合时底层使用 Iterator，遍历数组时底层用的普通 for：

// 集合
default void forEach (Consumer<? super T> var1) {
    Objects.requireNonNull(var1);
    Iterator var2 = this. iterator():
    while(var2.hasNext()){
        Object var3 = var2.next;
        var1.accept(var3);
    }
}

// 数组
String[] str = new String[]{"a", "b"};
String[] var2 = str;
int var3 = str.length;

for(int var4 = 0; var4 < var3; ++var4) {
  String s = var2[var4];
  System.out.println(s);
}

fail-fast

fail-fast 顾名思义，快速失败——让它崩溃！发现问题，马上让它暴露出来。

比如下面就是一个 fail-fast 的例子：

void do(String name){
  if(null == name) throw new Exception();
  //……s
}

而 Java 集合中 fail-fast 体现为：当遍历集合对象时，若集合对象同时被进行了「结构性更改」的操作，则会抛出 ConcurrentModificationException 异常。

啥是结构性更改呢？

ListIterator (Java Platform SE 7 )
Structural modifications are those that change the size of the list, or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results.

我觉得后面这段有点暧昧「或者以其它方式扰乱数组，以至于正在进行的迭代可能会产生错误的结果」，什么其它方式？以及，什么错误的结果？

我理解结构性更改的方式有两种：

集合对象中元素数目的变动（如 add()、remove()、addAll()、clear()……）
集合对象内部结构的更改
- 这个要具体到集合对象的实现，比如 HashMap 的 rehash()、ArrayList 的 replaceAll()。
- 比方说 HashMap 的 set() 就不算结构性更改，为啥 ArrayList 的 replaceAll() 就算结构性更改？

至于错误的结果，按我的理解：

比如对于 HashMap 来说，倘若遍历的途中进行了 rehash() 操作，显然遍历的结果会出问题。
比如对于 List 来说，倘若遍历的途中添加或删除了一些元素，会导致「也许部分添加的元素被遍历出来了而部分元素未能遍历」等数据不一致的情况。

Java 实现 fail-fast 的方式很清晰——集合对象内提供了一个 modCount 元素保存对象进行结构性更改的次数。这样在遍历之前，会取一个 modCount 的快照作为期望值 expectedModCount，每次访问时会判断这个期望值与当前的 modCount 是否一致。倘若不一致，这说明遍历期间有人捣蛋，则抛出ConcurrentModificationException 异常。

比方说 ArrayList.java 的 foreach() 实现：

public void forEach(Consumer<? super E> action) {
  Objects.requireNonNull(action);
  final int expectedModCount = modCount;
  final Object[] es = elementData;
  final int size = this.size;
  for (int i = 0; modCount == expectedModCount && i < size; i++)
    action.accept(elementAt(es, i));
  if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
}

不要在 foreach 循环里进行元素的 add/remove 操作

见 Alibaba Java Coding Guidelines

这里的 foreach 循环如果指前文提到的第三种遍历集合对象的元素，那就简单了。比方说上面 ArrayList.java 的 foreach() 实现，很明显会抛出 ConcurrentModificationException 异常——「为什么不要？」因为会抛异常嘛。

但倘若指前文提到的第二种遍历方式，即增强型 for 循环——则没这么显然了。因为增强型 for 循环实际上是 Iterator 的封装，因此需要到 Iterator 的实现里去看看会发生什么事。

举个例子：

// one
ArrayList<String> arrayList = new ArrayList();
    arrayList.add("one");
    arrayList.add("two");
    for(String s : arrayList){
      if("one".equals(s)){
        System.out.println(arrayList.remove(s));
      }
    }
// two
ArrayList<String> arrayList = new ArrayList();
    arrayList.add("one");
    arrayList.add("two");
    for(String s : arrayList){
      if("two".equals(s)){
        System.out.println(arrayList.remove(s));
      }
    }
// three
ArrayList var1 = new ArrayList();
    var1.add("one");
    var1.add("two");
    Iterator var2 = var1.iterator();

    while(var2.hasNext()) {
      String var3 = (String)var2.next(); // next() 会检查集合对象是否进行结构性更改
      if ("one".equals(var3)) {
        System.out.println(var1.remove(var3));// remove() 会记录为一次结构性更改
      }
    }
// Iterator 实现
public boolean hasNext() {
  return cursor != size;
}

public E next() {
  checkForComodification();
  int i = cursor;
  if (i >= size)
    throw new NoSuchElementException();
  Object[] elementData = ArrayList.this.elementData;
  if (i >= elementData.length)
    throw new ConcurrentModificationException();
  cursor = i + 1;
  return (E) elementData[lastRet = i];
}

对比反编译后的 three 及其实现来看例子 one 和 two 的执行情况：

例子 one 能正常执行：对例子 one 来说，第一次遍历便进行 remove()，此时游标 cursor 为 1，size 为 1，因此尝试第二次遍历时因为 hasNext() 为 false，跳出遍历。
而例子 two 会抛异常：对于例子 two 来说，第二次遍历进行 remove()，此时游标 cursor 为 2，size 为 1，因此尝试第二次遍历时因为 hasNext() 为 true，尝试进行第三次遍历，此时进入 next() 方法便抛出 ConcurrentModificationException 异常。

看样子仍然很危险呐——因此还是不要在 foreach 循环里进行元素的 add/remove 操作吧。