Nehmen wir an, wir haben einen Code
%Vor%Also, meine Frage ist, warum nach der Größenänderung von hashMap (das, soweit ich verstehe, rehashing keys ), wir haben noch 2 Schlüssel in keySet statt 1 (da Schlüsselobjekt ist das gleiche für beide bestehenden KV-Paare)?
Also, meine Frage ist, warum nach der Größenanpassung von HashMap (das, soweit ich verstehe, beinhaltet, Schlüssel neu zu rehabilitieren)
Tatsächlich beinhaltet nicht das Wiederhashing von Schlüsseln - zumindest nicht im HashMap -Code, außer unter bestimmten Umständen (siehe unten). Sie müssen sie in den Map-Buckets neu positionieren. Innerhalb von HashMap ist eine Entry -Klasse, die die folgenden Felder enthält:
Das Feld hash ist der gespeicherte Hashcode für den Schlüssel, der beim Aufruf von put(...) berechnet wird. Wenn Sie den Hashcode in Ihrem Objekt ändern, wirkt sich dies nicht auf den Eintrag in der HashMap aus, es sei denn, Sie fügen ihn in die Map ein. Natürlich, wenn Sie den Hashcode für einen Schlüssel ändern, werden Sie nicht einmal in der HashMap finden finden, weil er einen anderen Hashcode als den gespeicherten Hash-Eintrag hat.
Wir haben immer noch 2 Schlüssel in keySet statt 1 (da das Schlüsselobjekt für beide vorhandenen KV-Paare gleich ist)?
Auch wenn Sie den Hash für das einzelne Objekt geändert haben, befindet es sich in der Map mit zwei Einträgen mit unterschiedlichen Hashfeldern.
Alles, was gesagt wurde, es gibt Code innerhalb von HashMap , der darf die Schlüssel erneut aufschlüsselt, wenn die Größe einer HashMap geändert wird - siehe die geschützte Paket HashMap.transfer(...) -Methode in jdk 7 (zumindest). Aus diesem Grund ist das obige Feld hash nicht final . Es wird jedoch nur verwendet, wenn initHashSeedAsNeeded(...) wahr zurückgibt, um "alternatives Hashing" zu verwenden. Im Folgenden wird der Schwellenwert für die Anzahl der Einträge festgelegt, bei denen das Alt-Hashing aktiviert ist:
Mit dieser Einstellung auf der VM bin ich tatsächlich in der Lage, den hashcode() erneut aufzurufen, wenn die Größenanpassung stattfindet, aber ich kann den 2. put(...) nicht als Überschreiben sehen. Ein Teil des Problems ist, dass die HashMap.hash(...) -Methode eine XOR-Operation mit der internen hashseed ausführt, die bei der Größenänderung geändert wird, aber nachdem die put(...) den neuen Hash-Code für den eingehenden Datensatz aufzeichnet Eintrag.
Die HashMap speichert den Hash-Code für jeden Schlüssel (da der Hash-Code eines Schlüssels in der Berechnung teuer sein kann). Obwohl Sie den hashCode für einen vorhandenen Schlüssel geändert haben, hat der Eintrag, mit dem er in der HashMap verknüpft ist, immer noch den alten Code (und wird nach der Größenänderung in den "falschen" Bucket verschoben).
Sie können dies selbst im jvm-Code für HashMap.resize () (oder etwas einfacher im Code von Java 6 zu sehen HashMap.transfer () ).
Ich kann nicht sagen, warum zwei der Antworten für ein Beispiel auf HashMap.tranfer angewiesen sind, wenn diese Methode überhaupt nicht in Java-8 vorhanden ist. Als solche werde ich meine kleine Eingabe unter Berücksichtigung von Java-8 bereitstellen.
Einträge in einem HashMap werden zwar neu bewertet, aber nicht in dem Sinne, wie Sie vielleicht denken. Ein Re-Hash berechnet im Grunde das bereits von Ihnen bereitgestellte Key#hashcode ; Dafür gibt es eine Methode:
Wenn Sie also Ihren Hashcode berechnen, sagt HashMap im Grunde: "Ich traue Ihnen nicht genug" und es wird Ihren Hashcode erneut hashen und die Bits möglicherweise besser verteilen (das ist es tatsächlich ein XOR der ersten 16 Bits und der letzten 16 Bits).
Andererseits, wenn HashMap re-sized ist, bedeutet dies tatsächlich, dass die Anzahl der Bins / Buckets verdoppelt wird; und weil Bins immer sind, eine Potenz von Zwei - das bedeutet, dass ein Eintrag aus einem aktuellen Bin: Potential im selben Bucket bleibt OR in einen Bucket verschieben, der sich im Offset bei der aktuellen Anzahl von Bins. Sie können ein paar Details darüber finden, wie dies in dieser Frage gemacht wird.
Sobald also eine neue Größe auftritt, gibt es kein zusätzliches Re-Hash. tatsächlich wird ein weiteres Bit in Betracht gezogen und somit könnte sich ein Eintrag bewegen oder dort bleiben, wo er ist. Und Grays Antwort ist in diesem Sinne korrekt, dass jedes Entry das hash -Feld hat, das nur einmal berechnet wird - das erste Mal, wenn Sie dieses Entry setzen.
Ich kann es nicht eindeutig finden, aber das Ändern eines Schlüsselwerts in einer Weise, die seine hashCode() ändert, bricht normalerweise HashMap .
HashMap teilt Einträge zwischen b-Buckets. Sie können sich vorstellen, dass der Schlüssel mit dem Hash h dem Bucket h%b zugewiesen wird.
Wenn er einen neuen Eintrag erhält, ermittelt er, zu welchem Bucket er gehört, wenn in diesem Bucket bereits ein gleicher Schlüssel existiert. Es fügt es schließlich dem Bucket hinzu und entfernt alle passenden Schlüssel.
Durch Ändern des Hash-Codes wird das Objekt wrongHashCode (normalerweise und hier tatsächlich) zum zweiten Mal auf einen anderen Bucket gelenkt und sein erster Eintrag wird nicht gefunden oder entfernt.
Kurz gesagt, wenn Sie den Hashwert eines bereits eingefügten Schlüssels ändern, bricht HashMap ab, und was Sie danach erhalten, ist unvorhersehbar, kann aber dazu führen, dass (a) kein Schlüssel gefunden wird oder (b) zwei oder mehr gleiche Schlüssel gefunden werden / p>
Weil HashMap die Elemente in einer internen Tabelle speichert und die Inkrementierung des Codes diese Tabelle nicht beeinflusst:
%Vor% Und addEntry
Wie Sie table[bucketIndex] = new Entry (hash, ...) sehen können, obwohl Sie den Code inkrementieren, wird er hier nicht angezeigt.
Versuchen Sie, den Feldcode zu Integer zu machen und zu sehen, was passiert?