StringTable（一）-阿里云开发者社区

一、字符串前生今世

1.1 如何出生

话说 Java 大家族中有一类对象称为字符串，它的地位举足轻重，就让我们从它的出生开始说起 😄

这里说的出生，就是指对象被创建，那有同学就会说直接 new 呗，所有对象不都是使用 new 来创建吗？

对于字符串，还真有点特殊。

字符串有六种基本的创建（出生）方式

使用 char[] 数组配合 new 来创建
使用 byte[] 数组配合 new 来创建
使用 int[] 数组配合 new 来创建
使用已有字符串配合 new 来创建
使用字面量创建（不使用 new ）
合二为一，使用 + 运算符来拼接创建

可以看到，至少从表面上讲，后两种都没有用到 new 关键字

1.2 char[] 数组创建

这种是最基本的，因为字符串、字符串、就是将字符串起来，结果呢，也就是多个字符的 char[] 数组，例如

String s = new String(new char[]{'a', 'b', 'c'});

String s = new String(new byte[]{97, 98, 99}); // abc

new String(    new byte[]{(byte) 0xD5, (byte) 0xC5},     Charset.forName("gbk"));

new String(    new byte[]{(byte) 0xE5, (byte) 0xBC, (byte) 0xA0},     Charset.forName("utf-8"));

String s = new String(new int[]{0x1F602}, 0, 1);

参考

unicode 9.0 说明

unicode 中的 emoji 表情

1.5 从已有字符串创建

直接看源码

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

String s1 = new String(new char[]{'a', 'b', 'c'});String s2 = new String(s1);

public static void main(String[] args) {    String s = "abc";}

一粥一饭，当思来之不易，半丝半缕，恒念物力维艰

- 《朱子家训》

/**
 * 演示 intern 减少内存占用
 */
public class Demo1 {
    public static void main(String[] args) throws IOException {
        List<String> address = new ArrayList<>();
        System.in.read();
        for (int i = 0; i < 10; i++) {
            try (BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("linux.words"), "utf-8"))) {
                String line = null;
                long start = System.nanoTime();
                while (true) {
                    line = reader.readLine();
                    if(line == null) {
                        break;
                    }
                    address.add(line.intern());
                }
                System.out.println("cost:" +(System.nanoTime()-start)/1000000);
            }
        }
        System.in.read();
    }
}

2.4 家的位置

沉舟侧畔千帆过，病树前头万木春
刘禹锡
StringTable 的位置（1.6）

StringTable 的位置（1.8）

如何证明

1.6 不断将字符串用 intern 加入 StringTable，最后撑爆的是永久代内存，为了让错误快速出现，将永久代内存设置的小一些：-XX:MaxPermSize=10m，最终会出现 java.lang.OutOfMemoryError: PermGen space

1.8 不断将字符串用 intern 加入 StringTable，最后撑爆的是堆内存，为了让错误快速出现，将堆内存设置的小一些：-Xmx10m -XX:-UseGCOverheadLimit 后一个虚拟机参数是避免 GC 频繁引起其他错误而不是我们期望的 java.lang.OutOfMemoryError: Java heap space
代码

/**
 * 演示 StringTable 位置
 * 在jdk8下设置 -Xmx10m -XX:-UseGCOverheadLimit
 * 在jdk6下设置 -XX:MaxPermSize=10m
 */
public class Demo2 {

    public static void main(String[] args) throws InterruptedException {
        List<String> list = new ArrayList<String>();
        int i = 0;
        try {
            for (int j = 0; j < 260000; j++) {
                list.add(String.valueOf(j).intern());
                i++;
            }
        } catch (Throwable e) {
            e.printStackTrace();
        } finally {
            System.out.println(i);
        }
    }
}

2.5 intern 去重原理

致知在格物，物格而后知至
- 《礼记·大学》

查阅一下 jdk 的源码

hg.openjdk.java.net/jdk8u/jdk8u…

