How does the default hashCode() work?
In which scratching the surface of hashCode() leads to a speleology trip through the JVM source reaching object layout, biased locking, and surprising performance implications of relying on the default hashCode() .
Abundant thanks to Gil Tene and Duarte Nunes reviewing drafts of this article and their very valuable insights, suggestions and edits. Any remaining errors are my own.
A trivial mystery
Last week at work I submitted a trivial change to a class, an implementation of toString() so logs would be meaningful. To my surprise, the change caused a
5% coverage drop in the class. I knew that all new code was covered by existing unit tests so, what could be wrong? Comparing coverage reports a sharper colleague noticed that the implementation of hashCode() was covered before the change but not after. Of course, that made sense: the default toString() calls hashCode() :
After overriding toString() , our custom hashCode() was no longer being called. We were missing a test.
Everyone knew the default toString() but..
What is the default implementation of hashCode() ?
The value returned by the default implementation of hashCode() is called identity hash code so I will use this term from now on to distinguish it from the hash provided by overriden implementations of hashCode() . FYI: even if a class overrides hashCode() , you can always get the identity hash code of an object o by calling System.identityHashCode(o) .
Common wisdom is that the identity hash code uses the integer representation of the memory address. That’s also what the J2SE JavaDocs for Object.hashCode() imply:
Still, this seems problematic as the method contract requires that:
Given that the JVM will relocate objects (e.g. during garbage collection cycles due to promotion or compaction), after we calculate an object’s identity hash we must be able to retain it in a way that survives object relocation.
A possibility could be to take the current memory position of the object on the first call to hashCode() , and save it somewhere along with the object, like the object’s header. That way, if the object is moved to a different memory location, it would carry the original hash with it. A caveat of this method is that it won’t prevent two objects from having the same identity hash, but that’s allowed by the spec.
The best confirmation would be to to look at the source. Unfortunately, the default java.lang.Object::hashCode() is a native function:
Will the real hashCode() please stand up
Note that the identity hashCode() implementation is dependant on the JVM. Since I will only look at OpenJDK sources, you should assume this specific implementation whenever I talk about the JVM. All links refer to changeset 5820:87ee5ee27509 of the Hotspot tree, I assume that most of it will also be applicable to Oracle’s JVM, but things could (in fact, are) different in others (more about this later.)
OpenJDK defines entry points for hashCode() at src/share/vm/prims/jvm.h and src/share/vm/prims/jvm.cpp . The latter has:
ObjectSynchronizer::FastHashCode() is also called from identity_hash_value_for , which is used from a few other call sites (e.g.: System.identityHashCode() )
One might naively expect ObjectSynchronizer::FastHashCode() to do something like:
But it turns out to be a hundred line function that seems to be far more complicated. At least we can spot a couple of if-not-exists-generate blocks like:
Which seems to confirm our hypothesis. Let’s ignore that monitor for now, and be satisfied that it gives us the object header. It is kept at mark , a pointer to an instance of markOop, which represents the mark word that belongs in the low bits of the object header. So, tries to get a hash inside the mark word. If it’s not there, it’s generated using get_next_hash , saved, and returned.
The actual identity hash generation
As we saw, this happens at get_next_hash. This function offers six methods based on the value of some hashCode variable.
So what’s the default method? OpenJDK 8 seems to default on 5 according to globals.hpp:
OpenJDK 9 keeps the same default. Looking at previous versions, both OpenJDK 7 and OpenJDK 6 use the first method, a random number generator.
So, unless I’m looking at the wrong place the default hashCode implementation in OpenJDK has nothing to do with the memory address, at least since version 6.
Object headers and synchronization
Let’s go back a couple of points that we left unexamined. First, ObjectSynchronizer::FastHashCode() seems overly complex, needing over 100 lines to perform what we though was a trivial get-or-generate operation. Second, who is this monitor and why does it have our object’s header?
The structure of the mark word is a good place to start making progress. In OpenJDK, it looks like this
The format is slightly different on 32 and 64 bits. The latter has two variants depending on whether Compressed Object Pointers are enabled. Both Oracle and OpenJDK 8 do by default.
Object headers may thus relate to a free block or an actual object, in which case there are multiple possible states. In the simplest, (“normal object”) the identity hash is stored directly in the low addresses of the header.
But in other states, we find a pointer to a JavaThread or a PromotedObject . The plot thickens: if we put the identity hash in a “normal object”, will someone take it away? Where? If the object is biased, where can we get/set the hash? What is a biased object?
Let’s try to answer those questions.
Biased locking
Biased objects appear as a result of Biased Locking. A (patented!) feature enabled by default from HotSpot 6 that tries to alleviate the cost of locking objects. Such operations are expensive because their implementation often relies on atomic CPU instructions (CAS) in order to safely handle lock/unlock requests on the object from different threads. It was observed that in most applications, the majority of objects are only ever locked by one thread so paying the cost of the atomic operation was often a waste. To avoid it, JVMs with biased locking allow threads to try and “bias” an object towards themselves. While an object is biased, the lucky thread can lock/unlock the object without atomic instructions. As long as there are no threads contending for the same object, we’ll gain performance.
The biased_lock bit in the header indicates whether an object is biased by the thread pointed at by JavaThread* . The lock bits indicate whether the object is locked.
Precisely because OpenJDK’s implementation of biased locking requires writing a pointer in the mark word, it also needs to relocate the real mark word (which contains the identity hash.)
This could explain the additional complexity in FastHashCode . The header not only holds the identity hash code, but also locking state (like the pointer to the lock’s owner thread). So we need to consider all cases and find where the identity hash resides.
Let’s go read FastHashCode . The first thing we find is:
Wait. It just revoked existing biases, and disabled biased locking on the object (the false means “don’t attempt rebias”). A few lines down, this is indeed an invariant:
If I’m reading correctly, this means that simply asking for the identity hash code of an object will disable biased locking, which in turn forces any attempt to lock the object to use expensive atomic instructions. Even if there is only one thread.
Why does keeping biased locking state conflict with keeping the identity hash code?
To answer this question we must understand which are the possible locations of the mark word (that contains the identity hash) depending on the lock state of the object. The transitions are illustrated in this diagram from the HotSpot Wiki:
My (fallible) reasoning is the following.
For the 4 states at the top of the diagram, the OpenJDK will be able to use “thin” lock representations. In the simplest case (no locks) this means having the identity hash and other data directly in the object’s space for the mark word:
in more complex cases, it needs that space to keep a pointer to the “lock record”. The mark word will thus be “displaced” and put somewhere else.
While we have only one thread trying to lock the object, that pointer will actually refer to a memory location in the thread’s own stack. Which is twice good: it’s fast (no contention or coordination to access that memory location), and it suffices for the thread to identify that it owns the lock (because the memory location points to its own stack.)
But this won’t work in all cases. If we have contended objects (e.g. objects used on synchronized statements that many threads traverse) we will need a more complex structure that fits not only a copy of the object’s header (again, “displaced”), but also a list of waiters. A similar need for a list of waiters appears if a thread executes object.wait() .
This richer data structure is the ObjectMonitor, which is referred to as a the “heavyweight” monitor in the diagram. The value left in the object’s header doesn’t point to a “displaced mark word” anymore, but to an actual object (the monitor). Accessing the identity hash code will now require “inflating the monitor”: chasing a pointer to an object and reading/mutating whichever field contains the displaced mark word. Which is more expensive and requires coordination.
FastHashCode does have work to do.
Lines L640 to L680 deal with finding the header and checking for a cached identity hash. I believe these are a fast path that probe for cases that don’t need to inflate the monitor.
From L682 it needs to bite the bullet:
At this point, if the id. hash is there ( hash != 0 ), the JVM can return. Otherwise we’ll get one from get_next_hash and safely store it in the displaced header kept by the ObjectMonitor .
This seems to offer a reasonable explanation to why calling hashCode() on an object of a class that doesn’t override the default implementation makes the object ineligible for biased locking:
- In order to keep the identity hash of an object consistent after relocation we need to store the hash in the object’s header.
- Threads asking for the identity hash may not even care about locking the object, but in practise they will be sharing data structures used by the locking mechanism. This is a complex beast in itself that might be not only mutating, but also moving (displacing) the header contents.
- Biased locking helped perform lock/unlock operations without atomic operations, and this was effective as long as only one thread locked the object because we could keep the lock state in the mark word. I’m not 100% sure here, but I understand that since other threads may ask for the identity hash, even if there is a single thread interested in the lock, the header word will be contended and require atomic operations to be handled correctly. Which defeats the whole point of biased locking.
Recap
- The default hashCode() implementation (identity hash code) has nothing to do with the object’s memory address, at least in OpenJDK. In versions 6 and 7 it is a randomly generated number. In 8 and, for now, 9, it is a number based on the thread state. Here is a test that yields the same conclusion.
- Proving that “implementation-dependent” warns are not aesthetic: Azul’s Zingdoes generate the identity hash from the object’s memory address.
- Zing uses a different solution to keep it consistent despite object relocations, in which they delay storing the id. hash until the object relocates. At that point, it’s stored in a “pre-header”
- This implies that if you are synchronizing on objects that have no contention, you’d better override the default hashCode() implementation or you’ll miss out on JVM optimizations.
- This can be very useful. I’ve seen applications very heavy on contended producer/consumer queues where biased locking was causing more trouble than benefit, so we disabled the feature completely. Turns out, we could’ve done this only on specific objects/classes simply by calling System.identityHashCode() on them.
- Admittedly, I didn’t look much. Michael Rasmussenkindly pointed out that -XX:hashCode=2 can be used to change the default. Thanks!
Benchmarks
I wrote a simple JMH harness to verify those conclusions.
The benchmark (source) does something equivalent to this:
One configuration ( withIdHash ) synchronizes on an object that uses the identity hash, so we expect that biased locking will be disabled as soon as hashCode() is invoked. A second configuration ( withoutIdHash ) implements a custom hash code so biased locking should not be disabled. Each configuration is ran first with one thread, then with two threads (these have the suffix “Contended”.)
By the way, we must enable -XX:BiasedLockingStartupDelay=0 as otherwise the JVM will take 4s to trigger the optimisation distorting the results.
The first execution:
We can see that the using a custom hash code makes the lock/unlock loop work 4x faster than the one using the identity hash code (which disables biased locking.) When two threads contend for the lock, biased locking is disabled anyway so there is no significative difference between both hash methods.
A second run disables biased locking ( -XX:-UseBiasedLocking ) in all configurations.
The hash method no longer has any impact and withoutIdHash loses its advantage.
(All benchmarks were ran on a 2,7 GHz Intel Core i5.)
References
Whatever is not wild speculation and my weak reasoning trying to make sense of the JVM sources, comes from stitching together various sources about layout, biased locking, etc. The main ones are below:
To get notifications for new posts, subscribe to the RSS feed or follow me on Twitter. Here is the log of older posts.
Class Object
The actual result type is Class<? extends |X|> where |X| is the erasure of the static type of the expression on which getClass is called. For example, no cast is required in this code fragment:
Number n = 0;
Class<? extends Number> c = n.getClass();hashCode
- Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
- If two objects are equal according to the equals method, then calling the hashCode method on each of the two objects must produce the same integer result.
- It is not required that if two objects are unequal according to the equals method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.
equals
- It is reflexive: for any non-null reference value x , x.equals(x) should return true .
- It is symmetric: for any non-null reference values x and y , x.equals(y) should return true if and only if y.equals(x) returns true .
- It is transitive: for any non-null reference values x , y , and z , if x.equals(y) returns true and y.equals(z) returns true , then x.equals(z) should return true .
- It is consistent: for any non-null reference values x and y , multiple invocations of x.equals(y) consistently return true or consistently return false , provided no information used in equals comparisons on the objects is modified.
- For any non-null reference value x , x.equals(null) should return false .
An equivalence relation partitions the elements it operates on into equivalence classes; all the members of an equivalence class are equal to each other. Members of an equivalence class are substitutable for each other, at least for some purposes.
clone
By convention, the returned object should be obtained by calling super.clone . If a class and all of its superclasses (except Object ) obey this convention, it will be the case that x.clone().getClass() == x.getClass() .
By convention, the object returned by this method should be independent of this object (which is being cloned). To achieve this independence, it may be necessary to modify one or more fields of the object returned by super.clone before returning it. Typically, this means copying any mutable objects that comprise the internal «deep structure» of the object being cloned and replacing the references to these objects with references to the copies. If a class contains only primitive fields or references to immutable objects, then it is usually the case that no fields in the object returned by super.clone need to be modified.
The class Object does not itself implement the interface Cloneable , so calling the clone method on an object whose class is Object will result in throwing an exception at run time.
toString
notify
The awakened thread will not be able to proceed until the current thread relinquishes the lock on this object. The awakened thread will compete in the usual manner with any other threads that might be actively competing to synchronize on this object; for example, the awakened thread enjoys no reliable privilege or disadvantage in being the next thread to lock this object.
- By executing a synchronized instance method of that object.
- By executing the body of a synchronized statement that synchronizes on the object.
- For objects of type Class, by executing a static synchronized method of that class.
Only one thread at a time can own an object’s monitor.
notifyAll
The awakened threads will not be able to proceed until the current thread relinquishes the lock on this object. The awakened threads will compete in the usual manner with any other threads that might be actively competing to synchronize on this object; for example, the awakened threads enjoy no reliable privilege or disadvantage in being the next thread to lock this object.
This method should only be called by a thread that is the owner of this object’s monitor. See the notify method for a description of the ways in which a thread can become the owner of a monitor.
In all respects, this method behaves as if wait(0L, 0) had been called. See the specification of the wait(long, int) method for details.
In all respects, this method behaves as if wait(timeoutMillis, 0) had been called. See the specification of the wait(long, int) method for details.
The current thread must own this object’s monitor lock. See the notify method for a description of the ways in which a thread can become the owner of a monitor lock.
This method causes the current thread (referred to here as T ) to place itself in the wait set for this object and then to relinquish any and all synchronization claims on this object. Note that only the locks on this object are relinquished; any other objects on which the current thread may be synchronized remain locked while the thread waits.
- Some other thread invokes the notify method for this object and thread T happens to be arbitrarily chosen as the thread to be awakened.
- Some other thread invokes the notifyAll method for this object.
- Some other thread interrupts thread T .
- The specified amount of real time has elapsed, more or less. The amount of real time, in nanoseconds, is given by the expression 1000000 * timeoutMillis + nanos . If timeoutMillis and nanos are both zero, then real time is not taken into consideration and the thread waits until awakened by one of the other causes.
- Thread T is awakened spuriously. (See below.)
The thread T is then removed from the wait set for this object and re-enabled for thread scheduling. It competes in the usual manner with other threads for the right to synchronize on the object; once it has regained control of the object, all its synchronization claims on the object are restored to the status quo ante — that is, to the situation as of the time that the wait method was invoked. Thread T then returns from the invocation of the wait method. Thus, on return from the wait method, the synchronization state of the object and of thread T is exactly as it was when the wait method was invoked.
A thread can wake up without being notified, interrupted, or timing out, a so-called spurious wakeup. While this will rarely occur in practice, applications must guard against it by testing for the condition that should have caused the thread to be awakened, and continuing to wait if the condition is not satisfied. See the example below.
For more information on this topic, see section 14.2, «Condition Queues,» in Brian Goetz and others’ Java Concurrency in Practice (Addison-Wesley, 2006) or Item 81 in Joshua Bloch’s Effective Java, Third Edition (Addison-Wesley, 2018).
If the current thread is interrupted by any thread before or while it is waiting, then an InterruptedException is thrown. The interrupted status of the current thread is cleared when this exception is thrown. This exception is not thrown until the lock status of this object has been restored as described above.
finalize
Subclasses that override finalize to perform cleanup should use alternative cleanup mechanisms and remove the finalize method. Use Cleaner and PhantomReference as safer ways to release resources when an object becomes unreachable. Alternatively, add a close method to explicitly release resources, and implement AutoCloseable to enable use of the try -with-resources statement.
This method will remain in place until finalizers have been removed from most existing code.
When running in a Java virtual machine in which finalization has been disabled or removed, the garbage collector will never call finalize() . In a Java virtual machine in which finalization is enabled, the garbage collector might call finalize only after an indefinite delay.
The general contract of finalize is that it is invoked if and when the Java virtual machine has determined that there is no longer any means by which this object can be accessed by any thread that has not yet died, except as a result of an action taken by the finalization of some other object or class which is ready to be finalized. The finalize method may take any action, including making this object available again to other threads; the usual purpose of finalize , however, is to perform cleanup actions before the object is irrevocably discarded. For example, the finalize method for an object that represents an input/output connection might perform explicit I/O transactions to break the connection before the object is permanently discarded.
The finalize method of class Object performs no special action; it simply returns normally. Subclasses of Object may override this definition.
The Java programming language does not guarantee which thread will invoke the finalize method for any given object. It is guaranteed, however, that the thread that invokes finalize will not be holding any user-visible synchronization locks when finalize is invoked. If an uncaught exception is thrown by the finalize method, the exception is ignored and finalization of that object terminates.
After the finalize method has been invoked for an object, no further action is taken until the Java virtual machine has again determined that there is no longer any means by which this object can be accessed by any thread that has not yet died, including possible actions by other objects or classes which are ready to be finalized, at which point the object may be discarded.
The finalize method is never invoked more than once by a Java virtual machine for any given object.
Any exception thrown by the finalize method causes the finalization of this object to be halted, but is otherwise ignored.
A subclass should avoid overriding the finalize method unless the subclass embeds non-heap resources that must be cleaned up before the instance is collected. Finalizer invocations are not automatically chained, unlike constructors. If a subclass overrides finalize it must invoke the superclass finalizer explicitly. To guard against exceptions prematurely terminating the finalize chain, the subclass should use a try-finally block to ensure super.finalize() is always invoked. For example,
Report a bug or suggest an enhancement
For further API reference and developer documentation see the Java SE Documentation, which contains more detailed, developer-targeted descriptions with conceptual overviews, definitions of terms, workarounds, and working code examples. Other versions.
Java is a trademark or registered trademark of Oracle and/or its affiliates in the US and other countries.
Copyright © 1993, 2023, Oracle and/or its affiliates, 500 Oracle Parkway, Redwood Shores, CA 94065 USA.
All rights reserved. Use is subject to license terms and the documentation redistribution policy.Как работает hashCode() по умолчанию?
Недавно в рабочем проекте я внёс в класс тривиальное изменение: реализацию toString() , чтобы от логов была польза. К моему удивлению, это привело примерно к 5-процентному уменьшению покрытия (coverage drop) класса. Я знал, что весь новый код покрывался уже имевшимися модульными тестами, так в чём же дело? При анализе отчётов о покрытии мой коллега заметил, что реализация hashCode() покрывалась только до внесения изменений, а не после. Причина была понятна: по умолчанию toString() вызывает hashCode() :
После корректирования toString() наш кастомный hashCode() перестал вызываться. Мы пропустили тест.
Все знали, что собой представляет реализация по умолчанию toString() , но…
Чем является реализация по умолчанию hashCode()?
Реализация по умолчанию hashCode() возвращает значение, которое называется идентификационный хеш (identity hash code). Я и дальше буду использовать это значение, чтобы отличать его от хешей, генерируемых переопределёнными реализациями hashCode() . Для сведения: даже если класс переопределяет hashCode() , вы всегда можете получить идентификационный хеш объекта o с помощью вызова System.identityHashCode(o) .
Здравый смысл подсказывает, что идентификационный хеш использует целочисленное представление адреса памяти. Об этом свидетельствует документация J2SE на Object.hashCode():
. обычно реализуется с помощью конвертации внутреннего адреса объекта в целочисленное значение, но в Java эта методика не требуется.
Однако с этим связаны проблемы, поскольку контракт метода (method contract) требует:
При применении к одному и тому же объекту более одного раза в ходе выполнения Java-приложения метод hashCode должен в обязательном порядке возвращать одно и то же целочисленное значение.
Учитывая, что JVM будет перемещать объекты (например, при сборке мусора в ходе продвижения или уплотнения), после вычисления идентификационного хеша объекта мы должны сделать так, чтобы он как-то отслеживал местоположение самого объекта.
Например, можно взять текущую позицию объекта в памяти при первом вызове hashCode() и сохранить её где-нибудь, например в заголовке объекта. Тогда при перемещении объекта в другое место с ним переедет и исходный хеш. Недостаток способа: два объекта могут иметь одинаковый хеш, но это разрешено спецификацией.
Лучшим подтверждением будет посмотреть в исходный код. К сожалению, дефолтная java.lang.Object::hashCode() является нативной функцией:
Настоящий hashCode()
Обратите внимание, что идентификационная реализация hashCode() зависит от JVM. Я буду рассматривать только исходный код OpenJDK, помните об этом при каждом дальнейшем упоминании JVM. Все ссылки относятся к набору изменений 5934:87ee5ee27509 дерева Hotspot, и полагаю, что большинство из них применимы и к Oracle JVM, но в других машинах есть свои нюансы.
OpenJDK определяет входную точку hashCode() в src/share/vm/prims/jvm.h и src/share/vm/prims/jvm.cpp . Последняя содержит:
ObjectSynchronizer::FastHashCode() также вызывается из identity_hash_value_for , который используется и несколькими другими точками вызова (например, System.identityHashCode() )
Можно наивно ожидать, что ObjectSynchronizer::FastHashCode() делает что-то вроде:
Но оказывается, что там функция на сотню строк. А это куда сложнее. По крайней мере, мы можем отметить пару блоков «если-не-существует-то-генерировать»:
Это подтверждает нашу гипотезу. Пока что проигнорируем monitor и удовлетворимся получением заголовка объекта. Он хранится в mark , указателе на экземпляр markOop, который представляет слово mark, принадлежащее младшим битам заголовка объекта. Итак, попытаемся засунуть хеш в слово mark. Если он отсутствует, то сгенерируем с помощью get_next_hash , сохраним и вернём.
Реальное генерирование идентификационного хеша
Как мы уже видели, это делается в get_next_hash. Функция предлагает шесть методов на базе значения переменной hashCode .
0. Случайно сгенерированное число.
1. Функция адреса объекта в памяти.
2. Жёстко запрограммированное значение 1 (используется при тестировании на чувствительность (sensitivity testing)).
3. Последовательность.
4. Адрес объекта в памяти, приведённый к целочисленному значению.
5. Состояние потока, объединённое с xorshift (https://en.wikipedia.org/wiki/Xorshift)Какой метод используется по умолчанию? Согласно globals.hpp, в OpenJDK 8 это метод 5:
Так что, если я не ошибаюсь, как минимум с шестой версии реализация по умолчанию hashCode в OpenJDK не имеет ничего общего с адресом памяти.
Заголовки объектов и синхронизация
Вернёмся немного и рассмотрим пару пропущенных моментов. Во-первых, функция ObjectSynchronizer::FastHashCode() выглядит слишком сложной, в ней используется больше 100 строк кода для выполнения того, что мы считали тривиальной операцией «получить-или-сгенерировать». Во-вторых, что это вообще такое – monitor – и почему у него есть заголовки нашего объекта?
Структура слова mark — хорошее место для начала изысканий. В OpenJDK она выглядит так:
Для 32 и 64 битов формат несколько различается. Во втором случае могут быть два варианта, в зависимости от того, включены ли указатели сжатых объектов (Compressed Object Pointers). В Oracle и OpenJDK 8 по умолчанию они включены.
Таким образом, заголовки объектов могут относиться к свободному блоку или к реальному объекту, так что возможны несколько разных состояний. В простейшем случае («нормальный объект») идентификационный хеш сохраняется напрямую в младшие биты заголовка.
Но в других состояниях указатель связан с JavaThread или PromotedObject . Дело усложняется: если поместить идентификационный хеш в «нормальный объект», то извлечёт ли его кто-нибудь? И куда? Если объект привязан (biased), то куда мы можем поместить хеш? Что такое привязанный объект?
Попробуем ответить на все эти вопросы.
Привязанная блокировка (biased locking)
Привязанные объекты — это результат привязанной блокировки. Это запатентованный механизм, по умолчанию используемый начиная с HotSpot 6. Он пытается снизить стоимость блокирования объектов. Подобные операции дороги, поскольку ради безопасной обработки запросов блокировки/разблокировки объекта от разных потоков их реализации часто опираются на атомарные процессорные инструкции (сравнение с обменом). Но подмечено, что во многих реализациях большинство объектов когда-либо блокируются лишь одним потоком, так что использование атомарных операций зачастую расточительно. Чтобы этого избежать, JVM’ы с привязанной блокировкой позволяют потокам попытаться самостоятельно «привязать» объект. Когда потоку это удаётся, он может блокировать/разблокировать объект без использования атомарных инструкций. А раз у нас нет потоков, борющихся за один и тот же объект, то мы получаем прирост производительности.
Бит biased_lock в заголовке обозначает, привязан ли объект к потоку, указанному в JavaThread* . Биты lock обозначают, заблокирован ли объект.
В OpenJDK реализация привязанной блокировки требует прописывать указатель в слове mark, и в результате нужно также перемещать само слово mark (содержащее идентификационный хеш).
Это может объяснить повышенную сложность FastHashCode . Заголовок содержит не только идентификационный хеш, но и состояние блокировки (указатель на поток, установивший блокировку). Поэтому нам нужно рассмотреть все случаи и определить месторасположение идентификационного хеша.Начнём с FastHashCode . Первое, что мы обнаруживаем:
Погодите. Здесь просто отменяются привязка и привязанная блокировка объекта (метод false означает «не пытайся снова привязать»). Несколькими строками ниже это остаётся действительно неизменным:
Если я прочитал правильно, то простой запрос идентификационного хеша объекта отключает привязанную блокировку, что предотвратит любые попытки заблокировать объект для использования дорогих атомарных инструкций.
Почему сохранение состояния привязанной блокировки конфликтует с сохранением идентификационного хеша?
Для ответа на этот вопрос мы должны понять, где может находиться слово mark (содержащее идентификационный хеш) в зависимости от состояния блокировки объекта. Ниже показаны возможные переходы:
Моё (возможно, ошибочное) мнение таково.
Для четырёх состояний в верхней части схемы OpenJDK сможет использовать представления thin-блокировок. В простейшем случае (без блокировок) это означает хранение идентификационного хеша и других данных прямо в пространстве слова mark в объекте:
В более сложных случаях это пространство используется для хранения указателя на «запись о блокировке». Тогда слово mark будет «перемещено» в другое место.
Поскольку заблокировать объект у нас только пытается один поток, этот указатель фактически ссылается на область памяти в собственном стеке потока. Это хорошо по двум причинам:
- скорость (отсутствие разногласий или координации доступа к области памяти),
- этого достаточно, чтобы поток знал о том, что он владеет блокировкой (область памяти ссылается на его собственный стек).
Нашим нуждам удовлетворяет структура ObjectMonitor, которая на схеме называется «тяжёлый монитор». Оставшееся в заголовке объекта значение указывает не на «перемещённое слово mark», а на реальный объект (монитор). Теперь для доступа к идентификационному хешу требуется «получить монитор» (inflating the monitor): сделать указатель на объект и считывать/изменять в зависимости от поля, содержащего перемещённое слово mark. Это дороже и требует координации.
Есть работа и для FastHashCode .
В строках с L640 по L680 выполняется поиск заголовка и проверка на наличие закешированного идентификационного хеша. Я считаю, что это быстрый способ проверки случаев, когда нам не нужно получить монитор.
Начиная с L682 придётся стиснуть зубы:
Если тут есть id. hash ( hash != 0 ), то JVM может его вернуть. В противном случае мы можем получить его от get_next_hash и спокойно сохранить в перемещённом заголовке, который содержится в ObjectMonitor .
Это даёт разумное объяснение, почему вызов hashCode() применительно к объекту класса, который не переопределяет реализацию по умолчанию, делает объекты недоступными для привязанной блокировки:
- Чтобы сохранять консистентность идентификационного кеша после перемещения, нам нужно хранить хеш в заголовке объекта.
- Потоки, запрашивающие идентификационный хеш, могут вообще не заморачиваться блокировкой объекта. Но на практике они будут совместно использовать структуры данных, применяемые механизмом блокировки. Это очень сложная система, поскольку она может не только менять, но и перемещать содержимое заголовков.
- Привязанная блокировка помогает выполнять операции блокирования/разблокирования без использования атомарных операций. Это эффективно до тех пор, пока объект блокируется лишь одним потоком, потому что нам нужно хранить состояние блокировки в слове mark. Я не совсем уверен, но, как я понял, поскольку другие потоки могут запрашивать идентификационный хеш, даже если блокировка нужна лишь одному потоку, слово header будет конкурентным и для корректной обработки потребуется использовать атомарные операции. Что лишает смысла привязанную блокировку.
Промежуточные итоги
- Реализация по умолчанию hashCode() (идентификационного хеша) не имеет отношения к адресу памяти объекта, как минимум в OpenJDK. В версиях 6 и 7 это случайно генерируемое число. В версиях 8 и 9 это число, полученное на основании состояния потока. Здесь проведён тест, который привёл к такому же выводу.
- Доказательство предупреждений «зависит от реализации» не для эстетики: Azul’s Zingдействительно генерирует идентификационный хеш на основании адреса памяти объекта.
- В Zing для сохранения консистентности при перемещениях используется механизм задержки сохранения id.hash до тех пор, пока объект не переместится. В данном случае хеш хранится в «предзаголовке».
- Это означает, что при синхронизации объектов, не имеющих разногласий, вам лучше переопределить реализацию по умолчанию hashCode() , иначе вы не сможете воспользоваться оптимизациями JVM.
- Это очень полезная возможность. Мне встречались приложения, в которых очень часто возникают разногласия между очередями создания/потребления; привязанная блокировка больше мешала, чем помогала, так что приходилось её отключать. Мы делали это только для конкретных объектов/классов, просто вызывая применительно к ним System.identityHashCode().
Бенчмарки
Для проверки своих умозаключений я написал простой тест JMH.
Бенчмарк (исходник) делает нечто вроде этого:
Одна конфигурация ( withIdHash ) синхронизирует объект, который использует идентификационный хеш, так что можно ожидать, что привязанная блокировка будет отключена при вызове hashCode() . Вторая конфигурация ( withoutIdHash ) реализует кастомный хеш, при котором привязанная блокировка не отключается. Каждая конфигурация сначала прогоняется с одним потоком, затем с двумя (они получают суффикс Contended).
Кстати, необходимо включить -XX:BiasedLockingStartupDelay=0 , а иначе JVM понадобится четыре секунды на запуск оптимизации, что исказит результат.
Кастомный хеш в четыре раза ускоряет цикл блокировки/разблокировки по сравнению с идентификационным хешем (который отключает привязанную блокировку). Когда за блокировку конкурируют два потока, привязанная блокировка отключается в любом случае, так что между двумя методам хеширования не наблюдается значимой разницы.
При втором запуске привязанная блокировка отключается ( -XX:-UseBiasedLocking ) во всех конфигурациях.
Метод хеширования больше не влияет на результат, и withoutIdHash теряет своё преимущество.
Все бенчмарки прогонялись на Intel Core i5 2,7 ГГц.
Ссылки
Всё, что не является дикими спекуляциями и моими слабыми рассуждениями в попытке осмыслить исходные коды JVM, собрано из разных источников. Основные из них:
Name already in use
JBook / object / hashcode.md
- Go to file T
- Go to line L
- Copy path
- Copy permalink
- Open with Desktop
- View raw
- Copy raw contents Copy raw contents
Copy raw contents
Copy raw contents
Что такое hash ? Это некоторое число, генерируемое на основе объекта и описывающее его состояние. Это число вычисляется на основе hash -функции.
Метод int hashCode() является реализация hash -функции для Java -объекта. Возвращаемое число в Java считается hash -кодом объекта.Объявление метода выглядит так:
Возможно, вас напугала стрчока J9VMInternals.fastIdentityHashCode(this), но пока для простоты считайте, что эта реализация зависит от JVM .
В hash — таблицах или ассоциативных маассивах (их еще называют словари, мапы) важность hashCode -а нельзя недооценивать.
Представим, что у нас есть массив пар ключ-значение. Для поиска по ключу в таком массиве вам надо обойти весь массив, заглянуть в каждую ячейку и сравнить ключ. Долго? Долго!
А теперь вспомним, что хэш — это по сути метаинформация о состоянии объекта, некоторое число. И мы можем просто взять хэш, по нему понять в какой ячейке хранится искомая пара и просто взять ее оттуда, без перебора всего массива! Быстро? Гораздо быстрее, чем просто итерация по всему массиву!
Да, могут быть коллизии — ситуации, когда разным объектам будет сгенерирован одинаковый хэш, но решить коллизию можно через equals и это все еще быстрее, чем проходить весь массив.
По сути, главное преимущество в быстродействии ассоциативных массивов основано на работе с hashCode . Именно за счет хэша мы можем вставлять и получать данные за O(1) , то есть за время пропорциональное вычислению хэш-функции.
Если планируется использовать объекты в качестве ключа в ассоциативном массиве, то переопределять hashCode надо обязательно.
Еще раз посмотрим на метод:
Контракт hashCode предъявляет следующие требования к реализации:
- Если вызвать метод hashCode на одном и том же объекте, состояние которого не меняли, то будет возвращено одно и то же значение.
- Если два объекта равны, то вызов hashCode для каждого обязан давать один и тот же результат.
Равенство объектов проверяется через вызов метода equals.
Проще говоря, разный hash -код у двух объектов — это гарантия того, что объекты не равны, в то время как одинаковый hash -код не гарантирует равенства.
Cитуация, когда разные объекты имеют одинаковые hash -код, называется collision или коллизией.
Логично, что коллизии возможны, так как размер int ограничен, да и реализации хэш-функции могут быть далеко не идеальны.
Реализация метода hashCode по-умолчанию возвращает разные значения hash -кодов для разных объектов:
Что это за значения? По-умолчанию hashCode() возвращает значение, которое называется идентификационный хэш (identity hash code). В документации сказано:
This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the Java™ programming language.
Поэтому реализация зависит от JVM .
Более подробно об этом можно прочесть в разделе полезные ссылки.
Пока можете не акцентировать внимание на том, как реализована hash -функция по-умолчанию и запомнить, что для разных объетов будут всегда возвращены разные значения hash -кодов, не взирая на состояние объекта.
Исходя из описания контракта метода можно понять, что hashCode , наряду с equals , играет важную роль в сравнении объектов. По сути он показывает изменилось ли состояние объекта, которое мы используем в equals для сравнения.
Именно поэтому, если вы переопределяете equals , то вы обязаны переопределить hashCode .
Самый очевидный и самый плохой пример как можно переопределить hashCode — это всегда возвращать константу:
Для равных объектов такой метод вернет одно и то же число, что удовлетворяет спецификации. Но, делать так категорически не рекомендуется.
Во-первых, если состояние объекта с такой реализацией hashCode , будет изменено, то это никак не отразится на hashCode . Что уже наталкивает на мысль, что такая реализация не совсем верна.
Во-вторых, такая реализация гарантирует возникновение коллизий всегда. А значит, использовать такой подход — это лишить себя всех преимуществ, которые дает нам использование ассоциативных массивов.
Теперь, когда мы решили, что возвращать всегда одно и то же значение — это плохое решение, давайте поговорим о том, что нужно включать в рассчет hashCode .
Перво-наперво, необходимо исключить избыточные поля, которые не участвуют в equals .
Далее необходимо выбрать базу: число, которое будет основной вычисления hash -кода.
По историческим причинам обычно за базу берут число 31 . Кто-то говорит, что это взято из-за близости к числу 32 , т.е степени двойки 2^5 — 1 . Кто-то утверждает, что был проведен эксперимент и наиболее лучшей базой получились числа 31 и 33 , а 31 понравилось больше.
В целом, вы можете выбрать за базу что хотите, но обычно выбирают 31 . Многие IDE (например, IDEA ) генерят hashCode именно с такой базой.
Правила вычисления hashCode :
Присваиваем переменной result ненулевое значение — базу.
Далее для каждого значимого поля в объекте вычисляем hashCode , по следующим правилам:
Если поле boolean — (f ? 1 : 0)
Если поле byte , char , short или int — (int) f
Если поле long — (int)(f ^ (f >>> 32))
Если поле float , то Float.floatToIntBits(f);
Если поле double , то Double.doubleToLongBits(f) , а затем как с long .
Если поле это ссылка на другой объект, то рекурсивно вызовите hashCode()
Если поле null , то возвращаем 0 .
Если поле это массив, то обрабатываем так, как будто каждый элемент массива — это поле объекта.
После каждого обработанного поля объединяем его hashCode с текущим значением:
Пример приведем с помощью многострадального класса Person :
Также, с версии Java 8+ в классе java.util.Objects есть вспомогательные методы для генерации hashCode :
Использование hashCode в equals
Так как hashCode допускает возникновение коллизий, то использовать его в equals нет смысла. Методы идут в паре, но использование одного в другом не желательно и бесмыссленно.
hashCode призван облегчить поиск объектов в каких-то структурах, например, ассоциативных массивах. equals — это уже непосредственно про сравнение объектов.
Классы-обертки над примитивами
Помните, что типы-обертки, которые по размеру меньше или равны int , возвращают в качестве hashCode свое значение.
Так как Long превосходит int , то, разумеется, возвращать свое значение в качестве hashCode он не может. Вместо этого используется более сложный алгоритм, который работает с значением long (как в примере Person -а).
Помните, что хэш-код массива не зависит от хранимых в нем элементов, а присваивается при создании массива!
Решением является использовать статический метод для рассчета hashCode у массивов: Arrays.hashCode(. ) :
Хэш — это некоторое число, генерируемое на основе объекта и описывающее его состояние. Метод hashCode , наряду с equals , играет важную роль в сравнении объектов. По сути он показывает изменилось ли состояние объекта, которое мы используем в equals для сравнения.
Если планируется использовать объекты в качестве ключа в ассоциативном маассиве, то переопределять hashCode обязательно. Если в классе переопределяется equals , то обязательно надо переопределять hashCode и наоборот.
Эти методы всегда должны определяться парой!
Плохая реализация hash -функции даст вам большое количество коллизий, что сведет на нет все преимущества использования ассоциативных массивов.
Помните, что большинство IDE сейчас легко сгенерируют вам hashCode , чтобы вы не писали его вручную.
Также, существуют сторонние проекты, которые берут кодогенерацию на себя, например, проект lombok. Существуют и сторонние библиотеки, помогающие в вычислении hashCode , например apache commons.