In-depth explanation of how to automatically expand the capacity of StringBuilder when adding it
StringBuilder Overview
? A variable sequence of characters. This class provides an API compatible with StringBuffer, but does not guarantee synchronization (thread unsafe, efficient)
StringBuilder function
? Mainly used for string splicing
Comparison between String and StringBuilder
Question: String, String can also be spliced, just use +, but why do you need to use StringBuilder to splice?
reason:
①Every time String is spliced, a new string object will be generated, and a space will be opened up in the heap memory. If spliced too many times, it will occupy more memory and be less efficient.
②StringBuilder, the bottom layer comes with a buffer. After splicing strings, they will be saved in this buffer. During the splicing process, new objects will not be generated randomly, which saves memory.
Characteristics of StringBuilder
- The bottom layer has its own buffer. This buffer is a char array that has not been modified by final (byte array after jdk8). The default length is 16
- If the array length is exceeded, the array will automatically expand.
- Create a new array of specified length, copy the elements of the old array to the new array, and then reassign the address value of the new array to the old array
- Expansion 2 times + 2 each time
Usage of StringBuilder
constructor use
StringBuilder() StringBuilder(String str)
Common methods
StringBuilder append (any type of data) -> String splicing, what is returned is StringBuilder itself StringBuilder reverse()-> String flip, what is returned is StringBuilder itself String toString() -> Convert StringBuilder to String -> Use StringBuilder to spell strings quickly and save memory space. After spelling, we may process the spliced strings later, so we need to convert StringBuilder to String. Only then can the methods in String be called to process the spliced strings.
StringBuilder automatic expansion source code analysis
public class Exercise {<!-- --> public static void main(String[] args) {<!-- --> StringBuilder sb = new StringBuilder(); sb.append("b"); } }
? Here we first create a StringBuilder object sb, created using a parameterless constructor. Looking at the source code of StringBuilder and String, we can find that the bottom layer of String is a char[] array modified by final, while the bottom layer of StringBuilder is a char that has not been modified by final. []array
private final char value[]; //String class
abstract class AbstractStringBuilder implements Appendable, CharSequence{<!-- --> char[] value; //StringBuilder class int count; }
When we call the append() method to add elements, we enter the underlying source code of append()
@Override public StringBuilder append(String str) {<!-- --> super.append(str); return this; }
After entering, carry the formal parameter String str and call the append(str) method of the parent class to pass it. At this time we enter the parent class super
public AbstractStringBuilder append(String str) {<!-- --> if (str == null) return appendNull(); int len = str.length(); ensureCapacityInternal(count + len); str.getChars(0, len, value, count); count + = len; return this; }
First we execute the steps in the append method
if (str == null) return appendNull();
You can see that the passed formal parameter str is first compared with null to determine whether the passed in is an empty object. If not, the if statement will not be entered for judgment. Otherwise, the if statement will be entered for judgment. You can see that if the passed in If str is empty, the appendNull() method is returned.
private AbstractStringBuilder appendNull() {<!-- --> int c = count; ensureCapacityInternal(c + 4); final char[] value = this.value; value[c + + ] = 'n'; value[c + + ] = 'u'; value[c + + ] = 'l'; value[c + + ] = 'l'; count = c; return this; }
When we enter the appendNull() method, we can find that first it assigns count to an int type variable c, and then calls the ensureCapacityInternal(minimumCapacoty) method, here is ensureCapacityInternal(c + 4); to determine whether expansion is needed, because What is passed in is null, which occupies 4 bytes in char[]. At this time we enter the ensureCapacityInternal(minimumCapacoty) method
private void ensureCapacityInternal(int minimumCapacity) {<!-- --> // overflow-conscious code if (minimumCapacity - value.length > 0) {<!-- --> value = Arrays.copyOf(value, newCapacity(minimumCapacity)); } }
As you can see, the first step is to compare the passed formal parameter minimumCapacity with the array length of the underlying char[] (the default length of the underlying char[] array is 16). If minimumCapacity – 16 > 0, it means that in the original array If the sum of the existing elements plus the newly added elements exceeds 16, then the array needs to be expanded. At this time, the Arrays.copyOf() method is called at the bottom
public static char[] copyOf(char[] original, int newLength) parameter: original - the array to copy newLength - the length of the copy to be returned
Here we need to expand the array. We put the original array value in the first parameter and need to copy it. Then the second parameter needs to set the expansion length of the returned new array. Here, the bottom layer calls newCapacity( minimumCapacity) method.
private int newCapacity(int minCapacity) {<!-- --> // overflow-conscious code int newCapacity = (value.length << 1) + 2; if (newCapacity - minCapacity < 0) {<!-- --> newCapacity = minCapacity; } return (newCapacity <= 0 || MAX_ARRAY_SIZE - newCapacity < 0) ? hugeCapacity(minCapacity) : newCapacity; }
Enter the newCapacity(int minCapacity) method. First, the formal parameter receives the minCapacity parameter, which is the length of count + str.length(). The bottom layer defaults to 2 times the original value.length + 2; at this time, in case of emergency, the The expanded newCapacity is compared with the incoming minCapacity. If it is still less than minCapacity, then minCapacity is directly assigned to the expanded length of the new array, that is, newCapacity. After the assignment is completed, newCapacity is returned. The bottom layer uses a ternary expression when returning
return (newCapacity <= 0 || MAX_ARRAY_SIZE - newCapacity < 0) ? hugeCapacity(minCapacity) : newCapacity;
If , newCapacity < = 0 or MAX_ARRAY_SIZE - newCapacity < 0) is false, newCapacity will be returned.
After the return is completed, our new expanded array means that the creation is successful.
private void ensureCapacityInternal(int minimumCapacity) {<!-- --> // overflow-conscious code if (minimumCapacity - value.length > 0) {<!-- --> value = Arrays.copyOf(value, newCapacity(minimumCapacity)); } }
Rewrite the expanded array to point to value, then modify value with final, pass null into the index value of value, and then reassign count and return
final char[] value = this.value; value[c + + ] = 'n'; value[c + + ] = 'u'; value[c + + ] = 'l'; value[c + + ] = 'l'; count = c; return this;
If the str passed in at this time is not empty, we need to add the contents of str to the expanded array, and the getChars method is called at the bottom
public void getChars(int srcBegin, int srcEnd, char[] dst, int dstBegin) Characters are copied from this sequence into the target character array dst. The first character to be copied is at index srcBegin; the last character to be copied is at index srcEnd-1. The total number of characters to be copied is srcEnd-srcBegin. Characters are copied into a subarray of dst, starting at index dstBegin and ending at index dstbegin + (srcEnd-srcBegin) - 1 parameter: srcBegin - start copying at this offset. srcEnd - Stop copying at this offset. dst - the array to copy the data to. dstBegin - offset to dst.
str.getChars(0, len, value, count); count = c; return this;
That is to say, all the contents of the char[] array at the bottom of str are assigned to the expanded value[count], and then count is reassigned and value is returned.
At this point, we have completed the automatic expansion of StringBuilder objects during addition.