字串資料結構的實作

上一篇文章

簡介

在Java的基本資料型別中,并不包含字串這個關鍵字，字串的底層實際上是由字符陣列實作的，String物件也是一個不可變的物件，如果查看JDK檔案,你就會發現String類中的每一個看起來是修改了物件的方法,其本質上都是創建了一個全新的String物件以包含修改后的字串內容，而原先的字串絲毫未動，

本人過去曾寫過一篇關于串的資料結構博客,點擊該鏈接可以進去

String

實作字串參考的字符陣列

private final char value[];

當我們new了一個字串物件的時候，創建的字串其實是引數字串的副本，因為字串是不可變的，

public String(String original) {
        this.value = original.value;
        this.hash = original.hash;
    }

charAt方法

這個方法的作用主要是根據索引回傳指定位置的字符,由于字串底層是一個字符陣列,所以只需要判斷索引是否合法就可以直接回傳了，

public char charAt(int index) {
        if ((index < 0) || (index >= value.length)) {
            throw new StringIndexOutOfBoundsException(index);
        }
        return value[index];
    }

length方法

字符陣列的大小,也就是字串的長度，所以length方法只需要直接回傳陣列的大小即可

public int length() {
        return value.length;
    }

isEmpty方法

判斷字串的是不是空串,只需要判斷陣列的長度是不是等于0就好了

public boolean isEmpty() {
        return value.length == 0;
    }

equals方法

equals方法和= =就不太一樣了，當元素內容相同的時候地址不一樣,那么= =回傳的結果依然是false，因為 = =是通過地址來進行比較的，而equals呢,即使地址不一樣,只要內容完全一樣,就會回傳true，

public boolean equals(Object anObject) {
        if (this == anObject) {
            return true;
        }
        if (anObject instanceof String) {
            String anotherString = (String)anObject;
            int n = value.length;
            if (n == anotherString.value.length) {
                char v1[] = value;
                char v2[] = anotherString.value;
                int i = 0;
                while (n-- != 0) {
                    if (v1[i] != v2[i])
                        return false;
                    i++;
                }
                return true;
            }
        }
        return false;
    }

indexOf方法

通過字符回傳該字符所在字串的位置，其實作的方法則是通過遍歷字符陣列來實作的,通過底層的一層層呼叫,最后呼叫的方法實際是indexOfSupplementary

private int indexOfSupplementary(int ch, int fromIndex) {
        if (Character.isValidCodePoint(ch)) {
            final char[] value = this.value;
            final char hi = Character.highSurrogate(ch);
            final char lo = Character.lowSurrogate(ch);
            final int max = value.length - 1;
            for (int i = fromIndex; i < max; i++) {
                if (value[i] == hi && value[i + 1] == lo) {
                    return i;
                }
            }
        }
        return -1;
    }

compareTo方法

這個方法的功能主要是比較兩個字串的大小，為了保證效率,避免很多不必要的操作,因此底層先用lim變數存盤了兩個字串長度小的那個資料,這樣一來回圈的次數可以減少，if(c1 != c2){ return c1 - c2 }的意思主要是,假如兩個字串一樣長的話,就用ASCll碼來進行比較，

public int compareTo(String anotherString) {
        int len1 = value.length;
        int len2 = anotherString.value.length;
        int lim = Math.min(len1, len2);
        char v1[] = value;
        char v2[] = anotherString.value;

        int k = 0;
        while (k < lim) {
            char c1 = v1[k];
            char c2 = v2[k];
            if (c1 != c2) {
                return c1 - c2;
            }
            k++;
        }
        return len1 - len2;
    }

replace方法

replace方法則是將字串中老的字符替換成新的字符，首先它會判斷老字符和新的字符是否相同,如果相同就沒必要修改，不相同的話,那么它會先用len得到字符陣列的長度,再用val來保存新的字符陣列，用變數i作為索引來定位到老字符的位置，最后再用新的buf字符陣列保存新的字串進行回傳，也就是說,雖然這個方法是修改功能，但其本質上也只是創建了一個新的字符陣列而已，原先的那個依然是絲毫未動，

public String replace(char oldChar, char newChar) {
        if (oldChar != newChar) {
            int len = value.length;
            int i = -1;
            char[] val = value; /* avoid getfield opcode */

            while (++i < len) {
                if (val[i] == oldChar) {
                    break;
                }
            }
            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++;
                }
                return new String(buf, true);
            }
        }
        return this;
    }

StringBuilder

簡介

StringBuilder是一個可變的字符序列,底層繼承了AbstractStringBuilder的抽象類,其本質也依然是采用字符陣列實作的，但StringBuilder的實作和String又不太相同,StringBuilder看起來更像是ArrayList一般的動態陣列，因為,StringBuilder一開始會先給陣列一個初始長度,然后會用一個變數來統計字串的長度，也就是說,在String里面,字串的長度就等于字符陣列的長度，而在StringBuilder里面,字串的長度就未必會等于字符陣列的長度，而且,一旦字串的長度超過了字符陣列的長度,那么它底層則會呼叫一個方法對該字符陣列進行擴容，