// string_or_null 字符串对象
// name 字符串原始指针
// len 字符串长度
oop StringTable::intern(Handle string_or_null, jchar* name,
                        int len, TRAPS) {
  // 获取字符串的 hash 值
  unsigned int hashValue = hash_string(name, len);
  // 算出 hash table 桶下标  
  int index = the_table()->hash_to_index(hashValue);
  // 看字符串在 hash table 中有没有 
  oop found_string = the_table()->lookup(index, name, len, hashValue);

  // 如果有，直接返回（避免重复加入）
  if (found_string != NULL) {
    // 确保该字符串对象没有被垃圾回收  
    ensure_string_alive(found_string);
    return found_string;
  }

  debug_only(StableMemoryChecker smc(name, len * sizeof(name[0])));
  assert(!Universe::heap()->is_in_reserved(name),
         "proposed name of symbol must be stable");

  Handle string;
  // try to reuse the string if possible
  if (!string_or_null.is_null()) {
    string = string_or_null;
  } else {
    // 根据 unicode 创建【字符串对象 string】 
    string = java_lang_String::create_from_unicode(name, len, CHECK_NULL);
  }

#if INCLUDE_ALL_GCS
  if (G1StringDedup::is_enabled()) {
    // Deduplicate the string before it is interned. Note that we should never
    // deduplicate a string after it has been interned. Doing so will counteract
    // compiler optimizations done on e.g. interned string literals.
    G1StringDedup::deduplicate(string());
  }
#endif

  // Grab the StringTable_lock before getting the_table() because it could
  // change at safepoint.
  oop added_or_found;
  {
    MutexLocker ml(StringTable_lock, THREAD);
    // 将【字符串对象 string】加入 hash table
    added_or_found = the_table()->basic_add(index, string, name, len,
                                  hashValue, CHECK_NULL);
  }

  ensure_string_alive(added_or_found);

  return added_or_found;
}

其中 lookup 的定义为

// index 桶下标
// name 字符串原始指针
// len 字符串长度
// hash 哈希码
oop StringTable::lookup(int index, jchar* name,
                        int len, unsigned int hash) {
  int count = 0;
  for (HashtableEntry<oop, mtSymbol>* l = bucket(index); l != NULL; l = l->next()) {
    count++;
    if (l->hash() == hash) {
      if (java_lang_String::equals(l->literal(), name, len)) {
        return l->literal();
      }
    }
  }
  // 如果链表过长，需要 rehash
  if (count >= rehash_count && !needs_rehashing()) {
    _needs_rehashing = check_rehash_table(count);
  }
  return NULL;
}

其中 basic_add 的定义为

// index_arg 桶下标
// string 字符串对象
// name 字符串原始指针
// len 字符串长度
oop StringTable::basic_add(int index_arg, Handle string, jchar* name,
                           int len, unsigned int hashValue_arg, TRAPS) {

  assert(java_lang_String::equals(string(), name, len),
         "string must be properly initialized");
  // Cannot hit a safepoint in this function because the "this" pointer can move.
  No_Safepoint_Verifier nsv;

  // Check if the symbol table has been rehashed, if so, need to recalculate
  // the hash value and index before second lookup.
  unsigned int hashValue;
  int index;
  if (use_alternate_hashcode()) {
    hashValue = hash_string(name, len);
    index = hash_to_index(hashValue);
  } else {
    hashValue = hashValue_arg;
    index = index_arg;
  }

  // Since look-up was done lock-free, we need to check if another
  // thread beat us in the race to insert the symbol.

  oop test = lookup(index, name, len, hashValue); // calls lookup(u1*, int)
  if (test != NULL) {
    // Entry already added
    return test;
  }
    
  // 构造新的 HashtableEntry 节点
  HashtableEntry<oop, mtSymbol>* entry = new_entry(hashValue, string());
  // 加入链表  
  add_entry(index, entry);
  // 返回字符串对象
  return string();
}

2.6 G1 去重

懒云窝，醒时诗酒醉时歌。瑶琴不理抛书卧，无梦南柯
- 阿里西瑛
懒惰是程序员的一大美德，不追求懒惰的程序员不是好程序员

如果你使用的 JDK 8u20，那么可以使用下面的 JVM 参数开启 G1 垃圾回收器，并开启字符串去重功能

-XX:+UseG1GC -XX:+UseStringDeduplication

原理是让多个字符串对象引用同一个 char[] 来达到节省内存的目的

特点

由 G1 垃圾回收器在 minor gc 阶段自动分析优化，不需要程序员自己干预
只有针对那些多次回收还不死的字符串对象，才会进行去重优化，可以通过 -XX:StringDeduplicationAgeThreshold=n 来调整
可以通过 -XX:+PrintStringDeduplicationStatistics 查看 G1 去重的统计信息
与调用 intern 去重相比，G1 去重好处在于自动，但缺点是即使 char[] 不重复，但字符串对象本身还要占用一定内存（对象头、value引用、hash），intern 去重是字符串对象只存一份，更省内存

2.7 家的大小

安得广厦千万间，大庇天下寒士俱欢颜，风雨不动安如山
- 杜甫

StringTable 足够大，才能发挥性能优势，大意味着 String 在 hash 表中冲突减少，链表短，性能高。

可以通过 -XX:+PrintStringTableStatistics 来查看 StringTable 的大小，JDK 8 中它的默认大小为 60013

