String Vs Stringbuffer as HashMap key

问题:

I am trying to understand why String and Stringbuilder/StringBuffer are treated differently when used as Hashmap keys. Let me make my confusion clearer with the following illustrations:

Example #1, using String:

String s1 = new String("abc");
String s2 = new String("abc");
HashMap hm = new HashMap();
hm.put(s1, 1);
hm.put(s2, 2);
System.out.println(hm.size());

Above code snippet prints '1'.

Example #2, using StringBuilder(or StringBuffer):

StringBuilder sb1 = new StringBuilder("abc");
StringBuilder sb2 = new StringBuilder("abc");
HashMap hm = new HashMap();
hm.put(sb1, 1);
hm.put(sb2, 2);
System.out.println(hm.size());

The above code snippet prints '2'.

Could anyone please explain why the difference in behaviour.

回答1:

StringBuilder/Buffer do not override hashCode and equals. This means each instance of the object should be a unique hash code and the value or state of it does not matter. You should use the String for a key.

StringBuilder/Buffer is also mutable which is generally not a good idea to use as a key for a HashMap since storing the value under it can cause the value to be inaccessible after modification.

http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/lang/StringBuilder.java

回答2:

StringBuilder uses Object's default hashcode() implementation, whereas Strings are compared by value for the map keys.

The way that Map works (specifically HashMap) is that it utilizes an object's hashcode, not the contents of the class.

Note you lack parameterization on your maps:

HashMap yourMap = new HashMap();
//Should be
Map<String, Integer> yourMap = new HashMap<>();

And that there is no reason to create new string objects rather than assigning interned literals:

String s1 = "abc";

回答3:

I noticed you are using new String("abc"); which means you know that String a = "abc" and String b = "abc" are the same.

So, a == b returns true. and a.equals(b) returns true.

However the same thing doesn't work for StringBuffers, because its equals doesn't take into account the value of the object, only its hashcode.

If you look into StringBuffer you will see that it uses Object.equals, which is

public boolean equals(Object obj) {
    return (this == obj);
}

While the equals for String is:

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

回答4:

To understand the behaviour it is important to understand how Hashmaps work. Hashmaps use hash code value returned by the key objects (String objects in this case) to store them into appropriate memory compartments referred to as buckets. So, when retrieving the value associated with it hashmaps need to locate the compartment where the key is stored and then return the value against that key. Hashmaps identify the compartment from the hash code value of the key.

Now, imagine, if I have two objects which have same hash code value, what would happen? In such case the hashmap needs to know first whether both objects are same because if they are, then it would mean only one entry in the map and the existing value associated with that key will be replaced with the new value. But, merely having same hash code does not mean both keys are equal. So, the equality is determined by calling .equals() method on the key objects. If .equals() returns true then the objects are equal and in such a case the hashmaps need to update the value for the existing entry. But what if .equals() returns false? In that case both objects are different and should be stored as separate entries. So, they are stored side by side in the same compartment. So, when retrieving the value, the input key's hashcode is used to reach the compartment where it is stored and then if the compartment contains more than one objects then the input key is checked for equality with each object in the compartment and if matched then the associated value is returned.

Now, lets apply the above theory to the code you have. String objects are equal if their contents are equal. And by rule, if two objects are equal they should return same hash code. But remember, converse is not true. If two objects return same hash code that does not require them to be equal. This seems confusing at first but you can get over it in a few iterations. Two strings with same contents are equal and return same hash code even if they are physically different objects and hence when used as key in hashmap would always map to the same entry. And hence the behaviour.

The String class overrides the default equals() method which says two objects are equal if they have same references with the one which relies on the contents for equality. And it can do so because Strings are immutable. But, StringBuffer does not do that. It still relies on reference equality.