Что будет в HashMap, если мы добавим элемент во время перефразирования?

Question

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

А также, что такое использование дополнительного свободного места в hashmap, что составляет 25% от исходного размера карты, а коэффициент загрузки составляет 75%?

Answer 1

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

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

Этот вопрос имеет смысл, только если у вас есть два или более потоков, выполняющих операции на HashMap. Если вы делаете это, ваш код не является потокобезопасным. Его поведение не определено, спецификация версии c, и вы можете столкнуться с плохими вещами в непредсказуемое время. Такие вещи, как потерянные записи, необъяснимые NPE, даже если один из ваших потоков переходит в бесконечное l oop.

Вы не должны писать код, в котором два или более потока работают на HashMap без соответствующей внешней синхронизации с Избегайте одновременных операций. Если вы это сделаете, я не могу сказать вам, что произойдет.

Если у вас есть только один поток, использующий HashMap, то сценарий, который вас беспокоит, невозможен. Изменение размера происходит во время операции обновления.

Если у вас есть несколько потоков и выполняется синхронизация для предотвращения любых одновременных операций, то сценарий, который вас беспокоит, невозможен. Другой альтернативой является использование ConcurrentHashMap, который предназначен для правильной работы, когда несколько потоков могут одновременно краситься и писать. (Естественно, код для изменения размера ConcurrentHashMap намного сложнее. Но он гарантирует, что записи окажутся в нужном месте.)

Идет ли это на новую увеличенную карту или старую карту .

Если вы говорите о многопоточном несинхронизированном случае, ответ не определен и, возможно, указана версия c. (Я не проверял код.) В других случаях сценарий невозможен.

---

А также, как используется дополнительное свободное место в hashmap, что составляет 25% исходного размера карты, поскольку коэффициент загрузки составляет 75%?

Не используется. Если коэффициент загрузки составляет 75%, по крайней мере 25% слотов ha sh будут пустыми / никогда не будут использоваться. (Пока вы не достигнете точки, когда массив ha sh не может быть расширен в дальнейшем по архитектурным соображениям. Но вы редко достигнете этой точки.)

Это компромисс производительности. Инженеры Sun определили / оценили, что коэффициент загрузки 75% даст лучший компромисс между используемой памятью и временем, затрачиваемым на выполнение операций на HashMap. При увеличении коэффициента загрузки использование пространства становится лучше, но большинство операций на HashMap замедляются, поскольку увеличивается средняя длина цепи ha sh.

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

Answer 2

Изменение размера и многопоточность

Если вы обращаетесь к карте ha sh из одного потока, это не может произойти. Изменение размера запускается не таймером, а операцией, которая изменяет количество элементов в карте ha sh, например, она запускается операцией put () . Если вы позвоните put () и ha sh map увидит, что изменение размера необходимо, оно выполнит изменение размера, затем это будет ваш новый элемент. Означает, что новый элемент будет добавлен после изменения размера, ни один элемент не будет потерян, в любом из методов будет непоследовательное поведение.

Buf, если получить доступ к вашей карте ha sh из multiplic темы, то может быть много видов проблем. Например, если два потока вызывают put () одновременно, оба могут инициировать изменение размера. Одним из последствий может быть в том, что новый элемент одного из потоков будет потерян. Даже если изменение размера не требуется, многопоточность может привести к потере некоторых элементов. Например, два потока генерируют один и тот же индекс сегмента, и такого блока пока нет. Оба потока создают такой сегмент и добавляют его в массив блоков. Но самые последние выигрыши, другие будут отменены.

Ничто не указывает c на карту sh. Это типичная проблема, когда вы изменяете объект несколькими потоками. Чтобы правильно обрабатывать карты ha sh в многопоточной среде, вы можете либо реализовать синхронизацию, либо использовать класс, уже защищенный от потоков, ConcurrentHashMap .

Коэффициент загрузки

Элементы на карте ha sh хранятся в ведрах. Если каждый га sh соответствует одному индексу корзины, тогда время доступа составляет O (1) . Чем больше у вас хэшей, тем выше вероятность того, что два хэша выдают одинаковый индекс корзины. Затем они будут сохранены в том же контейнере, и время доступа увеличится на .

. Одним из решений для уменьшения таких коллизий является использование другой функции ha sh. Но 1) разработка функций ha sh, которые соответствуют определенным требованиям, может быть весьма нетривиальной задачей (помимо уменьшения коллизий, она должна обеспечивать приемлемую производительность), и 2) вы можете улучшить ha sh только в своих собственных классах, но не в библиотеках, которые вы используете.

Другое, более простое решение - использовать большее количество сегментов для того же количества хэшей. Когда вы уменьшаете соотношение (количество хэшей) / (количество сегментов) , вы уменьшаете вероятность коллизий и, таким образом, сохраняете время доступа близко к O (1) . Но цена в том, что вам нужно больше памяти. Например, для коэффициента загрузки 75% 25% массива сегментов не используются; при коэффициенте нагрузки 10% 90% не будут использоваться.

Не существует решения, подходящего для всех случаев. Попробуйте разные значения и измерьте производительность и использование памяти, а затем решите, что лучше в вашем случае.