S & B SCJP 6 - C7 - Q4 erratum

[Gijs Peek]

Hi all,

I think I have found an error in the answer to question 4 of chapter 7 in the S & B SCJP book (p. 649-650 in the hard cover book). The question and answer are stated below:

4. Given:
        import java.util.*;
        class MapEQ {
          public static void main(String[] args) {
            Map<ToDos, String> m = new HashMap<ToDos, String>();
            ToDos t1 = new ToDos("Monday");
            ToDos t2 = new ToDos("Monday");
            ToDos t3 = new ToDos("Tuesday");
            m.put(t1, "doLaundry");
            m.put(t2, "payBills");
            m.put(t3, "cleanAttic");
            System.out.println(m.size());
          }
        }
        class ToDos{
          String day;
          ToDos(String d) { day = d; }
          public boolean equals(Object o) {
            return ((ToDos)o).day == this.day;
          }
          // public int hashCode() { return 9; }
        }
Which is correct? (Choose all that apply.)
A. As the code stands it will not compile
B. As the code stands the output will be 2
C. As the code stands the output will be 3
D. If the hashCode() method is uncommented the output will be 2
E. If the hashCode() method is uncommented the output will be 3
F. If the hashCode() method is uncommented the code will not compile
 
  Answer:
 � C and D are correct. If hashCode() is not overridden then every entry will go into its own
  3
     bucket, and the overridden equals() method will have no effect on determining equivalency.
     If hashCode() is overridden, then the overridden equals() method will view t1 and
     t2 as duplicates.
  � A, B, E, and F are incorrect based on the above. (Objective 6.2)

The book states that both C and D are correct, but answer C is actually incorrect: the bucket in which each entry goes is undetermined (based on the default hashcode implementation), and entries *might* go in the same bucket, so the output is either 2 or 3 as the code stands. I confirmed this with an experiment - on my machine, the output was 2 in about 1 in 30,000,000 attempts (edit: it seems that the sun java 6 implementation only invokes the equals() method when the hash codes are equal, which explains the low collision rate: equal hash codes for unequal objects only occur rarely).
So I believe only answer D should be correct.

cheers,
- Gijs Peek
[ January 02, 2009: Message edited by: Gijs Peek ]

[Alejandro Galvan]

Hi,

I tried to replicate your experiment as:

    
import java.util.*;        
 
class MapEQ {
        public static void main(String[] args) {
for (int i=0; i<30000000; i++) {
Map<ToDos, String> m = new HashMap<ToDos, String>();
ToDos t1 = new ToDos("Monday");
ToDos t2 = new ToDos("Monday");
ToDos t3 = new ToDos("Tuesday");
m.put(t1, "doLaundry");
m.put(t2, "payBills");
m.put(t3, "cleanAttic");
if (m.size() != 3)
System.out.println(m.size());
t1 = t2 = t3 = null;
m = null;
System.gc();
}
}
}
 
class ToDos{
String day;
ToDos(String d) {
day = d;
}
public boolean equals(Object o) {
return ((ToDos)o).day == this.day;
}
//public int hashCode() { return 9; }        
}

And I didn't get a "2" in the output, I think you should not base your answers in probability, you should read and understand better how the compiler and the JVM works if you want success, the answers given by the book are correct, remember that, when hashCode is not overriden, it use the method from the super class (in this case from class Object) and that method from Object class return the memory address of the object, so, two different objects will have two different hashcodes, so the equals method won't be called.

Regards,

[Gijs Peek]

Originally posted by Alejandro Galvan:
Hi,

I tried to replicate your experiment as:
(...)
And I didn't get a "2" in the output, I think you should not base your answers in probability, you should read and understand better how the compiler and the JVM works if you want success, the answers given by the book are correct, remember that, when hashCode is not overriden, it use the method from the super class (in this case from class Object) and that method from Object class return the memory address of the object, so, two different objects will have two different hashcodes, so the equals method won't be called.

Regards,

Hi,

Thank you for evaluating my post. However, I am still not convinced of any errors in my reasoning. The inner workings of the compiler and JVM are in this case somewhat unpredictible since the hashcode function defined in Object is a native method. Also, official documentation on this subject seems sparse at best and the contract does not make any promises as to the uniqueness of the hashcode in Object.
As to using the method of probability, I know it is not an instrument to base answers on. However, in this case I only needed one counter-example to disprove the statement made in the book and I don't know of any other way of producing two objects with the same hashcode, as it depends on the memory location.
I don't know where you read that two different objects will have two different hashcodes, but this does not seem to be true.

Using the code

