posted 12 years ago
Thanks for the challenging question. I really appreciate it. It took me a long time to figure out, but it is worth it.
The problem comes from int hashcode() method.
Try to use public int hashCode() with a capital C instead.
Your MString does not override hashCode() method from the Object class.
Therefore, your MString ("1") , MString("3") and MString("1") and MString("2") all have unique hash codes.
Case 1 : when the hashCode() method is not overriden.
When you put MString objects into hash set or linked hash set, here are the steps implemented by hashset class or linkedhashset class :
1. MString("1") has a unique hashcode generated during runtime. For example, its hashcode is 1001. This object is put into a table in hashset class or linked hash set class. This table is called entry table, which is an array. Let's say, it will put entrytable [1001] = new MString("1");
2. MString ("3") has a unique hashcode. For example, its hashcode is 3001. Then, entrytable[3001]= new MString("3");
3. MString("1") has a UNIQUE hashcode. For example, its hashcode is 4001. Then, entrytable[4001]= new MString("1") and etc.
Therefore, you end up having 4 entries in the sets.
Case 2: when the hashCode() method is overriden.
1. MString("1") has a hash code which is 1. The entryTable[1] = new MString("1");
2. MString("3") has a hash code which is 1. The entryTable[1] has a value assigned as step 1. So, what should hash set do? Check if MString("3") equals MString("1"). They are not equal. Then, etnryTable[1] will have a list data structure, the first element in the list is MString("3") and the second one is MString("1"); Now, entryTable[1] has two objects. Just like a bucket has two balls.
3. MString("1") has a hash code which is also 1. The entryTable[1] has two values now. So, what should hash set do? Check if MString("1") equals the two values. Yes. It equals to another MString("1") that has exist. It is just like you have two balls, a red ball and a blue ball in the bucket. Now, you try to put another red ball in. But there exists a red ball in the bucket, so this second red ball won't be added.
For more detail or verify what I say , read the open source code about HashSet or HashMap developed by Oracle.