为什么 Joshua Bloch 在 Effective Java 中使用 2*size + 1 来调整堆栈大小？

Question

这是我正在谈论的代码：

public class Stack {
  private Object[] elements;
  private int size = 0;
  private static final int DEFAULT_INITIAL_CAPACITY = 16;
  public Stack() {
    elements = new Object[DEFAULT_INITIAL_CAPACITY];
  }
  public void push(Object e) {
    ensureCapacity();
    elements[size++] = e;
  }
  public Object pop() {
    if (size == 0)
      throw new EmptyStackException();
    return elements[--size];
  }
  /**
   * Ensure space for at least one more element, roughly
   * doubling the capacity each time the array needs to grow.
   */
  private void ensureCapacity() {
    if (elements.length == size)
      elements = Arrays.copyOf(elements, 2 * size + 1);
  }
}

为什么不简单地将最后一行保留为elements = Arrays.copyOf(elements, 2 * size);？

它可能有效的唯一情况是 Stack 的初始大小为 0。但在这种情况下，它是一个常量 - DEFAULT_INITIAL_CAPACITY（非零值）。并且没有其他重载构造函数可以从用户那里获取这个值（或默认为 0）

Answer 1

我将其解释为对假设的未来错误的安心防御。确实，正如所写的那样，此类的数组容量不会为 0，因此添加 1 并不是绝对必要的，但是一旦添加更多功能，该假设可能会悄悄地失败。

可能的附加功能的示例包括 from java.util.ArrayList，它具有trimToSize()可以将容量设置为 0的方法，允许从（可能为空）集合初始化数据的构造函数，以及允许将容量显式设置为 0 的构造函数。还可以想象一个特性，当这个类被清空时，它会自动减少分配的容量。或者也许有人会编辑DEFAULT_INITIAL_CAPACITY常量。现在想象一下，容量改变的方法被一整屏的 javadoc 注释分隔开，并拆分到子类中。很容易忘记您应该防止容量变为 0。

如果ensureCapacity()取决于大小为非零，则在重新编写类时必须始终牢记该假设。添加+1是一种低成本的改变，可以消除这种担忧。这也是处理边缘情况的简单算术方法的一个例子。