Механизм перекомпоновки OpenJDK - PullRequest
Новая
       8

Механизм перекомпоновки OpenJDK

18 голосов
/ 28 октября 2011

Нашел этот код на http://www.docjar.com/html/api/java/util/HashMap.java.html после поиска реализации HashMap. 

  264       static int hash(int h) {
  265           // This function ensures that hashCodes that differ only by
  266           // constant multiples at each bit position have a bounded
  267           // number of collisions (approximately 8 at default load factor).
  268           h ^= (h >>> 20) ^ (h >>> 12);
  269           return h ^ (h >>> 7) ^ (h >>> 4);
  270       }

Может кто-нибудь пролить свет на это? Комментарий говорит нам , почему этот код находится здесь, но я хотел бы понять, , как это улучшает неверное хеш-значение и , как это гарантирует, что позиции имеют ограниченное количество столкновений . Что означают эти магические числа ?

1 Ответ

22 голосов
/ 28 октября 2011

Для того, чтобы это имело какой-либо смысл, его необходимо объединить с пониманием того, как HashMap распределяет вещи по сегментам.Это тривиальная функция, с помощью которой выбирается индекс сегмента: 

static int indexFor(int h, int length) {
    return h & (length-1);
}

Итак, вы можете видеть, что при размере таблицы по умолчанию, равном 16, на самом деле только 4 младших значащих бита хеша действительно имеют значение для выделения сегментов!(16 - 1 = 15, что маскирует хеш на 1111b)

Это может быть плохой новостью, если ваша функция hashCode вернула: 

10101100110101010101111010111111

01111100010111011001111010111111

11000000010100000001111010111111
//etc etc etc

Такая хеш-функция вряд ли будет "плохо "любым способом, который виден его автору.Но если вы объедините это с тем, как карта распределяет сегменты, boom, MapFail (tm).

Если вы помните, что h - это 32-битное число, это не magic числасовсем.Он систематически записывает наиболее значимые биты числа вправо в младшие значащие биты.Цель состоит в том, чтобы «различия» в количестве, встречающемся где-либо «поперек», при просмотре в двоичном виде стали видны вниз в младших значащих битах.

Столкновения становятся ограниченными, поскольку число различных чисел, имеющих одинаковыесоответствующие LSB теперь значительно ограничены, потому что любые различия, которые встречаются где-либо в двоичном представлении, сжаты в биты, которые важны для сегментирования.

...