Các biến trong HashMap

HashMap sử dụng một mảng các "thùng" (buckets) để lưu trữ dữ liệu. Mỗi thùng có thể chứa một hoặc nhiều phần tử. Dưới đây là các biến quan trọng định nghĩa cấu trúc và hành vi của HashMap:

• DEFAULT_INITIAL_CAPACITY: Dung lượng ban đầu mặc định của mảng, luôn là lũy thừa của 2 (16).
• MAXIMUM_CAPACITY: Dung lượng tối đa mà HashMap có thể đạt được (2^30).
• DEFAULT_LOAD_FACTOR: Hệ số tải mặc định (0.75). Khi tỷ lệ phần tử trên dung lượng đạt 0.75, HashMap sẽ tự động mở rộng.
• TREEIFY_THRESHOLD: Ngưỡng để chuyển đổi một danh sách liên kết thành cây đỏ-đen (8).
• UNTREEIFY_THRESHOLD: Ngưỡng để chuyển đổi một cây đỏ-đen trở lại thành danh sách liên kết (6).
• MIN_TREEIFY_CAPACITY: Dung lượng tối thiểu của mảng để cho phép chuyển đổi sang cây (64).
• table: Mảng các thùng, nơi dữ liệu thực sự được lưu trữ.
• size: Số lượng cặp key-value thực tế trong HashMap.
• threshold: Ngưỡng dung lượng, khi size vượt qua ngưỡng này, HashMap sẽ được mở rộng.

Lớp Node

Mỗi phần tử trong HashMap được đóng gói trong một đối tượng Node:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // ... constructor và các phương thức khác
}

Phương thức put

Phương thức put được sử dụng để chèn một cặp key-value vào HashMap. Nó gọi đến phương thức trợ giúp putVal.

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

Phân tích phương thức putVal

Phương thức putVal xử lý logic cốt lõi của việc chèn phần tử:

1. Kiểm tra và khởi tạo mảng: Nếu mảng table chưa được khởi tạo, nó sẽ được tạo bằng cách gọi resize().
2. Tính chỉ số thùng: Chỉ số của thùng được xác định bằng cách thực hiện phép AND giữa giá trị băm (hash) và (n - 1), trong đó n là độ dài của mảng.
3. Xử lý các trường hợp:
   • Thùng trống: Nếu thùng tại chỉ số đã tính toán trống, một Node mới sẽ được tạo và đặt vào đó.
   • Key đã tồn tại: Nếu key của phần tử hiện tại trùng với key cần chèn, giá trị (value) sẽ được cập nhật.
   • Thùng chứa cây đỏ-đen: Nếu thùng chứa một cây, phương thức putTreeVal sẽ được gọi để chèn phần tử vào cây.
   • Thùng chứa danh sách liên kết: Nếu thùng chứa một danh sách liên kết, phương thức sẽ duyệt qua danh sách để tìm key. Nếu tìm thấy, giá trị sẽ được cập nhật. Nếu không, phần tử mới sẽ được thêm vào cuối danh sách. Nếu độ dài danh sách đạt đến TREEIFY_THRESHOLD, danh sách sẽ được chuyển đổi thành cây.
