Chi Tiết Mã Nguồn HashMap Trong Java

Bản Chất và Đặc Tính Của HashMap

HashMap là một trong những cấu trúc dữ liệu phổ biến nhất trong hệ thống Map của Java. Dưới đây là các đặc tính quan trọng của nó:

static final int DEFAULT_CAPACITY = 1 << 4;
static final int MAX_CAPACITY = 1 << 30;
static final float LOAD_FACTOR = 0.75f;
static final int TREE_THRESHOLD = 8;
static final int UNTREE_THRESHOLD = 6;
static final int MIN_TREE_SIZE = 64;
transient Node[] bucketArray;
transient Set> entrySet;
transient int count;
transient int modCount;
int threshold;
final float loadFactor;

Trong đó, bucketArray lưu trữ dữ liệu dưới dạng mảng của các node, mỗi node đại diện cho một cặp key-value.

Các Lớp Nội Bộ Của HashMap

HashMap định nghĩa nhiều lớp nội bộ, bao gồm lớp cơ bản như sau:

static class Element implements Map.Entry {
    final int hash;
    final K key;
    V value;
    Element next;
    Element(int hash, K key, V value, Element next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}
static final class TreeElement extends LinkedHashMap.Entry {
    TreeElement parent;
    TreeElement left;
    TreeElement right;
    TreeElement prev;
    boolean red;
    TreeElement(int hash, K key, V val, Element next) {
        super(hash, key, val, next);
    }
}

Lớp Element chứa các thuộc tính như hash, key, value và tham chiếu đến node tiếp theo. Lớp TreeElement kế thừa từ LinkedHashMap.Entry, bổ sung thêm các thuộc tính để quản lý cây đỏ-đen.

Khởi Tạo HashMap

Các phương thức khởi tạo của HashMap thiết lập các giá trị ban đầu cho các thuộc tính như sau:

public HashMap() {
    this.loadFactor = LOAD_FACTOR;
}

public HashMap(int initialCapacity) {
    this(initialCapacity, LOAD_FACTOR);
}

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Kích thước không hợp lệ: " + initialCapacity);
    if (initialCapacity > MAX_CAPACITY)
        initialCapacity = MAX_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Load factor không hợp lệ: " + loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

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 >= MAX_CAPACITY) ? MAX_CAPACITY : n + 1;
}

Phương thức tableSizeFor đảm bảo rằng kích thước của bảng luôn là lũy thừa của 2.

Phương Thức put()

Mã nguồn của phương thức put() như sau:

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

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node[] tab; Node p; int n, i;
    if ((tab = bucketArray) == 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 e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeElement)
            e = ((TreeElement)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 >= TREE_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++count > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

Quá trình chính của phương thức này là tính toán hash của key, xác định vị trí trong mảng và xử lý xung đột bằng cách sử dụng cấu trúc danh sách liên kết hoặc cây đỏ-đen.

Phương Thức resize()

Phương thức resize() thực hiện việc tăng kích thước của bảng khi cần thiết:

final Node[] resize() {
    Node[] oldTab = bucketArray;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAX_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } else if ((newCap = oldCap << 1) < MAX_CAPACITY &&
                   oldCap >= DEFAULT_CAPACITY)
            newThr = oldThr << 1;
    } else if (oldThr > 0)
        newCap = oldThr;
    else {
        newCap = DEFAULT_CAPACITY;
        newThr = (int)(LOAD_FACTOR * DEFAULT_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAX_CAPACITY && ft < (float)MAX_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node[] newTab = (Node[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeElement)
                    ((TreeElement)e).split(this, newTab, j, oldCap);
                else {
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        } else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

Phương thức này tạo ra một mảng mới có kích thước gấp đôi và di chuyển tất cả các phần tử từ mảng cũ sang mảng mới.

Thành phố Cuồng loạn