Detaillierte Einführung in die Java-Sammlungsklasse Hashmap (Codebeispiel)

Dieser Artikel bietet Ihnen eine detaillierte Einführung (Codebeispiel) über die Java-Sammlungsklasse Hashmap. Ich hoffe, dass er für Sie nützlich ist. hat geholfen.

1. Einführung in HashMap

HashMap ist eine Sammlungsklasse, die im Entwicklungsprozess von Programmierern sehr häufig verwendet wird,

In der Entwicklung können wir die Funktion nutzen, einen Schlüssel zu ersetzen, wenn er vorhanden ist, um einen aktualisierten Deduplizierungsvorgang zu implementieren.

Zur weiteren Zweckmäßigkeit können wir Map und FastJson verwenden, um schnell das benötigte JSON-Datenformat zu erstellen.

Vor jdk1.8 existierte HashMap in Form eines Arrays + einer verknüpften Liste. Der HashCode des Put-Schlüssels wurde durch die Störungsfunktion berechnet, um den Hash-Wert zu erhalten, und dann wurde der Wert durch (n-) berechnet. 1)&Hash an die entsprechende Position (n stellt die Länge des Arrays dar),

Wenn ein Hash-Konflikt auftritt, stellen Sie zunächst fest, ob der Schlüssel vorhanden ist, und überschreiben Sie ihn, falls vorhanden, andernfalls verwenden Sie die „Zipper-Methode“. " Um den Konflikt zu lösen, wird dann eine verknüpfte Liste erstellt.

Aber nach jdk1.8 hat sich HashMap geändert. Wenn die Länge der aktuellen verknüpften Liste größer als der Schwellenwert ist (der Standardwert ist 8), wird die verknüpfte Liste in einen rot-schwarzen Baum umgewandelt. Beschleunigung der Suche.

2. HashMap-Eigenschaften

//Die standardmäßige Anfangskapazität von HashMap beträgt 2^4=16
static final int DEFAULT_INITIAL_CAPACITY = 1 << // Die maximale Kapazität von HashMap

static final int MAXIMUM_CAPACITY = 1 << 30;

// Der Standardlastfaktor ist, wenn die Array-Länge

static final float DEFAULT_LOAD_FACTOR = 0.75f;

// Wenn die Anzahl der Knoten im Bucket größer als dieser Wert ist, wird er konvertiert in einen rot-schwarzen Baum

static final int TREEIFY_THRESHOLD = 8;

// Wenn die Anzahl der Knoten im Bucket unter diesem Wert liegt, wird der Baum in eine verknüpfte Liste umgewandelt

static final int UNTREEIFY_THRESHOLD = 6;

// Struktur im Bucket In die minimale Größe der Tabelle konvertieren, die dem rot-schwarzen Baum entspricht

static final int MIN_TREEIFY_CAPACITY = 64;

// Das Array zum Speichern der Elemente ist immer eine Potenz von 2

transient Node
//Speichersatz spezifischer Elemente

transient Set> enterSet;

//Speicheranzahl der Elemente. Beachten Sie, dass dies nicht der Länge des Arrays entspricht.

transient int size;

// Zähler für jede Erweiterung und Änderung der Kartenstruktur

transient int modCount;

// Der kritische Wert ist die tatsächliche Größe (Kapazität * Füllung Faktor) Wenn er den kritischen Wert überschreitet, wird er erweitert (*Wenn

größer oder gleich

ist, wird der Erweiterungsmechanismus nicht unbedingt ausgelöst, aber höchstwahrscheinlich wird er ausgelöst, solange er vorhanden ist ist ein neu erstellter size Hash. Wenn ein Konflikt auftritt, sofort threshold)Entry int limits;resize
// Füllfaktor Wenn Size>=threshold, muss die Erweiterung des Arrays berücksichtigt werden , das heißt, was das bedeutet Es ist ein Standard, um zu messen, ob das Array erweitert werden muss

final float loadFactor;

3 HashMap-Erweiterungsmechanismus

 public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

Der Code für tableSizeFor ist:

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

> ;>> ist ein Bit-Rechts-Verschiebungssymbol, das das Vorzeichenbit ignoriert |= ist eine &-Operation für die linken und rechten Zahlen

Diese Methode wird gedreht Die von Ihnen eingegebene Initialisierungskapazität wird in eine quadratische Potenz von 2 umgewandelt. Die Zahl ist daher hier festgelegt. Die Kapazität von HashMap muss die quadratische Potenz von 2 sein. Die Gründe sind wie folgt:

1.put-Methodenquellcode:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

Sehen Sie, dass p = tab[i = (n - 1) & hash]) == null Dieser Satz (n - 1) & Hash wird auf eine Position berechnet, wenn die Position auf dieser Registerkarte leer ist. Führen Sie dann den Einfügevorgang direkt aus.

Angenommen, es gibt 16 Stellen und 4 Studierende haben ihre eigenen Studierendennummern

此时我们分配位置的时候可以采用 1%16 = 1；2%16=2；3%16 = 3；4%16=4；给他们分配位置,但是考虑到性能问题。由于%操作比&慢10倍左右，因此采用&运算会提高性能。

通过限制length是一个2的幂数， (n - 1) & hash和hash%n结果是一致的。这就是为什么要限制容量必须是一个2的幂的原因。

比如2的hashCode是2 那么它对应的二进制是 （0000 0010）

假设n=16

那么n-1=15对应的二进制是 1111 1111 & 0000 0010 = 1111 1111 = 0010 = 2

2%16=2

得到(n - 1) & hash和hash%n结果是一致的,考虑到性能所以每次的扩容都是以2的幂次方扩容。

四.HashMap的简单应用

public  static void mapMethod() {
		HashMap<String, Object> map = new HashMap<>();
		map.put("zhangsan", 11);
		map.put("lisi", 11);
		//重复key会覆盖
		map.put("zhangsan", 22);
		//便利
		for(String key:map.keySet()) {
			//根据key获取value
			System.out.println(key+"=======value:"+map.get(key));
		}
		//containsKey方法判断当前map是否包含该方法
		System.out.println(map.containsKey("zhangsan"));
		//size打印map的长度
		System.out.println(map.size());
		//移除key
		map.remove("zhangsan");
		//判断是否存在value
		System.out.println(map.containsValue("22"));
	}

Das obige ist der detaillierte Inhalt vonDetaillierte Einführung in die Java-Sammlungsklasse Hashmap (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!