4. Kiểm tra ngưỡng mở rộng: Sau khi chèn, nếu số lượng phần tử (size) vượt quá ngưỡng (threshold), phương thức resize() sẽ được gọi để mở rộng mảng.

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // Khởi tạo mảng bucket và các biến tạm
    Node<K,V>[] bucketArray; Node<K,V> currentNode; int bucketSize, bucketIndex;
    
    // Nếu mảng chưa được khởi tạo, gọi resize để tạo
    if ((bucketArray = table) == null || (bucketSize = bucketArray.length) == 0)
        bucketSize = (bucketArray = resize()).length;

    // Tính chỉ số thùng và kiểm tra xem thùng có trống không
    if ((currentNode = bucketArray[bucketIndex = (bucketSize - 1) & hash]) == null)
        bucketArray[bucketIndex] = createNewNode(hash, key, value, null);
    else {
        Node<K,V> existingNode; K currentKey;
        // Nếu key trùng khớp, cập nhật giá trị
        if (currentNode.hash == hash &&
            ((currentKey = currentNode.key) == key || (key != null && key.equals(currentKey))))
            existingNode = currentNode;
        // Nếu thùng chứa cây, chèn vào cây
        else if (currentNode instanceof TreeNode)
            existingNode = ((TreeNode<K,V>)currentNode).putTreeVal(this, bucketArray, hash, key, value);
        else { // Nếu thùng chứa danh sách liên kết
            int chainLength = 0;
            for (Node<K,V> nextNode;; ++chainLength) {
                if ((nextNode = currentNode.next) == null) {
                    currentNode.next = createNewNode(hash, key, value, null);
                    // Nếu độ dài danh sách đạt ngưỡng, chuyển thành cây
                    if (chainLength >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(bucketArray, hash);
                    break;
                }
                if (nextNode.hash == hash &&
                    ((currentKey = nextNode.key) == key || (key != null && key.equals(currentKey)))) {
                    existingNode = nextNode;
                    break;
                }
                currentNode = nextNode;
            }
        }
        // Nếu key đã tồn tại, cập nhật giá trị và trả về giá trị cũ
        if (existingNode != null) {
            V oldValue = existingNode.value;
            if (!onlyIfAbsent || oldValue == null)
                existingNode.value = value;
            afterNodeAccess(existingNode);
            return oldValue;
        }
    }
    ++modCount;
    // Kiểm tra ngưỡng mở rộng và thực hiện nếu cần
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

Hàm băm (Hash Function)

Giá trị băm (hash) được tính bằng cách sử dụng một "hàm nhiễu" (perturbation function) để phân phối các phần tử một cách đồng đều hơn:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Phép toán ^ (h >>> 16) đảm bảo rằng cả các bit cao và bit thấp của giá trị hashCode đều ảnh hưởng đến kết quả cuối cùng, giúp giảm thiểu xung đột.

Phương thức resize

Phương thức resize được gọi khi số lượng phần tử trong HashMap vượt quá ngưỡng. Nó tạo ra một mảng mới với dung lượng gấp đôi và di chuyển tất cả các phần tử từ mảng cũ sang mảng mới.

final Node<K,V>[] resize() {
    Node<K,V>[] oldBuckets = table;
    int oldCapacity = (oldBuckets == null) ? 0 : oldBuckets.length;
    int oldThreshold = threshold;
    int newCapacity, newThreshold = 0;

    // Tính toán dung lượng và ngưỡng mới
    if (oldCapacity > 0) {
        if (oldCapacity >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldBuckets;
        }
        else if ((newCapacity = oldCapacity << 1) < MAXIMUM_CAPACITY &&
                 oldCapacity >= DEFAULT_INITIAL_CAPACITY)
            newThreshold = oldThreshold << 1; // Nhân đôi ngưỡng
    }
    else if (oldThreshold > 0)
        newCapacity = oldThreshold;
    else { // Sử dụng giá trị mặc định
        newCapacity = DEFAULT_INITIAL_CAPACITY;
        newThreshold = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    if (newThreshold == 0) {
        float ft = (float)newCapacity * loadFactor;
        newThreshold = (newCapacity < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                       (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThreshold;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newBuckets = (Node<K,V>[])new Node[newCapacity];
    table = newBuckets;

    // Di chuyển các phần tử từ mảng cũ sang mảng mới
    if (oldBuckets != null) {
        for (int i = 0; i < oldCapacity; ++i) {
            Node<K,V> node;
            if ((node = oldBuckets[i]) != null) {
                oldBuckets[i] = null;
                if (node.next == null)
                    newBuckets[node.hash & (newCapacity - 1)] = node;
                else if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).split(this, newBuckets, i, oldCapacity);
                else { // Di chuyển các danh sách liên kết
                    Node<K,V> lowChainHead = null, lowChainTail = null;
                    Node<K,V> highChainHead = null, highChainTail = null;
                    Node<K,V> nextNode;
                    do {
                        nextNode = node.next;
                        // Phân loại node vào hai danh sách dựa trên bit cao nhất của hash
                        if ((node.hash & oldCapacity) == 0) {
                            if (lowChainTail == null)
                                lowChainHead = node;
                            else
                                lowChainTail.next = node;
                            lowChainTail = node;
                        }
                        else {
                            if (highChainTail == null)
                                highChainHead = node;
                            else
                                highChainTail.next = node;
                            highChainTail = node;
                        }
                    } while ((node = nextNode) != null);
                    if (lowChainTail != null) {
                        lowChainTail.next = null;
                        newBuckets[i] = lowChainHead;
                    }
                    if (highChainTail != null) {
                        highChainTail.next = null;
                        newBuckets[i + oldCapacity] = highChainHead;
                    }
                }
            }
        }
    }
    return newBuckets;
}

Quá trình di chuyển các phần tử trong danh sách liên kết được tối ưu hóa bằng cách sử dụng phép toán (node.hash & oldCapacity). Vì dung lượng mới là bội số của 2, bit cao nhất của giá trị băm sẽ quyết định phần tử sẽ được đặt vào vị trí cũ (danh sách thấp) hay vị trí mới (danh sách cao) trong mảng, giúp giảm thiểu việc tính toán lại toàn bộ giá trị băm.