package main;
 
import java.util.*;
class MapEQ {
  public static void main(String[] args) {
int size=3;
long attempts = 0;
while(size==3) {
    Map<ToDos, String> m = new HashMap<ToDos, String>();
    ToDos t1 = new ToDos("Monday");
    ToDos t2 = new ToDos("Monday");
    ToDos t3 = new ToDos("Tuesday");
    m.put(t1, "doLaundry");
    m.put(t2, "payBills");
    m.put(t3, "cleanAttic");
    size = m.size();
    attempts++;
}
    System.out.println(size+" in "+attempts+" attempts");
  }
}
class ToDos{
  String day;
  ToDos(String d) { day = d; }
  public boolean equals(Object o) {
    return ((ToDos)o).day == this.day;
  }
  // public int hashCode() { return 9; }
}

The output I get is "2 in 19326731 attempts".

However, if you want easier proof, you can use the birthday paradox and enlarge the set size, which will scale down the computation time considerably:

package main;
 
import java.util.HashMap;
import java.util.Map;
class MapEQ {
  public static void main(String[] args) {
int size=2000;
int lastSize = size;
long attempts = 0;
while(lastSize==size) {
    Map<ToDos, String> m = new HashMap<ToDos, String>();
    for(int i=0; i<size; i++) {
    m.put(new ToDos("Monday"), "doSomething");
    }
    lastSize = m.size();
    attempts++;
}
    System.out.println(lastSize+" in "+attempts+" attempts");
  }
}
class ToDos{
  String day;
  ToDos(String d) { day = d; }
  public boolean equals(Object o) {
    return ((ToDos)o).day == this.day;
  }
  // public int hashCode() { return 9; }
}

outputs "1999 in 2 attempts" on my machine.

If you still don't believe it, you can try the code fragment

package main;
 
import java.util.HashMap;
import java.util.Map;
class MapEQ {
  public static void main(String[] args) {
int size=2000;
int lastSize = size;
long attempts = 0;
ToDos[] todos = null;
while(lastSize==size) {
    Map<ToDos, String> m = new HashMap<ToDos, String>();
todos = new ToDos[size];
    for(int i=0; i<size; i++) {
    todos[i] = new ToDos("Monday");
    m.put(todos[i], "doSomething");
    }
    lastSize = m.size();
    attempts++;
}
    System.out.println(lastSize+" in "+attempts+" attempts");
    for(ToDos td: todos) {
    for(ToDos td2: todos) {
    if(td != td2 && td.hashCode()==td2.hashCode()) {
    System.out.printf("%s:%x, %s:%x - equals: %b\n", td, td.hashCode(), td2, td2.hashCode(), td==td2);
    }
    }
    }
  }
}
class ToDos{
  String day;
  ToDos(String d) { day = d; }
  public boolean equals(Object o) {
    return ((ToDos)o).day == this.day;
  }
  // public int hashCode() { return 9; }
}

which gives me:

1999 in 2 attempts
main.ToDos@e29820:e29820, main.ToDos@e29820:e29820 - equals: false
main.ToDos@e29820:e29820, main.ToDos@e29820:e29820 - equals: false

This is because the Object's hashcode function doesn't typically use the actual memory addresses of the objects, but derives the hashcode from them using a hashcode function to disperse the actual hashcodes.

[Gijs Peek]

Alejandro Galvan wrote:you should read and understand better how the compiler and the JVM works if you want success, the answers given by the book are correct, remember that, when hashCode is not overriden, it use the method from the super class (in this case from class Object) and that method from Object class return the memory address of the object, so, two different objects will have two different hashcodes, so the equals method won't be called.

Actually, on page 552 the book does mention that the default hashCode method in Object virtually always comes up with a unique number - an important detail in this case.
I understand your frustration when your experiment failed, but i would have appreciated it if you would not have told me off so harshly before actually checking your facts. As a scientist it is good practice not to make bold statements without a reference, proof or some reproducible experiment. When you were not able to reproduce my result you could have asked yourself why I did get a positive result and you didn't instead of immediately drawing the conclusion that I was wrong. Your experiment was hardly statistically relevant, and anyway the chances probably differ across different systems.

[Ankit Garg]

Relax Gijs . The language of Alejandro might be harsh. But he was surely trying to help. So just relax

[Gijs Peek]

Ankit Garg wrote:Relax Gijs . The language of Alejandro might be harsh. But he was surely trying to help. So just relax