我們初次new的時候,它的初始長度會是字串的大小+16

public StringBuilder(String str) {
        super(str.length() + 16);
        append(str);
    }

append方法

append方法的功能是在原先的字串上添加字符或者字串,實作原理就是直接在字符陣列后面加一個元素,因為前面也說了，字串的長度并不等于字符陣列的長度，所以直接value[count++] = c;就好了，那么問題來了,如果長度超出了字符陣列的范圍怎么辦?其實它底層是呼叫了ensureCapacityInternal方法，

private void ensureCapacityInternal(int minimumCapacity) {
        // overflow-conscious code
        if (minimumCapacity - value.length > 0) {
            value = Arrays.copyOf(value,
                    newCapacity(minimumCapacity));
        }
    }

這個方法會讓字符陣列的長度進行擴容,到底擴容多少呢?我們在newCapacity方法里看到,是擴容了1倍+2，之所以使用位運算是因為位運算的效率相對乘法而言更高，

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

delete方法

delete方法會洗掉起始索引和終點索引內的元素，start是開區間,end則是閉區間，它的實作原理是先判斷兩個索引是否合法,如果合法就會呼叫System.arraycopy方法來實作

public AbstractStringBuilder delete(int start, int end) {
        if (start < 0)
            throw new StringIndexOutOfBoundsException(start);
        if (end > count)
            end = count;
        if (start > end)
            throw new StringIndexOutOfBoundsException();
        int len = end - start;
        if (len > 0) {
            System.arraycopy(value, start+len, value, start, count-end);
            count -= len;
        }
        return this;
    }

deleteCharAt方法

這個方法和剛才的洗掉原理是一樣的,先判斷索引是否合法,再呼叫System.arraycopy實作

public AbstractStringBuilder deleteCharAt(int index) {
        if ((index < 0) || (index >= count))
            throw new StringIndexOutOfBoundsException(index);
        System.arraycopy(value, index+1, value, index, count-index-1);
        count--;
        return this;
    }

insert方法

這個方法看起來和append很像，不同的是,append是默認在字串的尾部添加元素,而insert則是根據索引添加元素，如果長度不夠了,又會呼叫方法進行擴容

public AbstractStringBuilder insert(int offset, String str) {
        if ((offset < 0) || (offset > length()))
            throw new StringIndexOutOfBoundsException(offset);
        if (str == null)
            str = "null";
        int len = str.length();
        ensureCapacityInternal(count + len);
        System.arraycopy(value, offset, value, offset + len, count - offset);
        str.getChars(value, offset);
        count += len;
        return this;
    }

replace方法

在StringBuilder里面的replace和String里面的實作方式就有所不同，在StringBuilder里面,replace可以根據起始索引和終止索引范圍內的字串進行修改，其實作方式依然是先判斷索引,再重新定位大小,接著呼叫arraycopy方法進行操作，

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

reverse方法

這個方法的功能主要是實作字串的反轉，其最底層呼叫的是reverseAllValidSurrogatePairs方法

private void reverseAllValidSurrogatePairs() {
        for (int i = 0; i < count - 1; i++) {
            char c2 = value[i];
            if (Character.isLowSurrogate(c2)) {
                char c1 = value[i + 1];
                if (Character.isHighSurrogate(c1)) {
                    value[i++] = c1;
                    value[i] = c2;
                }
            }
        }
    }

StringBuffer

StringBuffer和StringBuilder的方法基本上都大同小異,但他們本質上的區別還是挺大的，StringBuffer是JDK1.0就存在的類，執行緒安全，做執行緒同步檢查，效率較低，而StringBuilder是JDK1.5才提供的類，執行緒不安全，不做執行緒同步檢查，因此效率較高，當然,實際使用中還是比較推薦使用StringBuilder

格式化輸出

在JavaSE5的時候推出了C語言風格的printf();printf里面不使用 "+"來連接,而是使用逗號分隔

public static void main(String[] args) {
        System.out.printf("%d + %d = %d",5,9,5 + 9);
    }

System.out.format()

format方法可以用于PrintStream和PrintWriter物件,其中也包括System.out物件，formate方法和printf方法是等價的，

public static void main(String[] args) {
        System.out.format("%d + %d = %d",5,9,5 + 9);
    }

Formatter類

在Java中,所有新的格式化功能都由java.util.Formatter類處理，可以將Formatter看作一個翻譯器,它將你的格式化字串與資料翻譯成需要的結果，當你創建一個Formatter物件的時候,需要向其構造器傳遞一些資訊，告訴它最終的結果向哪里輸出，