Re: Duplicate hashcode for different Class objects

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