Действительно ли HashMap ориентирован на многопотоковое исполнение для различных ключей?
Если я имею два несколько потоков, получающих доступ к HashMap, но гарантирую, что они никогда не будут получать доступ к тому же ключу одновременно, который мог все еще привести к состоянию состязания?
4 ответа
В ответе @dotsid он говорит следующее:
Если вы каким-либо образом измените HashMap, ваш код просто сломается.
Он прав. HashMap, который обновляется без синхронизации, нарушит даже , если потоки используют непересекающиеся наборы ключей. Вот некоторые из вещей, которые могут пойти не так.
Если один поток выполняет
put, то другой поток может увидеть устаревшее значение размера хэш-карты.Когда поток выполняет
put, который запускает перестройку таблицы, другой поток может видеть временные или устаревшие версии ссылки на массив хэш-таблицы, ее размер, ее содержимое или цепочки хеш-кодов. Может возникнуть хаос.Когда поток выполняет
putдля ключа, который конфликтует с некоторым ключом, используемым другим потоком, а последний поток выполняетputдля своего ключа, то последний может увидеть устаревшую копию ссылки на цепочку хэшей. Может возникнуть хаос.Когда один поток исследует таблицу с ключом, который сталкивается с одним из ключей другого потока, он может встретить этот ключ в цепочке. Он вызовет equals для этого ключа, и если потоки не синхронизированы, метод equals может столкнуться с устаревшим состоянием в этом ключе.
И если у вас есть два потока, одновременно выполняющих запросы put или remove , существует множество возможностей для состояний гонки.
Я могу придумать три решения:
- Используйте
ConcurrentHashMap. - Используйте обычную
HashMap, но выполняйте синхронизацию снаружи; например с использованием примитивных мьютексов,Lockобъектов и т. д. - Используйте разные
HashMapдля каждого потока. Если потоки действительно имеют непересекающийся набор ключей, тогда не должно быть необходимости (с алгоритмической точки зрения) для них совместно использовать одну карту. Действительно, если ваши алгоритмы включают потоки, повторяющие ключи, значения или записи карты в какой-то момент, разделение одной карты на несколько карт может дать значительное ускорение для этой части обработки.
Это зависит от того, что вы имеете в виду под "доступом". Если вы просто читаете, вы можете читать даже те же ключи при условии, что видимость данных гарантируется в соответствии с правилами « происходит до ». Это означает, что HashMap не должен изменяться, и все изменения (начальные конструкции) должны быть завершены до того, как любой читатель начнет доступ к HashMap .
Если вы каким-либо образом измените HashMap , то ваш код просто сломается. @Stephen C дает очень хорошее объяснение, почему.
РЕДАКТИРОВАТЬ: Если первый случай - это ваша реальная ситуация, я рекомендую вам использовать Collections.unmodifiableMap () , чтобы быть уверенным, что ваш HashMap никогда не изменяется. Объекты, на которые указывает HashMap , также не должны изменяться, поэтому агрессивное использование ключевого слова final может вам помочь.
И, как говорит @Lars Andren, ConcurrentHashMap - лучший выбор в большинстве случаев.
Изменение HashMap без надлежащей синхронизации из двух потоков может легко привести к состоянию гонки.
- Когда
put ()приводит к изменению размера внутренней таблицы, это занимает некоторое время, и другой поток продолжает запись в старую таблицу. - Два
put ()для разных ключей приводят к обновлению одного и того же блока, если хэш-коды ключей равны по модулю размера таблицы. (На самом деле связь между хэш-кодом и индексом корзины более сложная, но коллизии все же могут возникать.)
Просто используйте ConcurrentHashMap. ConcurrentHashMap использует несколько блокировок, которые охватывают диапазон хэш-сегментов, чтобы снизить вероятность оспаривания блокировки. Получение неоспоримой блокировки оказывает незначительное влияние на производительность.
Чтобы ответить на ваш исходный вопрос: согласно javadoc, пока структура карты не меняется, с вами все в порядке. Это означает, что вообще не нужно удалять элементы и не добавлять новые ключи, которых еще нет на карте. Заменить значение, связанное с существующими ключами, можно.
Если несколько потоков обращаются к хэш-карте одновременно, и хотя бы один из потоков структурно модифицирует карту, она должна быть синхронизирована извне. (Структурная модификация - это любая операция, которая добавляет или удаляет одно или несколько сопоставлений; простое изменение значения, связанного с ключом, который уже содержится в экземпляре, не является структурной модификацией.)
Хотя это не дает никаких гарантий относительно видимости. Поэтому вы должны быть готовы время от времени получать устаревшие ассоциации.