Java StringBuilder(StringBuffer)的sunsureCapacity():为什么它加倍并增加2?

2022-09-01 17:49:47

我已经搜索了一下,但我找不到为什么StringBuilder的方法不会通过加倍但同时添加两个来延长旧容量。ensureCapacity()

因此,当默认容量 16 已满时,除非整个字符串长度不超过 34,否则下一个加长值将为 34。为什么不应该是32岁?

我最好的猜测是考虑一个空字符,“\u0000”,但我不确定。谁能告诉我为什么?


答案 1

我相信这与一种简单(尽管有些愚蠢)的方法有关,以确保非常小的字符串的角落情况。

例如,如果我有字符串

""

而且我只加倍它,我将没有足够的大小来存储其中的任何其他内容。如果我将其加倍并添加少量恒定数量的空间,我可以确保我的新值大于我的旧值。

那么为什么要把它加两个呢?可能是一个很小的性能改进。通过添加两个字符而不是 1 个字符,我可以避免小型扩展的中间扩展(下面详述的 0 到 10 个字符)

"" => expand => "1" => expand => "123" expand => "1234567" expand => "123456789012345"

这是 4 扩展相比

"" => expand => "12" => expand => "123456" => expand => "123456789012"

这是3个扩展。这也适用于一个字符字符串(扩展到10个字符)

"1" => expand => "1234" => expand => "1234567890"

而 1 个字符扩展例程看起来像

"1" => expand => "123" => expand => "1234567" => expand => "123456789012345"

最后,添加 2 的增量倾向于在大约 50% 的时间内对齐单词,而添加 1 或 3 的增量会在大约 25% 的时间内这样做。虽然这似乎没什么大不了的,但有些架构无法容纳不对齐的读取,除非昂贵的中断调用来重写CPU中的读取,从而导致各种性能问题。


答案 2

我认为原因是结合

  • 有些古老;-)启发式策略如何扩展容量,特别是对于短缓冲区,

  • 在最早的java API文档中记录此策略,

  • Sun/Oracle非常小心地坚持曾经记录的行为。

StringBuilder与其前身StringBuffer共享此方法,StringBuffer读取(可能从最早的开始,至少在j2sdk1.4_02中,碰巧仍然存在于我机器上的某个存档文件夹中):

/**
 * Ensures that the capacity of the buffer is at least equal to the
 * specified minimum.
 * If the current capacity of this string buffer is less than the 
 * argument, then a new internal buffer is allocated with greater 
 * capacity. The new capacity is the larger of: 
 * <ul>
 * <li>The <code>minimumCapacity</code> argument. 
 * <li>Twice the old capacity, plus <code>2</code>. 
 * </ul>
 * If the <code>minimumCapacity</code> argument is nonpositive, this
 * method takes no action and simply returns.
 *
 * @param   minimumCapacity   the minimum desired capacity.
 */
public synchronized void ensureCapacity(int minimumCapacity) {
    if (minimumCapacity > value.length) {
        expandCapacity(minimumCapacity);
    }
}

它准确地记录了倍数二加二的行为,因此即使在此期间一些JRE开发人员找到了更好的策略,也没有机会在这里实现它,因为它不符合文档。


推荐