Re: Duplicate hashcode for different Class objects

Yeah, it's not rocket science.  Works pretty well, though.  They key  
thing we were trying to do in that paper is get the Java object model  
down to a single word.  It really offends me that it costs more than  
32 bits in pretty much every JVM.

david


On Dec 13, 2008, at 1:37 PM, David Chase wrote:

> I heard about this trick on a Smalltalk (Squeak) mailing list, I am  
> pretty sure before Y2K.
> I think it could be old.
>
> On 2008-12-13, at 1:21 PM, David F. Bacon wrote:
>> 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.
>
>
> I would normally hope that people would pay the loads and adds.  As  
> some of your colleagues (Wegman, among them) will no doubt tell  
> you, hashcodes should be better than they usually are (they should  
> be "uniform").  People insist on taking penny-wise-pound-foolish  
> atheoretical shortcuts when defining hash functions, and they  
> should just plain know better.
>
> Except that some languages have baked-in definitions, hashcodes  
> should also not be predictable from run to run and (ahem) web  
> server to web server.  If I know that your server is sticking  
> strings into a Java hashtable, it's relatively easy for me to  
> pollute that table with collisions by sending you carefully  
> constructed strings that will hit the same hashcode (or that will  
> hit the same hashcode, modulo common hashtable sizes).
>
> David