Re: Duplicate hashcode for different Class objects

Yes, that's all correct.  That being said, different implementations  
of hashcode give better or worse performance.  There are issues of  
both the number of "significant bits" and the quality of the hash  
(which of course gets traded off against the cost of object creation  
or the first hash).

Grove, Fink, and I had a paper in ECOOP a few years ago about how to  
optimize hashing.  The basic idea is

- assume most objects are never hashed, so don't bother generating a  
hashcode on creation and just have two hashcode flag bits which are  
initially 0 (also enables header compression).

- if the object is hashed, use its address>>3 as the hashcode, and  
set a "hashed" bit in the object header.

- if the object is moved by the collector, set a "hashed and moved"  
bit in the header and copy the old hash to the end of the copy of the  
object.

This allows fast object creation and fairly high quality hash codes  
at the expense of complexity and a slightly more expensive hashCode()  
operation.  However, you have to be careful with a generational  
collector if the nursery is small.  One way around that would be to  
augment the hashcode with a generation number, at the expense of a  
couple of additional loads and adds in the hashCode() operation.

We implemented this in Jikes RVM and it was a major driver in  
modularizing the object model.  I don't know whether any of the  
specific code is still in there.

david


On Dec 13, 2008, at 9:27 AM, David Chase wrote:

> This is completely possible, especially when you have a copying  
> collector.
>
> First, hashcodes are not guaranteed to be unique.
>
> Second, the memory address is not necessarily the hashcode.  If  
> nothing else, there are non-random bits in object locations (an 8- 
> byte alignment guarantees the three least significant bits are  
> zero). It is quite reasonable to apply an extra bit of hashing to  
> the object; either using something invariant like the address/ 
> hashcode of the class, or storing a few extra bits in the header  
> word (say, the gc count, modulo 16) that get mixed into the  
> hashcode.  Or, the hashcode can be stored with the object itself.   
> That extra hashing can cause two different addresses to yield the  
> same hashcode.
>
> Third, in a copying collector, it is entirely likely that different  
> objects allocated at different times will get cycled through the  
> same youngspace, and the same address in the youngspace.  Thus,  
> their address would be the same.  If you can vary the size of the  
> youngspace, you might even be able to observe a change in the  
> frequency of these coincident hashcodes (if you did, that would  
> statistically confirm this hypothesis, if the frequency of  
> collision is somewhat inversely proportional to the size of the  
> youngspace).
>
> On 2008-12-13, at 5:11 AM, Unmesh joshi wrote:
>
>>
>> Hi,
>>
>> We are facing a strange problem in our application. getClass 
>> ().hashCode() is returning same hashcode for two different  
>> classes. My understanding is that default JDK implementation  
>> returns Object's memory address as hashCode. Can this duplication  
>> happen because of any GC implementation chosen? (like copying  
>> collection?). Is there any such bug already known?
>>
>> This problem is intermitent on Mac OS X machines and also observed  
>> on a linux box.
>>
>>
>> Thanks,
>> Unmesh
>> _________________________________________________________________
>> Wish to Marry Now? Join MSN Matrimony FREE!
>> http://in.msn.com/matrimony