Механизм реинжиниринга OpenJDK

Нашел этот код 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

Чтобы он имел какой-то смысл, он должен сочетаться с пониманием того, как 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

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

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

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