Re: Duplicate hashcode for different Class objects

David,

Isn't this the Agesen scheme?

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.477

Tony

David F. Bacon wrote:
> 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
>