要注意 StringTable 底层的 hash 表在 JVM 启动后大小就固定不变了

这个 hash 表可以在链表长度太长时进行 rehash，但不是利用扩容实现的 rehash，而是通过重新计算字符串的 hash 值来让它们分布均匀

如果想在启动前调整 StringTable 的大小，可以通过 -XX:StringTableSize=n 来指定

代码

/**
 * 演示串池大小对性能的影响
 * -XX:+PrintStringTableStatistics -XX:StringTableSize=1009
 */
public class Demo3 {

    public static void main(String[] args) throws IOException {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("linux.words"), "utf-8"))) {
            String line = null;
            long start = System.nanoTime();
            while (true) {
                line = reader.readLine();
                if (line == null) {
                    break;
                }
                line.intern();
            }
            System.out.println("cost:" + (System.nanoTime() - start) / 1000000);
        }
    }
}

2.8 字符串之死

All Men Must Die - 凡人皆有一死
《冰与火之歌：权力的游戏》

字符串也是一个对象，只要是对象，终究逃不过死亡的命运。字符串对象与其它 Java 对象一样，只要失去了利用价值，就会被垃圾回收，无论是野生字符串，还是家养字符串

怎么证明家养的字符串也能被垃圾回收呢，可以用以下 JVM 参数来查看

-XX:+PrintStringTableStatistics -XX:+PrintGCDetails -verbose:gc

代码

/**
 * 演示 StringTable 垃圾回收
 * -Xmx10m -XX:+PrintStringTableStatistics -XX:+PrintGCDetails -verbose:gc
 */
public class Demo4 {
    public static void main(String[] args) throws InterruptedException {
        int i = 0;
        try {
            for (int j = 0; j < 100000; j++) { // j=100, j=10000
                String.valueOf(j).intern();
                i++;
            }
        } catch (Throwable e) {
            e.printStackTrace();
        } finally {
            System.out.println(i);
        }

    }
}

三、面试题讲解

1. 判断输出

String str1 = "string"; // 家
String str2 = new String("string"); // 野生
String str3 = str2.intern(); // 家

System.out.println(str1==str2);//#1  false
System.out.println(str1==str3);//#2  true

2. 判断输出

String baseStr = "baseStr";
final String baseFinalStr = "baseStr";

String str1 = "baseStr01"; // 家
String str2 = "baseStr"+"01"; // 家
String str3 = baseStr + "01"; // 野生
String str4 = baseFinalStr+"01";// 家
String str5 = new String("baseStr01").intern(); // 家

System.out.println(str1 == str2);//#3 true
System.out.println(str1 == str3);//#4 false 
System.out.println(str1 == str4);//#5 true
System.out.println(str1 == str5);//#6 true

3. 判断输出（注意版本）

String str2 = new String("str")+new String("01");
str2.intern(); //1.6
String str1 = "str01";
System.out.println(str2==str1);//#7 1.7 true, 1.6 false

4. 判断输出

String str1 = "str01";
String str2 = new String("str")+new String("01");
str2.intern();
System.out.println(str2 == str1);//#8 false

5. String s = new String("xyz")，创建了几个String Object?

6. 判断输出

String s1 = "abc";
String s2 = "abc";
System.out.println(s1 == s2); // true

7. 判断输出

String s1 = new String("abc");
String s2 = new String("abc");
System.out.println(s1 == s2); //false

8. 判断输出

String s1 = "abc";String s2 = "a";String s3 = "bc";String s4 = s2 + s3;System.out.println(s1 == s4); //false

String s1 = "abc";final String s2 = "a";final String s3 = "bc";String s4 = s2 + s3;System.out.println(s1 == s4);//true

String s = new String("abc"); // 野生String s1 = "abc"; // 家String s2 = new String("abc"); // 野生System.out.println(s == s1.intern()); // falseSystem.out.println(s == s2.intern()); // falseSystem.out.println(s1 == s2.intern()); // true

9. 判断输出

StringTable（二）：https://developer.aliyun.com/article/1535761

StringTable（一）

一、字符串前生今世

1.1 如何出生

1.2 char[] 数组创建

1.5 从已有字符串创建

2.4 家的位置

2.5 intern 去重原理

2.6 G1 去重

2.7 家的大小

2.8 字符串之死

三、面试题讲解

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

StringTable（一）

一、字符串前生今世

1.1 如何出生

1.2 char[] 数组创建

1.5 从已有字符串创建

2.4 家的位置

2.5 intern 去重原理

2.6 G1 去重

2.7 家的大小

2.8 字符串之死

三、面试题讲解

热门文章

最新文章

相关电子书