codestory

Die Anleitung zu Java IdentityHashMap

  1. IdentityHashMap
  2. Wie arbeitet IdentityHashMap?
  3. Examples

1. IdentityHashMap

IdentityHashMap<K,V> ist eine Klasse im Java Collection Framework und implementiert die Interface Map<K,V>. IdentityHashMap unterstützt alle in der Interface Map angegebenen Funktionen vollständig, einschließlich optionaler Funktionen. Grundsätzlich ist IdentityHashMapHashMap sehr ähnlich, beide verwenden hashing technique, um den Datenzugriff und die Speicherleistung zu verbessern. Sie unterscheiden sich jedoch darin, wie Daten gespeichert und Schlüssel verglichen werden. IdentityHashMap verwendet den Operator == , um zwei Schlüssel zu vergleichen, während HashMap die Methode equals verwendet.
public class IdentityHashMap<K,V> extends AbstractMap<K,V>
                     implements Map<K,V>, java.io.Serializable, Cloneable
IdentityHashMap constructors:
IdentityHashMap()
Erstellt ein leeres Objekt IdentityHashMap mit der standardmäßig maximal erwarteten Größe (21).
IdentityHashMap(int expectedMaxSize)
Erstellt ein leeres Objekt IdentityHashMap mit der angegebenen maximalen erwarteten Größe. Das Hinzufügen von mehr als expectedMaxSize zu IdentityHashMap führt dazu, dass die interne Datenstruktur wächst, was etwas zeitaufwändig sein kann.
IdentityHashMap(Map<? extends K,? extends V> m)
Erstellt ein Objekt IdentityHashMap mit Mapping, die aus einer angegebenen Map kopiert wurden.

2. Wie arbeitet IdentityHashMap?

Genau wie HashMap verwendeten Designer Java die hashing technique für die Klasse IdentityHashMap, um den Datenzugriff und die Speicherleistung zu verbessern. Jetzt werden wir sehen, wie diese Technik in IdentityHashMap verwendet wird. Grundsätzlich analysieren wir, was passiert, wenn wir die Methoden IdentityHashMap.put(K,V), IdentityHashMap.get(K) và IdentityHashMap.remove(key) aufrufen.
IdentityHashMap verwaltet ein Array von Objekten (Object[] table), das bei Bedarf automatisch vergrößert werden kann. Und die Paare (key,value) werden an die Positionen (idx,idx+1) gespeichert.
Die Länge des internen Arrays wird basierend auf der maximal erwarteten Größe von IdentityHashMap wie im folgenden Beispiel berechnet:
InternalArrayLength_test.java
package org.o7planning.identityhashmap.ex;

public class InternalArrayLength_test {

    private static final int MINIMUM_CAPACITY = 4;

    private static final int MAXIMUM_CAPACITY = 1 << 29;

