«Сегодня я узнал, что такое Load Factor, и как обрабатываются конфликты в HashMap / HashSet, а в Java».

Привет! Это последний пост из моей серии «Хеширование». Приведенные ниже темы привлекли мое внимание больше всего. Надеюсь, тебе понравится!

  • Что такое коэффициент загрузки в структурах хеш-данных?
  • Что происходит внутри HashSet / HashMap, если происходит столкновение?

Что такое коэффициент загрузки в структурах хеш-данных?

Давайте определимся с некоторыми словами, которые мы собираемся использовать в этой части сообщения.

Сегмент. Сегмент - это то, что мы называем «позицией» в первом сообщении. Это слот, в который мы помещаем наш объект.
Вместимость - вместимость - это общее количество корзин, которое может иметь наша таблица.
Коэффициент загрузки - Коэффициент загрузки - это среднее количество элементов, хранящихся в одном ведре.

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

Если у нас есть все элементы, перечисленные в одной позиции / сегменте в нашей хеш-таблице, то нам не нужно много сегментов, однако время поиска становится линейным, что нам не нужно. Это все равно, что поставить 1.000 игр и положить их все на одну полку. Как бы вы нашли в этой кучке Age of Empires?

Если у нас есть таблица с большим количеством пустых позиций / корзин и заполняется только несколько из них, это снижает риск столкновения, однако это очень неэффективное использование пространства. Это все равно, что иметь всего 400 игр и арендовать здание, в котором можно хранить 90 000 игр.

Значение по умолчанию для коэффициента нагрузки установлено на 0,75. Если мы посмотрим на формулу для коэффициента загрузки:

loadFactor = (number of elements) / (number of buckets)

При превышении коэффициента загрузки хеш-таблица увеличивается, и все значения повторно хешируются.

Скажем, если бы у нас был коэффициент загрузки 0,75 и 75 элементов для хранения в нашей хеш-таблице, нам потребовалось бы как минимум 100 сегментов, мы можем сказать, что в среднем у нас есть 0,75 элементов в каждом сегменте, что равно нашему коэффициенту загрузки. Если мы хотим добавить еще один элемент в эту таблицу, теперь у нас есть 76 элементов, и среднее количество элементов на ведро теперь составляет 0,76 (76/100), что больше, чем коэффициент загрузки (0,75), поэтому таблица увеличивается (емкость увеличивается), и значения повторно хешируются.

Что мы подразумеваем под повторным хешированием?

Представьте, что у вас есть таблица с емкостью 16 (это значение по умолчанию).
С такой таблицей, если у вас есть два разных объекта (A, B), которые генерируют хешированные ключи hashed (A) = 15 и hashed (B) = 31.
Чтобы определить их позицию в массиве, вы берете их положительный мод, который был:

position = hashed mod n

Положение A - (15 mod 16) = 15, а положение B - (31 mod 16) = 15. Глядя на это, мы должны поместить оба этих элемента в 15-й индекс.
Давайте удвоим размер нашей таблицы и повторно хэшируем значения.
Теперь емкость нашей таблицы составляет 32.
Мы видим, что позиция A по-прежнему (15% 32) = 15 однако новая позиция для B (31% 32) = 31! Теперь мы можем поместить A в 15-й индекс, а B - в 31-й.
И это помогает нам свести к минимуму проблемы с коллизиями.

Что происходит внутри HashSet / HashMap, если происходит столкновение?

Поскольку HashSet использует внутри HashMap, нижеследующее применимо к обоим.

При извлечении элемента из HashMap с помощью ключа он создает хэш и переходит к индексу для этого хэша, проверяет, имеет ли первый узел ‹K, V› в этой позиции такой же hashedKey и тот же Key. Здесь сравнение ключей выполняется путем вызова equals () для данного ключа - вот почему важно переопределить hashCode () и equals () вместе. Если какое-либо из этих условий не соответствует действительности, HashMap переходит к следующему элементу по этому индексу.

Таким образом, мы можем сделать вывод, что HashMap сначала проверяет hashCode, если он равен, затем используйте метод equals.

При помещении элемента в HashMap, если результирующий индекс для данного ключа не пуст, значение этого индекса сравнивается с нашим текущим значением.
Сначала сравниваются их hashedKey, а затем вызывается equals. Если оба одинаковые, мы перезаписываем его.
Если это не совсем тот же объект, а другой объекты в этой позиции все еще находятся ниже уровня «TREEIFY_THRESHOLD», добавьте к следующему из последнего элемента. Если они хранятся в виде дерева, поместите его в правильное положение этого дерева.

Вывод

Хеширование - удивительная тема! Написание этих сообщений помогло мне многое узнать по теме, надеюсь, это поможет и вам.

Ура!