StringBuilder StringBuffer and source code analysis

Strings are immutable once created. Immutable!

Question: Since strings are immutable, how are the common methods of modifying values that they contain implemented?

We often use String String + or += to change the value of the String. This is a special case!

First of all, + and += are the only overloaded operators in JAVA whose String object does not change when adding strings, but its value changes!

Case 1:

String str = "Hello" + "Wrold";
Copy the code

Decompiling it using the javap command yields the following code:

str = new StringBuilder("Hello").append("Wrold").toString();
Copy the code

Conclusion: From the above example, we can see that the String + operation is actually performed through the StringBuilder.

From an efficiency point of view, using the + concatenation string in most cases does not cause a loss of efficiency and can improve the program’s readability and brevity!

Case 2:

String str = "0";
String append = "1";
for(int i = 0; i < 10000; i++){// Result: STR = 011111....... Many (1)
    str += append;
}
Copy the code

In this case, if decompiled, the result would be something like this:

.for(int i = 0; i < 10000; i++){// Result: STR = 011111....... Many (1)
    str = (new StringBuilder()).append(str).append(append).toString(); 
}    
Copy the code

In this case, since a large number of StringBuilders are created in heap memory, there is definitely a loss of efficiency, so in this case it is recommended to create a StringBuilder object outside of the loop and call the Append () method to manually concatenate it!

Case 3:

In addition to the above two cases, let’s analyze a special case, namely:

When both ends of + are String constants (in this case, “XXX” rather than a final String), they are concatenated directly after compilation. For example:

System.out.println("Hello" + "World");
Copy the code

After decompiling, it becomes:

System.out.println("HelloWorld");
Copy the code

In such cases the efficiency of concatenating strings by + is optimal!

StringBuffer is also a mutable string class! It can also be viewed as a container.

• StringBufferCan be achieved bytoString()Method convert toString
• String can be converted to StringBuffer using the StringBuffer constructor

eg:

String string = new StringBuffer().toString();
StringBuffer stringBuffer = new StringBuffer(new String());
Copy the code

Stringbuffer concatenates strings less efficiently than StringBuilder, but it is thread-safe!

// An immutable char array is used to hold strings, indicating that it is immutable.
private final char value[];

// The hash variable of type int is used to store the computed hash value.
private int hash; // Default is 0

// Serialize the version number
private static final long serialVersionUID = -6849794470754667710L;
Copy the code

A simple method

// String length
public int length(a) {
    return value.length;
}

// Whether the string is empty
public boolean isEmpty(a) {
    return value.length == 0;
}

// Get the character at the corresponding position of the character array according to the subscript
public char charAt(int index) {
    if ((index < 0) || (index >= value.length)) {
        throw new StringIndexOutOfBoundsException(index);
    }
    return value[index];
}

// Get an array of bytes
public byte[] getBytes() {
    return StringCoding.encode(value, 0, value.length);
}
Copy the code

The key way to

