Why did Joshua Bloch use 2*size + 1 for resizing the stack in Effective Java?

Question

This is the code I am talking about:

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);
  }
}

Why not simply keep the last line as elements = Arrays.copyOf(elements, 2 * size);?

The only case where it might have been valid would be if the initial size of Stack was 0. But in this case it is a constant - DEFAULT_INITIAL_CAPACITY (a non zero value). And there is no other overloaded constructor which could take this value from user (or default it to 0)

Answer 1

It seems a bit more obvious to me than all the wording @Boann uses, although the he/she does have the simpler answer inside his/her answer. The answer is simply that the author wants to support starting the array at a size of zero...of setting DEFAULT_INITIAL_CAPACITY = 0. This will cause the code to crash without the +1. There's no other way that the size of the elements array can ever be zero except if it starts out that way, and that's the only reason for the +1.

As the code is written, there's no reason for the +1.

Answer 2

I interpret it as peace-of-mind defense against a hypothetical future bug. It's true that as written, this class won't have an array capacity of 0, so adding 1 is not strictly necessary, but that assumption could quietly fail once more features are added.

Examples of possible additional features include those from java.util.ArrayList, which has a trimToSize() method that can set the capacity to 0, and a constructor which allows initializing the data from a (possibly empty) collection, and a constructor that allows explicitly setting the capacity to 0. You can also imagine a feature that reduces this class's allocated capacity automatically when it is emptied. Or maybe someone will edit the DEFAULT_INITIAL_CAPACITY constant. Now imagine that capacity-changing methods become separated by screenfuls of javadoc comments, and split across subclasses. It's easy to forget you were supposed to prevent the capacity becoming 0.

If ensureCapacity() depends on the size being non-zero, you always have to keep that assumption in mind while you rework the class. Adding +1 is a low-cost change that removes that worry. It's also an example of a simple arithmetic way of dealing with an edge case.