Yes, maybe I was overreacting a bit. Anyway, in the answer to question 11 the book mentions that for the purpose of the exam, the hashCode implementation in object does produce unique hashcodes (as far as I can see, they don't mention this earlier in the chapter).
However, the explanation still states that unequal hashcodes will go in different buckets, and for this reason the equals method will not be called. This not true: elements with different hashcodes might still map onto a single bucket (the chance is approximately 1 in 16, because HashMap starts out with 16 buckets and the default hashcode is approximately uniformly random). The sun JVM caches the hash values and only calls the equals method when the hashes mismatch, but I do not believe this is a specific requirement of HashMap's contract. In other words, another JVM implementation (or possibly the Sun JVM in the future) might choose not to cache hash values and call the equals methods instead when iterating over the entries in a single bucket, in which case the program output still remains undetermined even when the HashCodes are guaranteed to be unique.

[Alejandro Galvan]

Hi Gijs,

First of all, my apologize if I wrote a bit harsh, was no my intention. Second, it is not matter that I don't belive you, I really belive you cause it is possible, but as I told you, you should not base your answers in probability and, as you already see:

Gijs Peek wrote:
Anyway, in the answer to question 11 the book mentions that for the purpose of the exam, the hashCode implementation in object does produce unique hashcodes (as far as I can see, they don't mention this earlier in the chapter).

This room is for SCJP purposes, and so do the S&B book, then, and based in your comment I quoted, the book has no errata, and your answer, in the real exam, should be as explained in the book.

However I'm quoting here some other texts for one of the questions you gave me:

Gijs Peek wrote: I don't know where you read that two different objects will have two different hashcodes, but this does not seem to be true.

I don't know if you are aware of the API, if you don't, check it, it is a good place to know the entire Java Application Program Interface, go to http://java.sun.com/javase/6/docs/api/, there, navigate to class java.lang.Object and you'll find the method hashCode and its explanaiton:

hashCode
public int hashCode()Returns a hash code value for the object. This method is supported for the benefit of hashtables such as those provided by java.util.Hashtable.
The general contract of hashCode is:

Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hashtables.
As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)


Returns:
a hash code value for this object.
See Also:
equals(java.lang.Object), Hashtable

Also, I'm posting here the put method from the HashMap class (you can download the source code from the Sun Microsystems site):

    
          /**
          * Associates the specified value with the specified key in this map.
          * If the map previously contained a mapping for the key, the old
          * value is replaced.
          *
          * @param key key with which the specified value is to be associated
          * @param value value to be associated with the specified key
          * @return the previous value associated with <tt>key</tt>, or
          *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
          *         (A <tt>null</tt> return can also indicate that the map
          *         previously associated <tt>null</tt> with <tt>key</tt>.)
          */
         public V put(K key, V value) {
             if (key == null)
                 return putForNullKey(value);
             int hash = hash(key.hashCode());
             int i = indexFor(hash, table.length);
             for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                 Object k;
                 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                     V oldValue = e.value;
                     e.value = value;
                     e.recordAccess(this);
                     return oldValue;
                 }
             }

So, hopefully this helps you in the exam and, I want to congratulate you because your great research and, again, my apologize.

Regards,

[Gijs Peek]

Alejandro Galvan wrote:I don't know if you are aware of the API, if you don't, check it, it is a good place to know the entire Java Application Program Interface, go to http://java.sun.com/javase/6/docs/api/, there, navigate to class java.lang.Object and you'll find the method hashCode and its explanaiton:

hashCode
public int hashCode()Returns a hash code value for the object. This method is supported for the benefit of hashtables such as those provided by java.util.Hashtable.
The general contract of hashCode is:

(...)As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)
(...)

As I have several years of java experience, I am aware of the API, and I still don't see any promises for hashcode uniqueness there, only a JVM implementation guideline for attempting to make them as distinct as reasonably practical.

Alejandro Galvan wrote:Also, I'm posting here the put method from the HashMap class (you can download the source code from the Sun Microsystems site)

I already read that, which is how I knew that the actual JVM implementation checks the hashcode before invoking the equals() method. The point I would like to stress is that since this behavior is not guaranteed, no assumptions can be made about this. This is why the answer is false.
I do understand, however, which answer is expected from me on the exam, and this is probably not the place to complain about invalid exam questions. So only one point remains: the answer to ch. 6 q. 4 states that distinct hashcodes will be put in distinct buckets. This should be modified - 2 distinct hashcodes could be mapped onto a single bucket - the chance is approximately 1 in <hashtable capacity>.

[Gijs Peek]

Alejandro Galvan wrote:As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)

Actually, Sun does acknowledge that this description can be considered misleading, read the bug report at http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6321873.