Является ли HashMap поточно-ориентированным для разных ключей?

Question

Если у меня есть несколько потоков, обращающихся к HashMap, но гарантирую, что они никогда не получат доступ к одному и тому же ключу в одно и то же время, может ли это привести к состоянию гонки?

Answer 1

В ответе @ доцида он говорит так:

Если вы каким-либо образом измените HashMap, ваш код просто сломается.

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

• Если один поток выполняет put, то другой поток может увидеть устаревшее значение для размера хэш-карты.

• Когда поток выполняет put, который запускает перестроение таблицы, другой поток может увидеть временные или устаревшие версии ссылки на массив хеш-таблиц, его размера, его содержимого или цепочек хеширования. Может наступить хаос.

• Когда поток выполняет put для ключа, который сталкивается с каким-либо ключом, используемым другим потоком, а последний поток делает put для своего ключа, тогда последний может увидеть устаревшую копию ссылка на хеш-цепочку. Может наступить хаос.

• Когда один поток исследует таблицу ключом, который сталкивается с одним из ключей другого потока, он может столкнуться с этим ключом в цепочке. Он будет вызывать equals для этого ключа, и если потоки не синхронизированы, метод equals может столкнуться с устаревшим состоянием в этом ключе.

И если два потока одновременно выполняют запросы put или remove, существует множество возможностей для условий гонки.

Я могу придумать три решения:

1. Используйте ConcurrentHashMap.
2. Используйте обычный HashMap, но синхронизируйте снаружи; например используя примитивные взаимные исключения, Lock объекты и так далее.
3. Используйте разные HashMap для каждого потока. Если потоки действительно имеют непересекающийся набор ключей, то им не нужно (с алгоритмической точки зрения) делить одну карту. Действительно, если в ваших алгоритмах используются потоки, повторяющие ключи, значения или записи карты в какой-то момент, разделение одной карты на несколько карт может значительно ускорить эту часть обработки.

Answer 2

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

1002 * Для того, чтобы ответить на ваш первоначальный вопрос:. В соответствии с Javadoc, до тех пор, пока структура карты не меняется, ваш прекрасны.Это означает, что вообще не нужно удалять элементы и добавлять новые ключи, которых еще нет на карте.Замена значения, связанного с существующими ключами, подойдет.

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

Хотя это не дает никаких гарантийо видимости.Таким образом, вы должны быть готовы иногда принимать устаревшие ассоциации.

Answer 3

Это зависит от того, что вы имеете в виду под «доступом». Если вы просто читаете, вы можете читать даже те же самые ключи, если видимость данных гарантирована правилами " произойдет до ". Это означает, что HashMap не должен изменяться, и все изменения (начальные конструкции) должны быть завершены до того, как любой читатель начнет доступ к HashMap.

Если вы измените HashMap каким-либо образом, то ваш код просто сломан. @Stephen C дает очень хорошее объяснение, почему.

РЕДАКТИРОВАТЬ: Если первый случай соответствует вашей реальной ситуации, я рекомендую вам использовать Collections.unmodifiableMap(), чтобы убедиться, что ваша HashMap никогда не изменяется. Объекты, на которые указывает HashMap, также не должны меняться, поэтому агрессивное использование ключевого слова final может помочь вам.

И, как говорит @Lars Andren, ConcurrentHashMap - лучший выбор в большинстве случаев.

Answer 4

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

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