    private static int capacity(int expectedMaxSize) {
        // assert expectedMaxSize >= 0;
        return (expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY
                : (expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY
                        : Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
    }

    public static void main(String[] args) {
        for (int i = 1; i < 15; i++) {
            int mapSize = i * 25;

            int arrayLength = 2 * capacity(mapSize);
            System.out.printf("Map size: %3d --> Internal Array length: %d%n",mapSize, arrayLength);
        }
    }
}
Output:
Map size:  25 --> Internal Array length: 128
Map size:  50 --> Internal Array length: 256
Map size:  75 --> Internal Array length: 256
Map size: 100 --> Internal Array length: 512
Map size: 125 --> Internal Array length: 512
Map size: 150 --> Internal Array length: 512
Map size: 175 --> Internal Array length: 1024
Map size: 200 --> Internal Array length: 1024
Map size: 225 --> Internal Array length: 1024
Map size: 250 --> Internal Array length: 1024
Map size: 275 --> Internal Array length: 1024
Map size: 300 --> Internal Array length: 1024
Map size: 325 --> Internal Array length: 1024
Map size: 350 --> Internal Array length: 2048
IdentityHashMap.put(key,value):
Wenn die Methode IdentityHashMap.put(key,value) aufgerufen wird, berechnet IdentityHashMap die erwartete Position zum Speichern des Paares (notNullKey,value) im internen Array mithilfe der folgenden Formel:
private static int hash(Object x, int length) {
    int h = System.identityHashCode(x);
    // Multiply by -127, and left-shift to use least bit as part of hash
    return ((h << 1) - (h << 8)) & (length - 1);
}
// Return default not null Object if key is null.
private static Object maskNull(Object key) {
    return (key == null ? NULL_KEY : key);
}

final Object notNullKey = maskNull(key);
int len = table.length; // Length of Object[] table.
int idx = hash(notNullKey, len);
Das Paar (notNullKey,value) soll an die Position (idx,idx+1) des Arrays gespeichert werden. (Mit idx wird es nach obiger Formel berechnet).
  • Wenn table[idx]null ist, wird das Paar (notNullKey,value) an die Position (idx,idx+1) des Arrays gespeichert.
  • Im Gegensatz dazu, wenn table[idx]==notNullKeytrue ist, wird value an table[idx+1] zugewiesen.
  • Andernfalls wird die Mapping (notNullKey,value) in die Position (idx+2,idx+3), oder (idx+4,idx+5),.... gespeichert.
IdentityHashMap.get(key):
Wenn die Methode IdentityHashMap.get(key) aufgerufen wird, berechnet IdentityHashMap die erwartete Position, die die Mapping mit dem Schlüssel notNullKey auf dem internen Array mit derselben Formel gefunden hat:
private static int hash(Object x, int length) {
    int h = System.identityHashCode(x);
    // Multiply by -127, and left-shift to use least bit as part of hash
    return ((h << 1) - (h << 8)) & (length - 1);
}
// Return default not null Object if key is null.
private static Object maskNull(Object key) {
    return (key == null ? NULL_KEY : key);
}

final Object notNullKey = maskNull(key);
int len = table.length; // Length of Object[] table.
int idx = hash(notNullKey, len);
Es wird erwartet, dass die Mapping mit dem Schlüssel notNullKey am Index idx des Arrays gefunden wird. IdentityHashMap verwendet den Operator ==, um notNullKey und table[idx] zu vergleichen.
// true or false?
notNullKey == table[idx]
Wenn notNullKey == table[idx]true ist, gibt die Methode table[idx+1] zurück. Andernfalls wird notNullKey mit den nächsten Elementen an den Indizes idx+2, idx+4,... verglichen, bis ein passender Index gefunden wird oder das Ende des Arrays erreicht ist. Wenn sie nicht gefunden wird, gibt die Methode null zurück.
IdentityHashMap.remove(key):
Die Methode IdentityHashMap.remove(key) funktioniert ähnlich wie IdentityHashMap.get(key). Wenn Positionen (index,index+1) der zu entfernenden Zuordnungen gefunden werden, werden diese auf null aktualisiert.
table[index] = null;
table[index+1] = null;
Zum Schluss:
IdentityHashMap verwendet die statische Methode System.identityHashCode(key), um den hashcode des Schlüssels zu berechnen. Grundsätzlich gibt diese Methode eine Integer zurück, die sehr selten dupliziert wird. Die in IdentityHashMap verwendete Technik hilft, die Leistung beim Zugriff auf und beim Speichern von Daten zu verbessern. Reduzieren Sie die Verwendung des Operator == zum Vergleichen von Objekten.
Erfahren Sie mehr über hashing technique die in HashMap:

3. Examples

IdentityHashMapEx1.java
package org.o7planning.identityhashmap.ex;

import java.util.IdentityHashMap;

public class IdentityHashMapEx1 {

    public static void main(String[] args) {
        String key1 = "Tom";
        String key2 = new String("Tom");
        
        // key1 == key2 ? false
        System.out.println("key1 == key2 ? " + (key1== key2)); // false

        IdentityHashMap<String, String> map = new IdentityHashMap<String, String>();
        
        map.put(key1, "Value 1");
        map.put(key2, "Value 2");
        
        System.out.println("Map Size: " + map.size());
        
        System.out.println(map);
    }  
}
Output:
key1 == key2 ? false
Size: 2
{Tom=Value 1, Tom=Value 2}
Grundsätzlich enthalten alle Funktionen von IdentityHashMap die Spezifikation der Interface Map, außer dass es den Operator == verwendet, um Schlüssel zu vergleichen. Dies ist ein leichter Verstoß gegen die Spezifikation der Interface Map. (Erfordert die Methode equals zum Vergleichen von Schlüsseln).
Weitere Beispiele ansehen:

Die Anleitungen Java Collections Framework

Show More

Neueste Artikel

Show More