• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

S & B SCJP 6 - C7 - Q4 erratum

 
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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:



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 ]
 
Ranch Hand
Posts: 48
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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,
 
Gijs Peek
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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


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:


outputs "1999 in 2 attempts" on my machine.

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


which gives me:

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
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Sheriff
Posts: 9707
43
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Relax Gijs . The language of Alejandro might be harsh. But he was surely trying to help. So just relax
 
Gijs Peek
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 48
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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):


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
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic