Пользователь
0,0
рейтинг
14 января 2013 в 13:08

Разработка → Откуда растут ноги у hashCode

Java*
Опять на собеседованиях по Java спрашивают про hashCode и equals? А кто из собеседующих сам ответит на вопрос, как вычисляется Object.hashCode() и System.identityHashCode()? Насколько дорог вызов этих методов? Как их можно ускорить в HotSpot JVM? Держу пари, едва ли кто даст правильный ответ. Разве что, кто прочитает эту статью.

Существует распространенное заблуждение, что Object.hashCode возвращает адрес объекта в памяти. Когда-то давно, наверное, так оно и было. Например, Dalvik VM до сих пор использует адрес объекта, сдвинутый на 3 бита вправо. Однако такая реализация неудачна: во-первых, последовательно выделяемые объекты будут иметь последовательные хеш-коды; во-вторых, сборщик мусора может передвигать объекты в памяти, меняя их адреса.

Так получилось, что на прошлой неделе я дважды столкнулся с темой вычисления хеш-кода, что и побудило меня написать заметку. Сначала попался на глаза крайне несправедливо заминусованный комментарий. Именно SSSurkv совершенно верно предположил, что для вычисления Object.hashCode используется генератор случайных чисел.
– Как так? – спросите вы. – Ведь хеш-код объекта должен оставаться постоянным в течение жизни приложения.

Все верно. Встроенный хеш-код генерируется лишь один раз для каждого объекта при первом вызове метода hashCode(), после чего сохраняется в заголовке объекта для последующих вызовов. Но для первого раза используется именно random! Убедитесь сами, заглянув в исходники OpenJDK (функция get_next_hash).

Вероятно, я бы забыл про этот случай, если бы на днях не столкнулся с реальной проблемой в реальном проекте. Профилируя приложение, среди горячих методов я неожиданно увидел IdentityHashMap.put(), который, на мой взгляд, реализован довольно эффективно. Узким местом оказался System.identityHashCode(), на который IdentityHashMap полагается. Причем медленным был только первый вызов identityHashCode на объекте. Второй и последующие вызовы, как мы теперь знаем, берут сохраненное значение из заголовка.

Но нет худа без добра. Дело в том, что в HotSpot можно выбирать реализацию Object.hashCode с помощью ключа командной строки -XX:hashCode=n (где n от 0 до 5).
  0 – Park-Miller RNG (по умолчанию)
  1 – f(адрес, глобальное_состояние)
  2 – константа 1
  3 – последовательный счетчик
  4 – адрес объекта
  5 – Thread-local Xorshift
Наиболее адекватным, на мой взгляд, является последний – он дает неплохое равномерное распределение, используя только битовые операции, и, что важно для конкурентных алгоритмов, не трогает глобальные переменные.
Так, всего лишь добавив ключ JVM -XX:hashCode=5, я магическим образом ускорил свой алгоритм на 30%! Почему этот вариант до сих пор не сделали дефолтным, остается загадкой…

Напоследок забавный факт: хотспотовский hashCode никогда не вернет 0, так как 0 считается признаком того, что хеш-код для данного объекта еще не генерировался:
if (value == 0) value = 0xBAD ;

Надеюсь, теперь, когда вы узнали всю правду о hashCode, вы сможете не только удивить коллег на собеседовании, но и сделать свои алгоритмы еще эффективнее.
Андрей @apangin
карма
144,5
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (39)

  • НЛО прилетело и опубликовало эту надпись здесь
    • НЛО прилетело и опубликовало эту надпись здесь
      • +2
        я смотрю, там понеслось :)

        На самом деле, сейчас самое время менять дефолтное поведение: в восьмёрке JCK, скорее всего, пропустит это изменение, а в 7uXX или 8uXX может быть чревато по причинам, описанным Дэвидом:
        This kind of switch can not be made lightly. It is not just a matter of raw performance, we have to understand how the change might affect existing applications. The default affects thousands of programs.


        Так что, имхо, сейчас самое время.
  • +2
    Можно ещё напомнить, что в hotspot вычисление identity hash code приводит к revoke bias, потому что в этом мире заголовке нет места для них обоих.
  • 0
    Дико извиняюсь, возможно неправильно понял но разве не должны два отдельных объекта которые equals возвращать одинаковый хашкод? Иначе как в хаштабах искать?
    • НЛО прилетело и опубликовало эту надпись здесь
      • +1
        прошу пардону
      • 0
        Но есть ньюанс:

        If two objects are equal according to the equals(Object) 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(java.lang.Object) 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 hashtables.


        docs.oracle.com/javase/1.4.2/docs/api/java/lang/Object.html#hashCode()
        • НЛО прилетело и опубликовало эту надпись здесь
          • 0
            Я специально процитировал, т.к. в изначальном вопросе не было уточнено, переопределены ли equals(). Ну и последнее предложение второй цитаты тоже достаточно интересно.
            • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          Так в том и фишка что " Два разных объекта (т.е. созданные разными new) будут всегда не равны по Object.equals". Соответственно раз они не равны то и хаши никому ничего не обязаны.
          • 0
            > However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hashtables.
          • –5
            Т.е. вы предполагаете что созданный объекты через «new» 2жды будет уметь разные хеши и equals на них вернет false?
            Для примера: Object o1 = new Object(«test») и Object o2 = new Object(«test»); из ваших слов будут иметь разные хеши.
            Так ли я вас понял?
            • –2
              > Для примера: Object o1 = new Object(«test») и Object o2 = new Object(«test»); из ваших слов будут иметь разные хеши.

              Зависит от Object. Если это нечто вроде Integer или String — то хэши будут одни, и equals() вернет true.
              А если нечто вроде org.eclipse.jetty.server.Server.Server(8080), то очевидно хэши будут разные.
            • 0
              А вообще, если, как мне сказали выше, речь идет о «В топике обсуждается Object.hashCode(), т.е. поведение базового хешкода, пришедшего из суперкласса Object.», то Object не принимает в конструктор аргументов.
  • 0
    Если хешкод генерится случайно во время первого вызова, то получается, что у двух разных объектов могут совпасть хешкоды (хоть и с малой вероятностью)?
    • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      Конечно. Хотя бы потому, что они ограничены объёмом int -1, раз 0 не годится за правильный хэшкод.
    • 0
      в оригинальном посте даже указан ключ когда все они будут константой :D насколько понимаю тут баланс между затратами на генерацию и затратами на дальнейший поиск по такому хэшу — если у многих объектов он совпадает то поиск будет дольше.
    • 0
      Если размер множества допустимых значений объектов класса больше 2 ** 32, то в любом случае будут совпадения хешей у разных объектов.
    • 0
      Они могут совпасть и из-за race condition, когда для двух объектов впервые вызывается hashCode из разных тредов почти одновременно:
      533 // This form uses an unguarded global Park-Miller RNG,
      534 // so it's possible for two threads to race and generate the same RNG.
  • +2
    Сначала попался на глаза крайне несправедливо заминусованный комментарий. Именно SSSurkv совершенно верно предположил, что для вычисления Object.hashCode используется генератор случайных чисел.

    Вообще в топике, к которому был тот комментарий, речь шла про Android, где, как вы сами же и написали, всё-таки используется адрес.

    И, кстати, всё-таки непонятно, чем плох вариант с адресом:
    1) То, что значения последовательные, не должно особо на что-то влиять, так как все реализации Map, которые я видел, не используют хэш напрямую, а вычисляют на его основе ещё один хэш — как раз, чтобы добиться равномерного распределения по бакетам.
    2) Какая разница, что адрес меняется, если, аналогично рандому, его можно считать только один раз?
    Единственное, что приходит в голову, это то, что если использовать адреса, то, видимо, множество возможных хэшей становится сильно ограниченным.

    И ещё мне интересно, а как реализуется, что хэш вычисляется только при первом обращении? Там, получается, блокировка должна быть?
    • 0
      И ещё мне интересно, а как реализуется, что хэш вычисляется только при первом обращении? Там, получается, блокировка должна быть?
      На сколько я понимаю из вышеприведённых исходников, там используются bias-locking (очень легковесный лок) и атомарная операция для присвоения нового хэша, если его нет. Если атомарная операция фейлится, используется более тяжелый лок.

      Спасибо автору поста, первый раз смотрю в сорцы JDK, интересно.
      • 0
        Блин, точно — не сообразил посмотреть, где используется get_next_hash.
        Спасибо :)
    • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    Поправьте меня, если я не права: рандом используется в jdk7, а в jdk6 это был всё же адрес, который сохранялся в заголовке так же как сохраняется рандом в jdk7?
    • НЛО прилетело и опубликовало эту надпись здесь
      • 0
        Удивительно, но официальный javadoc намекает, что это таки адрес в памяти, а так же многие гайды это говорят. Это, конечно, не существенно, но как-то обидно, когда javadoc врет, хоть и намеками, о поведении JDK от Oracle/SUN…
        • НЛО прилетело и опубликовало эту надпись здесь
          • +1
            Может это конечно и не верно с моей стороны, но я общаюсь только с Oracle JVM, и если у них в javadoc указано, что ТИПИЧНОЕ поведение вот такое, то я закономерно ожидаю его от Oracle JVM, потому что это как бы ТИПИЧНАЯ JVM.
            • НЛО прилетело и опубликовало эту надпись здесь
              • 0
                CR что ли зафайлить…
              • –2
                На самом деле, мне без разницы как считается hash code у Object, комментарий был не об этом, а о том, что некоторые вещи в яве не очевидны…
                • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    забавный факт: хотспотовский hashCode никогда не вернет 0

    А как же null?
    • 0
      Для null, очевидно, хеш-код не генерируется. Но System.identityHashCode(null) возвращает 0 — все верно.
  • 0
    Так, всего лишь добавив ключ JVM -XX:hashCode=5, я магическим образом ускорил свой алгоритм на 30%!


    Интересно, а какой use-case, что потребовался system hash code, а не штатный, скорее всего переопределённый?
    • 0
      Сериализация графа объектов.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.