Space and time‐efficient hashing of garbage‐collected objects
Ole Agesen · Theory and Practice of Object Systems · 1999
The hashCode() method found in the JavaTM programming language, and similar methods in other languages, map an arbitrary object to an integer value that is constant for the lifetime of the object. We review existing implementations of the hash operation, specifying the kinds of memory systems for which they work. Then we propose a new implementation of hashing for the hardest case: memory systems with compaction and direct pointers. Our proposal uses just two bits of space per object for the (majority of) objects that are never hashed. © 1999 John Wiley & Sons, Inc.