String Intern???

Today we explore a commonly asked interview question of Java String#intern()

Question

So the commonly asked question is: what is the output of following code (run using Java8) and explain why:

String s1 = new String("s1");
// notice this is `==`, is to compare address
System.out.println(s1.intern() == s1);
String s2 = new String("s") + new String("2");
// notice this is `==`, is to compare address
System.out.println(s2.intern() == s2);
Strig s3 = "s3";
// notice this is `==`, is to compare address
System.out.println(s3.intern() == s3);

---

Think a while before continue.

Answer

false
true
true

The explanation is a bit complex, so let us start with the Java doc of intern:

Returns a canonical representation for the string object.
A pool of strings, initially empty, is maintained privately by the class String.
When the intern method is invoked, if the pool already contains a string equal to this String object as determined by the equals(Object) method, then the string from the pool is returned. Otherwise, this String object is added to the pool and a reference to this String object is returned.

After viewing the doc, we may be still not clear the differences between s1 and s2. Don’t be worried, let’s explore what the doc means by combining code.

As the doc says, if a string is not in string pool, it will be added and return reference to this string, i.e. the return value in this case will be same with original string:

s.intern() == s

which seems the case of s2.

In other words, s1 goes to another branch: the pool already had the same content string and return directly, i.e. the return value may be different with invoked string. And for s1 it is different as output shows.

What about s3? The short answer is the pool has the same content string and return it. And the s3 is the one in string pool.

In order to understand those behavior we have to understand the so called ‘String Pool’.

String Pool

What Is String Pool?

This is the first reason we are wondering: what exactly the string pool is?

By following the call stack of method call, we will follow from java code to cpp code (for which intern is a native method). Finally, we can find the following implementation code in HotSpot JVM:

oop StringTable::intern(Handle string_or_null, jchar* name,  
                        int len, TRAPS) {  
  unsigned int hashValue = java_lang_String::hash_string(name, len);  
  int index = the_table()->hash_to_index(hashValue);  
  oop string = the_table()->lookup(index, name, len, hashValue);  
  // Found  
  if (string != NULL) return string;  
  // Otherwise, add to symbol to table  
  return the_table()->basic_add(index, string_or_null, name, len, hashValue, CHECK_NULL);  
}

In short, the StringTable is a fixed size HashMap<hashcode, string> (If you are interested in more details, you may refer to this openjdk implementaion). So, we can just take the so-called ‘String Pool’ a HashMap.

What is In String Pool

Understand what is String Pool, we need to know what is in String Pool:

String s1 = "1";
String s2 = new String("2");
String s3 = "" + new String("3");
String s4 = new String("4") + new String("4");
String s5 = "1" + "2";
String s6 = "1" + 3;

• literal strings and string-valued constant expressions are default in it – "1" (so as s1), "2", "", "3", "4", "12"(s5), "13"(s6)
• a string will promote to string pool after intern if not already exist

What should be noticed here is s5 & s6: they will be combined to string const by compiler, as this question described.

Where Is String Pool

The last question is where is string pool? This is related with the memory structure of JVM and we will just gloss over it.

JVM

As we all know, JVM has some key components: class loading system, runtime, execution engine, etc. The heap in runtime area is the area of program allocation and ‘String Pool’ is no exception.

Heap

Heap is divided into three main areas in Java, according to the age:

• Young Generation
• Old Generation, tenured space
• Permanent Generation – removed in Java8, replaced with meta area

In Java 6 and before, ‘String Pool’ is stored in Permanent Generation, but it is moved to Young/Old Generation (string literal is on Old Generation, but there may exists some string object which is on young generation¹) in Java 7 in order to assist the removal of Permanent Generation.

// (1) string const is in String Pool (tenured space)
// (2) new allocated object should normally on young generation
// So: s is on young area not in String Pool, "1" in String Pool (tenured space)
String s = new String("1");

Detailed Explanation

So back to our example, this time we add more explanation comment:

String s1 = new String("s1");
// (1) s1.intern() will return ref to "s1" which is in tenured space
// (2) s1 is on young generation, not in String Pool 
// So: s1 != "s1"
System.out.println(s1.intern() == s1);
String s2 = new String("s") + new String("2");
// (1) s2 is on young area
// (2) String Pool doesn't not have "s2", so s2 is added and returned
// So: s2 == s2
System.out.println(s2.intern() == s2);
Strig s3 = "s3";
// (1) "s3" is in String Pool
// (2) s3.intern try to find same content string and find itself, just return s3
// s3 == s3, "s3" == "s3"
System.out.println(s3.intern() == s3);

More Tests

Write the Output (Environment: Java7)

One

String s1 = new String("1");
s1.intern();
String s2 = "1";
System.out.println(s1 == s2);

String s3 = new String("1") + new String("1");
s3.intern();
String s4 = "11";
System.out.println(s3 == s4);

Second

String s1 = new StringBuilder("why").append("true").toString();
System.out.println(s1.intern() == s1);

---

Why and When

We talked a lot about String.intern(), but why we need it?

As we have said above, the interned string is in a string pool, which is a cache for unique strings. So the functionality of this method is to save memory when we have many duplicate strings. But be careful about this JVM maintained cache, it can’t be evicted, which may be not suitable for your case.

Actually, Long/Integer/Byte etc also have some object pooling, to save memory, like following:

public static Long valueOf(long l) {  
    final int offset = 128;  
    if (l >= -128 && l <= 127) { // will cache  
        return LongCache.cache\[(int)l + offset\];  
    }  
    return new Long(l);  
}

Ref

• A Chinese blog related to String#intern
• Hotspot source code
• Source of test

Written with StackEdit.

---

1. This conclusion is from the this method source (which is called when need to add string to string pool; comments are mine), and may be changed during version. So you should not depend on this behavior: ↩︎