为什么Joshua Bloch在《Effective Java》中将栈的大小调整使用2*size + 1?

huangapple go评论73阅读模式
英文:

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

问题

这是我正在谈论的代码部分:

/**
 * 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);

唯一可能有效的情况是如果堆栈的初始大小为0。但在这种情况下,它是一个常数 - DEFAULT_INITIAL_CAPACITY(非零值)。而且没有其他重载的构造函数可以从用户那里获取这个值(或者将其默认为0)。

英文:

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)

答案1

得分: 13

我将其解释为对假设性未来错误的一种安心防御。的确,按照目前的编写方式,这个类不会有一个容量为0的数组,因此增加1并不是绝对必要的,但是一旦添加了更多功能,这种假设可能会悄然失败。

可能的附加功能示例包括来自java.util.ArrayList的功能,它有一个trimToSize()方法,可以将容量设置为0,还有一个允许从(可能为空的)集合初始化数据的构造函数,以及一个允许显式将容量设置为0的构造函数。您还可以想象一种在清空时自动减少该类分配的容量的功能。或者,有人可能会编辑DEFAULT_INITIAL_CAPACITY常量。现在想象一下,改变容量的方法被分隔成满屏的javadoc注释,并且分布在子类之间。很容易忘记您应该防止容量变为0。

如果ensureCapacity()依赖于大小非零,那么在重新设计类时您必须始终记住这一假设。添加+1是一种低成本的更改,可以消除这种担忧。这也是一种处理边缘情况的简单算术方法的示例。

英文:

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.

答案2

得分: 1

这对我来说似乎比@Boann使用的所有措辞更明显,尽管他/她在他/她的回答中确实有更简单的答案。答案很简单,作者希望支持从大小为零的数组开始...设置DEFAULT_INITIAL_CAPACITY = 0。如果没有+1,这将导致代码崩溃。除非初始时数组的大小为零,否则elements数组的大小永远不可能为零,而这就是添加+1的唯一原因。

根据目前的代码编写,没有必要添加+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.

huangapple
  • 本文由 发表于 2020年10月17日 02:17:24
  • 转载请务必保留本文链接:https://go.coder-hub.com/64394410.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定