38

I've often heard that these methods (Object.hashCode and System.identityHashCode) return the address of the object, or something computed quickly from the address; but I'm also pretty sure the garbage collector moves and compacts objects. Since the hash code cannot change, this presents a problem. I know this is not something one needs to know for everyday work, but I'd like to understand the internals. So, does anyone know how this is implemented in Java? Or .NET, since they are probably similar.

Rob N
  • 15,024
  • 17
  • 92
  • 165
  • 1
    Do you have a source of the article where it says GC might move objects? – Amir Raminfar Aug 26 '11 at 15:48
  • 2
    @Amir I'm pretty sure most JVM implementations implement garbage compaction, which *could* move an object in memory. – dlev Aug 26 '11 at 15:50
  • 1
    @Amir: There definitely are GCs that do this (see http://en.wikipedia.org/wiki/Garbage_collection_%28computer_science%29#Moving_vs._non-moving) and no language prescribes GC implementation details like that. Or, more pragmatically: Google will confirm that at least some JVMs use a generational GC, generational GC is by definition moving. Also see http://java.sun.com/docs/hotspot/gc1.4.2/faq.html, which explicitly states the young generations are managed by a copying (i.e. also moving) GC. –  Aug 26 '11 at 15:50
  • 3
    I don't think the "address" used by `hashCode()` is a physical memory address. In general, the GC can move objects around between young and tenured spaces without the application knowing... – Lukas Eder Aug 26 '11 at 15:52
  • @Amir Here is one article: http://www.ibm.com/developerworks/ibm/library/i-gctroub/ which I found after googling "java garbage collector compact". – Rob N Aug 26 '11 at 15:56

3 Answers3

27

.NET's implementation is intentionally not published (and when you attempt to decompile it, you will find that it makes an unmanaged framework call). The only documentation as such is here, which only states that it is "not guaranteed to produce a different value for each object", and "may change between framework versions". Making any assumptions about how it actually works is probably ill-advised.

Java's is more well-understood (though presumably could differ across JVMs), and is covered specifically in this question: Will .hashcode() return a different int due to compaction of tenure space?

The gist of the Java implementation is that by contract, the value of an object's hashcode is not relevant until it is retrieved for the first time. After that, it must remain constant. Thus the GC moving the object doesn't matter until the object's hashcode() method is called for the first time. After that, a cached value is used.

Community
  • 1
  • 1
Chris Shain
  • 50,833
  • 6
  • 93
  • 125
  • 1
    So I am curious to know. What does JVM do to all the references when it moves an object? Are they all just symbolic references? or does it need to update each reference to the new location? – Amir Raminfar Aug 26 '11 at 16:31
  • @AmirRaminfar - The short answer is that it updates all of the references, but there is some clever stuff to ensure that this can be done efficiently. The long answer is to buy / read a good textbook on Garbage Collection. – Stephen C Jul 04 '13 at 07:29
3

The identityHashCode does not change for an object. So any moving is done beneath that level.

A rudimentary implementation would have a logical address --> physical address mapping for every object.

More sophisticated implementations would only have the mapping at a page level, so perhaps the last 6 bits is the memory offset, and the rest are the page id. The indirection would happen at the page id --> actual page address level.

Dilum Ranatunga
  • 13,254
  • 3
  • 41
  • 52
1

In .net the getHash() method will be impacted by the GC and therefore its recommended that developers use their own hash implementations. I cant find the link to the internal implementation at them moment. I will post it later if I find it..

Found the link... This question was answered here

Community
  • 1
  • 1
Osama Javed
  • 1,432
  • 1
  • 16
  • 21