Невозможно понять часть Пуассона таблиц Хэша из документации Sun

Я пытаюсь понять, как HashMap реализован в Java. Я решил, что я попытаюсь понять каждую строку (кода и комментариев) из этого класса, и, очевидно, я столкнулся с сопротивлением очень скоро. Следующий фрагмент из класса HashMap и рассказывает о распределении Пуассона:

 Ideally, under random hashCodes, the frequency of
 nodes in bins follows a Poisson distribution
 (http://en.wikipedia.org/wiki/Poisson_distribution) with a
 parameter of about 0.5 on average for the default resizing
 threshold of 0.75, although with a large variance because of
 resizing granularity. Ignoring variance, the expected
 occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
 factorial(k)). The first values are:
 0:    0.60653066
 1:    0.30326533
 2:    0.07581633
 3:    0.01263606
 4:    0.00157952
 5:    0.00015795
 6:    0.00001316
 7:    0.00000094
 8:    0.00000006
 more: less than 1 in ten million

Я среднестатистический парень по математике и должен был понять, какое распределение Пуассона первое. Благодаря простому видео, которое объяснило мне это.

Теперь даже после понимания того, как вы вычисляете вероятность с помощью Пуассона, я не могу понять, что описано выше.

Может кто-нибудь объяснить это на более простом языке и с примером, если это возможно? Это сделает мою задачу намного интереснее.

Ответы

Ответ 1

A HashMap организован как массив "ведер" на основе хэш-кода вставленных элементов. Каждое ведро (по умолчанию) содержит связанный список элементов. У каждого ведра будет очень мало элементов (в идеале, не более одного), так что для нахождения определенного элемента требуется очень мало поиска по связанному списку.

Чтобы взять простой пример, скажем, у нас есть HashMap с емкостью 4 и коэффициент загрузки 0,75 (по умолчанию), что означает, что он может удерживать до 3 элементов до изменения размера. Идеальное распределение элементов в ведра будет выглядеть примерно так:

bucket | elements
-------+---------
     0 | Z
     1 | X
     2 |
     3 | Y

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

bucket | elements
-------+---------
     0 | 
     1 | Z -> X -> Y
     2 |
     3 |

Это произойдет, если все элементы произойдут с хэшем в одно и то же ведро, поэтому поиск элемента Y потребует прохождения по связанным спискам.

Это может показаться не очень важным, но если у вас есть HashMap с емкостью 10 000 элементов и в объединенном списке содержится 7500 элементов, поиск определенного элемента будет деградировать до линейного времени поиска - - это то, что пытается избежать HashMap.

Одна из проблем заключается в том, что хэш-код для распределения элементов в ведра определяется самими объектами, а реализация хеш-кода объектов не всегда очень хороша. Если hashCode не очень хорош, тогда элементы могут группироваться в определенных ведрах, а HashMap начнет плохо работать.

Комментарий от кода говорит о вероятности появления разных длин связанных списков в каждом ковше. Во-первых, предполагается, что хэш-коды распределены случайным образом - это не всегда так! - и я думаю, что он также предполагает, что количество элементов в HashMap составляет 50% от количества ведер. Согласно этим предположениям, согласно распределению Пуассона, 60,6% ведер будет пустым, 30,3% будут иметь один элемент, 7,5% будут иметь два элемента, 1,2% - три элемента и т.д.

Другими словами, учитывая эти (идеальные) предположения, связанные списки в каждом ведре обычно будут очень короткими.

В JDK 8 существует оптимизация для превращения связанного списка в дерево выше определенного порогового размера, так что по меньшей мере производительность ухудшается до O (log n) вместо O (n) в худшем случае. Вопрос в том, какое значение следует выбирать в качестве порога? Это то, о чем эта дискуссия. Текущее пороговое значение TREEIFY_THRESHOLD равно 8. Опять же, при этих идеальных предположениях ведро со связанным списком длины 8 будет иметь место только 0.000006% времени. Поэтому, если мы получим связанный список, который долгое время, что-то явно не идеально! Это может означать, например, что хранящиеся объекты имеют исключительно плохие хэш-коды, поэтому HashMap должен переключиться со связанного списка на дерево, чтобы избежать чрезмерной деградации производительности.

Ссылка на исходный файл с комментарием находится здесь:

http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/jdk8-b119/src/share/classes/java/util/HashMap.java

Ответ 2

Принятый ответ велик, но я просто хотел бы указать, почему разумно использовать распределение Пуассона, в частности, поскольку у меня был тот же самый вопрос при чтении этого фрагмента кода.

В случае, когда мы фиксируем количество элементов k, вставляемых в фиксированное число ковшей n, тогда количество элементов в фиксированном ковше должно следовать за Биномиальное распространение с k испытания и вероятность успеха 1 / n. Это довольно легко увидеть; если хэш случайный, то каждый элемент помещается в наш ведро с вероятностью 1 / n и есть элементы k.

Когда k велико, а среднее из Биномиального распределения мало, то хорошим приближением является Poisson Distribution с тем же средним значением. В этом случае среднее значение k / n, коэффициент загрузки хэш-таблицы. Принимая 0,5 для среднего, разумно, потому что таблица допускает коэффициент загрузки не более 0,75 до изменения размера, поэтому таблица будет использоваться много с коэффициентом нагрузки около 0,5.