// Returns the hash code for this string
public int hashCode(a) {
    int h = hash;
    // If the hash has not been evaluated and the string is not empty, the hashCode evaluation is performed
    if (h == 0 && value.length > 0) {
        char val[] = value;
        
        // The calculation process
        //val[0]*31^(n-1) + val[1]*31^(n-2) + ... + val[n-1]
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}
Copy the code

The String class overrides the hashCode method. The hashCode method in Object is a Native call. The hashCode of the String class is polynomial, and we can produce the same hash from different strings, so just because two strings have the same hashCode doesn’t mean two strings are the same.

So why use base 31 when calculating hash values?

Each object evaluates a HashCode based on its value. The code size is not necessarily unique (it is usually very slow), but it should be as small as possible, so the cardinality should be as large as possible. In addition, 31N can be optimized by the compiler to move 5 bits to the left and subtract 1, i.e. 31N = (N<<5)-1, which has high performance. The reason for using 31 is probably to allocate hash addresses better, and 31 only takes up 5bits!

Conclusion:

• The cardinal number is primeThe property of prime numbers (only 1 and itself are factors) makes it easier to produce unique results when multiplied by other numbers than by other methods, i.eThe Hash Code value has the lowest conflict probability.
• Option 31 is a choice made after observing the result of the hash distribution. It is not clear why, but it is beneficial (more dispersion, less conflict).

// Determines whether the substring of this string starts at the specified index and begins with the specified prefix
public boolean startsWith(String prefix, int toffset) {
    char ta[] = value;
    int to = toffset;
    char pa[] = prefix.value;
    int po = 0;
    int pc = prefix.value.length;
    // Note: toffset might be near -1>>>1.
    // If the start address is less than 0 or (the start address + the length of the compared object) is greater than the length of its own object, false is returned
    if ((toffset < 0) || (toffset > value.length - pc)) {
        return false;
    }
    // Start at the end of the object being compared
    while (--pc >= 0) {
        if(ta[to++] ! = pa[po++]) {return false; }}return true;
}

// startsWith overloads method 1
public boolean startsWith(String prefix) {
    return startsWith(prefix, 0);
}

// startsWith overloads method 2
public boolean endsWith(String suffix) {
    return startsWith(suffix, value.length - suffix.value.length);
}
Copy the code

Start comparison and end comparison are commonly used to compare, for example, to determine whether a string is HTTP, or to determine whether a file is mp3.

// Returns a string produced by replacing all occurrences of oldChar in the string with newChar
public String replace(char oldChar, char newChar) {
    // Compare the old and new values first
    if(oldChar ! = newChar) {int len = value.length;
        int i = -1;
        char[] val = value; /* avoid getfield opcode */
        // Find where the old value started
        while (++i < len) {
            if (val[i] == oldChar) {
                break; }}// Start at that position and end with the new value instead of the old value
        if (i < len) {
            char buf[] = new char[len];
            for (int j = 0; j < i; j++) {
                buf[j] = val[j];
            }
            while (i < len) {
                char c = val[i];
                buf[i] = (c == oldChar) ? newChar : c;
                i++;
            }
            // Note that a new String is returned, not the original String
            return new String(buf, true); }}return this;
}
Copy the code

public static void main(String[] args) {
    String a = "a"+"b"+1;
    String b = "ab1";
    // ab1 is in the constant pool
    // If a and b are both equal to ab1, there is only one copy in memory, so == true
    System.out.println("Hash of A:" + a.hashCode());
    System.out.println("Hash of b:" +b.hashCode());
    System.out.println("Address of A:" +System.identityHashCode(a));
    System.out.println("B's address:" +System.identityHashCode(b));
    System.out.println(a == b);
    System.out.println("--------------------------------------------------- String a1 = new String("ab1"); String b1 = "ab1"; // The new method determines the String.ab1// b1 is in the constant pool so == returns false system.out.println ("The hash value of A1:" + a1.hashCode()); System.out.println("Hash value of B1:" +b1.hashCode()); System.out.println("Address of A1:" +System.identityHashCode(a1)); System.out.println("Address of B1:" +System.identityHashCode(b1)); System.out.println(a1 == b1); }Copy the code

Output result:

public final class StringBuilder
    extends AbstractStringBuilder
    implements java.io.Serializable.CharSequence
{... }Copy the code

First, StringBuilder is modified by the final keyword just like String. The class cannot be inherited!

AbstractStringBuilder class AbstractStringBuilder class AbstractStringBuilder class AbstractStringBuilder class contains mutable string operations: Append (), INSERT (), delete(), replace(), charAt(), etc. **StringBuffer and StringBuilder ** both inherit this class!

For example, the append(String STR) method in StringBuilder (more on that later) :

/ / Java. Lang. StringBuilder class
@Override
public StringBuilder append(String str) {
    AbstractStringBuilder append(String STR
    super.append(str);
    return this;
}

/ / Java. Lang. AbstractStringBuilder class (interested can read his point in the source code, still have a lot of harvest, only briefly here!)
public AbstractStringBuilder append(String str) {
    if (str == null)
        return appendNull();
    int len = str.length();
    // Its member property value[] is an array expansion, similar to ArrayList expansion
    Int newCapacity = (value.length << 1) + 2;
    // Note that there is a maximum capacity: MAX_ARRAY_SIZE
    ensureCapacityInternal(count + len);
    str.getChars(0, len, value, count);
    count += len;
    return this;
}
Copy the code

StringBuilder also implements Serializable and CharSequence interfaces, indicating that objects of the class can be serialized, and comes with methods for read-only access to character sequences, such as: Length (), charAt(), subSequence(), toString(), etc.

• Unlike the value array in Sting, this array is not modified by the final keyword, and its value can be modified!
• The two member attribute is not on the Java lang. StringBuilder, and located in its parent class Java. Lang. AbstractStringBuilder, the two attributes of the same StringBuffer is also located in the parent class!

String, StingBuilder, and StirngBuffer are similar to containers in that they all maintain an array of type CHAR underneath!

The append method is overloaded with a variety of arguments, such as String int and so on. The principle is similar.

// In the parent class StringBuilder
@Override
public StringBuilder append(Object obj) {
    return append(String.valueOf(obj));
}

// In the parent class StringBuilder
@Override
public StringBuilder append(String str) {
    super.append(str);
    return this;
}

// In the parent class StringBuilder
@Override
public StringBuilder append(boolean b) {
    super.append(b);
    return this; }...AbstractStringBuilder (AbstractStringBuilder)
// Add String
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;
}

AbstractStringBuilder (AbstractStringBuilder)
// Add a Boolean type
public AbstractStringBuilder append(boolean b) {
    if (b) {
        ensureCapacityInternal(count + 4);
        value[count++] = 't';
        value[count++] = 'r';
        value[count++] = 'u';
        value[count++] = 'e';
    } else {
        ensureCapacityInternal(count + 5);
        value[count++] = 'f';
        value[count++] = 'a';
        value[count++] = 'l';
        value[count++] = 's';
        value[count++] = 'e';
    }
    return this;
}
Copy the code

The append() method appends the string representation of the specified parameter type to the end of the character sequence.

The StringBuilder class provides a set of append() methods, It can accept Boolean, char, char[], CharSequence, double, float, int, long, Object, String, StringBuffer, etc.

Each of these methods ends up calling the corresponding method in the parent AbstractStringBuilder class. Finally, the Append () method returns the StringBuilder object itself so that the user can chain calls to methods in the StringBuilder class.

The AbstractStringBuilder class’s various append() methods are pretty much the same. The append() method calls ensureCapacityInternal() to make sure the value array is full before appending characters to the value array.

AbstractStringBuilder (AbstractStringBuilder)
// Determine whether the size of the value array is sufficient. If not, call the newCapacity method to expand the capacity
private void ensureCapacityInternal(int minimumCapacity) {
    // overflow-conscious code
    if (minimumCapacity - value.length > 0) { value = Arrays.copyOf(value, newCapacity(minimumCapacity)); }}AbstractStringBuilder (AbstractStringBuilder)
// Returns the new array capacity
private int newCapacity(int minCapacity) {
    // Increase the size of the array by 2 +2
    int newCapacity = (value.length << 1) + 2;
    if (newCapacity - minCapacity < 0) {
        newCapacity = minCapacity;
    }
    return (newCapacity <= 0 || MAX_ARRAY_SIZE - newCapacity < 0)? hugeCapacity(minCapacity) : newCapacity; }AbstractStringBuilder (AbstractStringBuilder)
// The maximum size of the array
private int hugeCapacity(int minCapacity) {
    if (Integer.MAX_VALUE - minCapacity < 0) { // overflow
        throw new OutOfMemoryError();
    }
    return (minCapacity > MAX_ARRAY_SIZE)
        ? minCapacity : MAX_ARRAY_SIZE;
}
Copy the code

The ensureCapacityInternal() method determines whether the value array is large enough, and if not, calls newCapacity() to expand it.

The newCapacity() method increases the array capacity by 2 +2 by default. An array can be expanded to a maximum of integer.max_value.

Finally, we call the copyOf() static method of the Arrays class to create a new array and copy the original data into the new array, pointing value to the new array.

// In the parent class StringBuilder
@Override
public StringBuilder replace(int start, int end, String str) {
    super.replace(start, end, str);
    return this;
}

AbstractStringBuilder (AbstractStringBuilder)
public AbstractStringBuilder replace(int start, int end, String str) {
    if (start < 0)
        throw new StringIndexOutOfBoundsException(start);
    if (start > count)
        throw new StringIndexOutOfBoundsException("start > length()");
    if (start > end)
        throw new StringIndexOutOfBoundsException("start > end");

    if (end > count)
        end = count;
    int len = str.length();
    int newCount = count + len - (end - start);
    ensureCapacityInternal(newCount);

    System.arraycopy(value, end, value, start + len, count - end);
    str.getChars(value, start);
    count = newCount;
    return this;
}

// in java.lang.string
void getChars(char dst[], int dstBegin) {
    System.arraycopy(value, 0, dst, dstBegin, value.length);
}
Copy the code

The replace() method replaces characters in the specified position with characters in the specified string. The replacement character starts at the specified start position up to the end-1 position.

The replace() method also calls the corresponding method in the parent AbstractStringBuilder class.

The replace() method first checks the validity of the argument. When end is greater than the number of characters already stored in the value array count, end takes the value count. The ensureCapacityInternal() method is then called to ensure that the value array has sufficient capacity. The static arrayCopy () method of the System class is then called to make a copy of the array. The main effect is to empty the len position of the replacement string starting at the start position. Finally, the getChars() method of the String class is called to copy the characters from the replaced String into the value array. This completes the substitution of characters.

• The StringBuilder class uses an array of char to store characters. This array is a dynamic array that can be expanded when the storage capacity becomes insufficient.
• The StringBuilder object is a mutable sequence of characters.
• The StringBuilder class is non-thread-safe.

public final class StringBuffer
    extends AbstractStringBuilder
    implements java.io.Serializable.CharSequence
{... }Copy the code

StingBuffer and StringBuilder inherit the same parent class, implement the same interface, and are both modified by the final keyword and cannot be inherited, so I won’t repeat this!

public StringBuffer(a) {
    super(16);
}

public StringBuffer(int capacity) {
    super(capacity);
}

public StringBuffer(String str) {
    super(str.length() + 16); append(str); }...Copy the code

There is no difference between StringBuffer and StringBuilder in terms of constructors.

A StringBuffer has a method called ensureCapacity that inherits from the AbstractStringBuilder class:

// is in StringBuffer
@Override
public synchronized void ensureCapacity(int minimumCapacity) {
    super.ensureCapacity(minimumCapacity);
}

// in the parent class
public void ensureCapacity(int minimumCapacity) {
    if (minimumCapacity > 0)
        ensureCapacityInternal(minimumCapacity);
}
Copy the code

StringBuffer overrides this, calling the parent’s expandCapacity method directly. This method is used to ensure that the length of value is greater than the given minimumCapacity parameter, in the parent ensureCapacityInternal method:

private void ensureCapacityInternal(int minimumCapacity) {
    // overflow-conscious code
    if (minimumCapacity - value.length > 0) { value = Arrays.copyOf(value, newCapacity(minimumCapacity)); }}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; }Copy the code

The resulting new value array size is Max (value.length*2+2,minimumCapacity). The second judgment in the code above is to prevent newCapacity overflow.

Each append and insert function in a StringBuffer calls the parent function:

@Override
public synchronized StringBuffer append(Object obj) {
    toStringCache = null;
    super.append(String.valueOf(obj));
    return this;
}

@Override
public synchronized StringBuffer insert(int index, char[] str, int offset, int len) {
    toStringCache = null;
    super.insert(index, str, offset, len);
    return this;
}
Copy the code

In the parent class, these functions first ensure that the value is large enough to store the content to be added:

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

public AbstractStringBuilder insert(int index, char[] str, int offset, int len){
    if ((index < 0) || (index > length()))
        throw new StringIndexOutOfBoundsException(index);
    if ((offset < 0) || (len < 0) || (offset > str.length - len))
        throw new StringIndexOutOfBoundsException(
            "offset " + offset + ", len " + len + ", str.length "
            + str.length);
    ensureCapacityInternal(count + len);
    System.arraycopy(value, index, value, index + len, count - index);
    System.arraycopy(str, offset, value, index, len);
    count += len;
    return this;
}
Copy the code

The parent class ensures size via ensureCapacityInternal’s function, which looks like this:

private void ensureCapacityInternal(int minimumCapacity) {
    // overflow-conscious code
    if (minimumCapacity - value.length > 0)
        expandCapacity(minimumCapacity);
}
Copy the code

If you run out of space, the expandCapacity method is eventually called as well. This ensures that there is enough space for the value operation.

As you can see, the difference between StringBuffer and StringBuilder in adding the append() method is that the former adds a synchronized lock and is therefore thread-safe, while the latter is non-thread-safe!

There is no difference between StringBuffer and StringBuilder in determining whether to expand and how to expand.

If the article is helpful to you, click a concern or support, thank you ~