StringBuffer如何在不创建两个对象的情况下实现append函数？

Question

StringBuffer如何在不创建两个对象的情况下实现append函数？

28

这是一道面试题。我被要求实现StringBuffer的追加函数。面试后我看到了代码。但我无法理解如何在创建单个对象的情况下完成操作。

我的想法是这样的。

String s = "orange";
s.append("apple");

这里创建了两个对象。

但是

StringBuilder s = new StringBuilder("Orange");
s.append("apple");

现在只创建了一个对象。

Java是如何执行这个操作的？

- javaMan

问题中有几个假设是不正确的。new StringBuilder()和new String()会创建两个对象。 - Peter Lawrey

3

是我的问题吗？;) - Adam Dray

10个回答

9

源代码是你的朋友，卢克！

这里是AbstractStringBuilder的源代码。

- LordDoskias

AbstractStringBuilder是StringBuilder的父类。 - John B

4

这段代码无法编译。

String S= "orange";
S.append("apple");

如果您这样做

final String S= "orange";
final S2 = S + "apple";

这不会创建任何对象，因为它在编译时被优化为两个字符串字面值。

StringBuilder s = new StringBuilder("Orange");
s.append("apple");

这将创建两个对象 StringBuilder 和它所包含的 char[]。如果您使用

String s2 = s.toString();

这将创建两个新的对象。

如果您执行此操作，

String S= "orange";
S2 = S + "apple";

这与之前的相同。

String S2 = new StringBuilder("orange").append("apple").toString();

这将创建2 + 2 = 4个对象。

- Peter Lawrey

4

String是不可变的。追加字符串只能生成一个新的字符串。

StringBuilder是可变的。向StringBuilder追加内容是一种就地操作，类似于向ArrayList添加元素。

- SLaks

嗨，Slaks，我知道那个。我想知道字符串构建器是如何执行该操作的。 - javaMan

2

StringBuffer和StringBuilder一样，它会分配一个字符数组，将您附加的字符串复制到其中。只有当字符数量超过数组大小时，它才会创建新的对象，在这种情况下，它会重新分配并复制数组。

- Matthew Farwell

1

简而言之：使用加号+进行字符串连接会创建一个新的String对象，并将初始字符串的内容复制到其中。而StringBuffer则持有一个内部结构，在需要时才会扩展，将字符追加到其中。

但是，很多人都在使用加号字符串连接！

好吧，我们/他们不应该这样做。

就内存使用而言，StringBuffer中使用了一个数组来保存字符，虽然它会重新分配空间，但如果其重新分配算法有效，则很少这样做。并且只有在调用toString()方法时创建一个String对象，比在每次执行+连接时创建一个新的String对象要好得多。

就时间复杂度而言，字符仅从_chars复制一次到新字符串中（O(n)时间复杂度），通常比使用+运算符进行字符串连接好得多，在这种情况下，每个操作都会将字符复制到一个新对象中，导致O(1 + 2 + .... + n) = O(n^2)操作。

我应该自己实现吗？

对于练习来说，这将是很好的，但现代语言提供了本地StringBuffer实现，可以在生产代码中使用它。

四个简单的步骤：

Create a MyCustomStringBuilder class that internally (privately) holds an array (let's name it _chars) of characters of a fixed initial size. This array will hold the string characters.
Add an expanding method that will increase the size of _chars once the holding string character length exceeds its length. (What you are practically doing, is implementing a simple version of an ArrayList internally).
When using the stringBufferInstance.append(String s) method, add characters to _chars, increasing its size if needed.
In your toString() method implementation, you can simply create a string using the array:
```
public String toString() {
    return new String(_chars);
}
```

- Nick Louloudakis

1

StringBuilder 在一个 char[] 中保存了一些字符，并在调用 toString 方法时将它们转换为一个 String。

- John B

1

String s = "orange";
s.append("apple");

这是不正确的，因为在String中没有可用的append方法：

- Raja

0

正如其他人所描述的那样，StringBuffer是可变的，并且是通过使用char数组实现的。StringBuffer中的操作是就地操作。

更多信息可以从以下链接获得 http://www.concentric.net/~ttwang/tech/jfastbuf.htm

它展示了使用char数组的简单StringBuffer实现。

- Upul Bandara

-1

****String s1="Azad"; ----One object will create in String cons. pool

System.out.println(s1);--output--Azad

s1=s1.concat("Raja");  Two object will create 1-Raja,2-AzadRaja and address of AzadRaja Store in reference s1 and cancel ref.of Azad object 

System.out.println(s1);  --output AzadRaja****

- Raja

你的回答很难读懂。它是否添加了任何有用的信息，这些信息在已接受的答案中没有包含？ - Duncan Jones

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- stivlo · Accepted Answer

首先，你的问题存在一个问题：

String s = "orange";
s.append("apple");

这里创建了两个对象

没错，创建了两个对象，一个是字符串"orange"，另一个是字符串"apple"。如果没有溢出缓冲区，StringBuffer/StringBuilder内部不会创建任何对象。所以这几行代码创建了2或3个对象。

StringBuilder s = new StringBuilder("Orange");
s.append("apple");

现在这里只创建了一个对象

我不知道你是从哪里得到的信息，这里创建了一个StringBuilder对象，一个"Orange"字符串，一个"apple"字符串，总共3个对象，如果我们溢出StringBuilder缓冲区，则为4个对象（我将数组创建计算为对象创建）。

我理解你的问题是，当缓冲区未溢出时，如何使用StringBuilder进行追加而不创建新对象？

你应该看看StringBuilder，因为它是非线程安全的实现。这段代码很有趣且易读。我已经添加了行内注释。

作为内部结构，它是一个char数组，而不是String。它最初的长度为16，在每次超过容量时都会增加。如果要追加的字符串适合于char数组，则无需创建新对象。

StringBuilder扩展了AbstractStringBuilder，其中包含以下代码：

/**
 * The value is used for character storage.
 */
char value[];

由于并非所有的数组在同一时间都会被使用，因此另一个重要的变量是长度：

/**  
 * The count is the number of characters used.
 */
int count;

append有很多重载，但最有趣的是以下内容：

public AbstractStringBuilder append(String str) {
    if (str == null) str = "null"; //will literally append "null" in case of null
    int len = str.length(); //get the string length
    if (len == 0) return this; //if it's zero, I'm done
    int newCount = count + len; //tentative new length
    if (newCount > value.length) //would the new length fit?
        expandCapacity(newCount); //oops, no, resize my array
    str.getChars(0, len, value, count); //now it will fit, copy the chars 
    count = newCount; //update the count
    return this; //return a reference to myself to allow chaining
}

以下是您需要翻译的内容：

String.getChars(int srcBegin, int srcEnd, char[] dst, int dstBegin) 将此字符串中的字符复制到目标字符数组中。

因此，append方法非常简单，唯一需要发现的魔法是expandCapacity，这里它是：

void expandCapacity(int minimumCapacity) {
    //get the current length add one and double it
    int newCapacity = (value.length + 1) * 2; 
    if (newCapacity < 0) { //if we had an integer overflow
        newCapacity = Integer.MAX_VALUE; //just use the max positive integer
    } else if (minimumCapacity > newCapacity) { //is it enough?
        //if doubling wasn't enough, use the actual length computed
        newCapacity = minimumCapacity;
    }
    //copy the old value in the new array
    value = Arrays.copyOf(value, newCapacity); 
}

Arrays.copyOf(char[] original, int newLength) 会复制指定的数组，如果需要，会用空字符进行截断或填充，以使得复制后的数组长度符合指定值。

在我们的情况下，由于我们要扩展长度，所以是填充操作。