Ist eine HashMap threadsicher für verschiedene Schlüssel?

Wenn ich zwei mehrere Threads habe, die auf eine HashMap zugreifen, aber garantieren, dass sie niemals gleichzeitig auf denselben Schlüssel zugreifen, könnte dies dann immer noch zu einer Racebedingung führen?

In @ dotsids Antwort sagt er Folgendes:

Wenn Sie eine HashMap auf irgendeine Weise ändern, ist Ihr Code einfach kaputt.

Er ist richtig. Eine HashMap, die ohne Synchronisation aktualisiert wird, wird auch dann unterbrochen, wenn die Threads disjunkte Schlüsselsätze verwenden. Hier sind einige der Dinge, die schief gehen können.

• Wenn ein Thread a ausführt, sieht ein putanderer Thread möglicherweise einen veralteten Wert für die Größe der Hashmap.

• Wenn ein Thread eine Aktion ausführt put, die eine Neuerstellung der Tabelle auslöst, sieht ein anderer Thread möglicherweise vorübergehende oder veraltete Versionen der Hashtable-Array-Referenz, ihrer Größe, ihres Inhalts oder der Hash-Ketten. Chaos kann entstehen.

• Wenn ein Thread ein putfür einen Schlüssel ausführt, der mit einem von einem anderen Thread verwendeten Schlüssel kollidiert, und der letztere Thread ein putfür seinen Schlüssel ausführt, sieht der letztere möglicherweise eine veraltete Kopie der Hash-Kettenreferenz. Chaos kann entstehen.

• Wenn ein Thread die Tabelle mit einem Schlüssel prüft, der mit einem der Schlüssel eines anderen Threads kollidiert, trifft er möglicherweise auf diesen Schlüssel in der Kette. Auf diesem Schlüssel wird equals aufgerufen. Wenn die Threads nicht synchronisiert sind, kann die equals-Methode in diesem Schlüssel auf einen veralteten Status stoßen.

Und wenn Sie zwei Threads gleichzeitig ausführen putoder removeanfordern, gibt es zahlreiche Möglichkeiten für Rennbedingungen.

Ich kann mir drei Lösungen vorstellen:

1. Verwenden Sie a ConcurrentHashMap.
2. Verwenden Sie eine reguläre, HashMapaber außen synchronisierte Funktion. zB mit primitiven Mutexen, LockObjekten usw.
3. Verwenden Sie HashMapfür jeden Thread einen anderen . Wenn die Threads wirklich einen disjunkten Satz von Schlüsseln haben, sollte es (aus algorithmischer Sicht) nicht erforderlich sein, dass sie eine einzelne Map gemeinsam nutzen. Wenn Ihre Algorithmen die Threads beinhalten, die die Schlüssel, Werte oder Einträge der Karte irgendwann iterieren, kann die Aufteilung der einzelnen Karte in mehrere Karten zu einer erheblichen Beschleunigung für diesen Teil der Verarbeitung führen.

Verwenden Sie einfach eine ConcurrentHashMap. Die ConcurrentHashMap verwendet mehrere Sperren, die eine Reihe von Hash-Buckets abdecken, um die Wahrscheinlichkeit zu verringern, dass eine Sperre angefochten wird. Der Erwerb einer unbestrittenen Sperre hat nur geringfügige Auswirkungen auf die Leistung.

Um Ihre ursprüngliche Frage zu beantworten: Laut Javadoc geht es Ihnen gut, solange sich die Struktur der Karte nicht ändert. Dies bedeutet, dass überhaupt keine Elemente entfernt und keine neuen Schlüssel hinzugefügt werden müssen, die noch nicht in der Karte enthalten sind. Das Ersetzen des mit vorhandenen Schlüsseln verknüpften Werts ist in Ordnung.

Wenn mehrere Threads gleichzeitig auf eine Hash-Map zugreifen und mindestens einer der Threads die Map strukturell ändert, muss sie extern synchronisiert werden. (Eine strukturelle Änderung ist eine Operation, die eine oder mehrere Zuordnungen hinzufügt oder löscht. Das bloße Ändern des Werts eines Schlüssels, den eine Instanz bereits enthält, ist keine strukturelle Änderung.)

Es gibt jedoch keine Garantie für die Sichtbarkeit. Sie müssen also bereit sein, gelegentlich das Abrufen veralteter Assoziationen zu akzeptieren.

Es kommt darauf an, was Sie unter "Zugriff" verstehen. Wenn Sie nur lesen, können Sie sogar dieselben Schlüssel lesen, solange die Sichtbarkeit der Daten gemäß den Regeln für " Vorheriges " garantiert ist. Dies bedeutet, dass HashMapsich nichts ändern sollte und alle Änderungen (anfängliche Konstruktionen) abgeschlossen sein sollten, bevor ein Leser mit dem Zugriff beginnt HashMap.

Wenn Sie a HashMapin irgendeiner Weise ändern , ist Ihr Code einfach kaputt. @ Stephen C bietet eine sehr gute Erklärung dafür.

BEARBEITEN: Wenn der erste Fall Ihre tatsächliche Situation ist, empfehle ich Ihnen Collections.unmodifiableMap(), um sicherzugehen, dass Ihre HashMap niemals geändert wird. Objekte, auf die verwiesen wird, HashMapsollten sich ebenfalls nicht ändern. Eine aggressive Verwendung von finalSchlüsselwörtern kann Ihnen also helfen.

Und wie @Lars Andren sagt, ConcurrentHashMapist es in den meisten Fällen die beste Wahl.

Das Ändern einer HashMap ohne ordnungsgemäße Synchronisierung von zwei Threads kann leicht zu einer Racebedingung führen.

• Wenn a put()zu einer Größenänderung der internen Tabelle führt, dauert dies einige Zeit und der andere Thread schreibt weiter in die alte Tabelle.
• Zwei put()für verschiedene Schlüssel führen zu einer Aktualisierung desselben Buckets, wenn die Hashcodes der Schlüssel modulo der Tabellengröße entsprechen. (Tatsächlich ist die Beziehung zwischen Hashcode und Bucket-Index komplizierter, es können jedoch immer noch Kollisionen auftreten.)