数组、越界及遍历

🏷 学习折腾 自己浅见

数组越界检查

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

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

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

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

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

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

// 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 层面进行越界检查。比方说 LinkedListget() 中的越界检查实现:

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.javaforeach() 实现:

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 操作

这里的 foreach 循环如果指前文提到的第三种遍历集合对象的元素,那就简单了。比方说上面 ArrayList.javaforeach() 实现,很明显会抛出 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 操作吧。

相关文章

评论区加载中……