Cấu trúc Package java.util chia Collection thành hai nhánh chính: Collection và Map. Trong khi Collection chứa các phần tử đơn độc, Map lưu trữ dữ liệu dưới dạng cặp khóa-giá trị (key-value). Mỗi khóa trong Map là duy nhất, không phép trùng lặp; ngược lại, các giá trị có thể trùng nhau.

Hình 1: Mối quan hệ giữa các lớp và giao diện trong hệ thống Map

Giao diện Map và các phương thức(cơ bản)

Giao diện顶层 Map<K, V> định nghĩa toàn bộ các thao tác truy xuất và thao tác dữ liệu:

public interface Map<K, V> {
    int size();
    boolean isEmpty();
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    V get(Object key);
    V put(K key, V value);
    void putAll(Map<? extends K, ? extends V> map);
    V remove(Object key);
    void clear();
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();
}

Mỗi phương thức đảm nhận một vai trò cụ thể:

• size() và isEmpty() phục vụ quản lý kích thước,
• containsKey()/containsValue() kiểm tra sự hiện diện của dữ liệu,
• get(), put(), remove() là các thao tác cơ bản,
• entrySet(), keySet(), values() cho phép truy cập dữ liệu dưới dạng bộ sưu tập chuẩn.

Giao diện Entry

Nội bộ Map định nghĩa giao diện Entry<K, V> để biểu diễn một cặp cụ thể:

interface Entry<K, V> {
    K getKey();
    V getValue();
    V setValue(V newValue);
    boolean equals(Object obj);
    int hashCode();
}

Giao diện này hỗ trợ việc truy xuất và cập nhật nhanh giá trị của từng cặp dữ liệu trong Map thông qua các phương thức truy cập chuẩn.

Thực hiện chung: AbstractMap

Lớp trừu tượng AbstractMap cung cấp triển khai sẵn một số phương thức chung dựa trên phương thức trừu tượng entrySet() — triển khai theo mẫu thiết kế Template Method:

public int size() {
    return entrySet().size();
}

public boolean isEmpty() {
    return size() == 0;
}

public V get(Object key) {
    Iterator<Entry<K, V>> iterator = entrySet().iterator();
    if (key == null) {
        while (iterator.hasNext()) {
            Entry<K, V> entry = iterator.next();
            if (entry.getKey() == null) {
                return entry.getValue();
            }
        }
    } else {
        while (iterator.hasNext()) {
            Entry<K, V> entry = iterator.next();
            if (key.equals(entry.getKey())) {
                return entry.getValue();
            }
        }
    }
    return null;
}

Các phương thức như put(), remove(Object) vẫn ném UnsupportedOperationException hoặc yêu cầu lớp dẫn xuất phải cung cấp logic riêng.

Hai nhánh con mở rộng Map

1. SortedMap – Hỗ trợ sắp xếp

Giao diện SortedMap<K, V> mở rộng từ Map, đồng thời bổ sung các phương thức phục vụ truy xuất theo thứ tự khóa:

public interface SortedMap<K, V> extends Map<K, V> {
    Comparator<? super K> comparator();
    SortedMap<K, V> subMap(K fromKey, K toKey);
    SortedMap<K, V> headMap(K toKey);
    SortedMap<K, V> tailMap(K fromKey);
    K firstKey();
    K lastKey();
    // overridden keySet(), values(), entrySet()
}

Đặc biệt, subMap(fromKey, toKey) trả về một "cửa sổ" rõ ràng được giới hạn hai đầu; headMap() và tailMap() cắt tỉa từ đầu hoặc đến cuối cấu trúc.

2. ConcurrentMap – Hỗ trợ cập nhật nguyên tử

Giao diện ConcurrentMap<K, V> được thiết kế cho môi trường đa luồng, cung cấp các thao tác nguyên tử:

public interface ConcurrentMap<K, V> extends Map<K, V> {
    default V getOrDefault(Object key, V defaultValue) {
        V value = get(key);
        return (value != null) ? value : defaultValue;
    }

    V putIfAbsent(K key, V value);
    boolean remove(Object key, Object value);
    boolean replace(K key, V oldValue, V newValue);
    V replace(K key, V value);
}

Các phương thức như putIfAbsent() và replace() đều tránh trạng thái cạnh tranh (race condition) nhờ cơ chế Compare-And-Swap (CAS) hoặc khóa trong các triển khai cụ thể.

Các lớp triển khai thực tế

Mặc dù AbstractMap, SortedMap, ConcurrentMap tạo nền tảng cơ sở, nhưng chúng không đủ để sử dụng độc lập. Các lớp thực tế thường dùng bao gồm:

• HashMap: triển khai dựa trên bảng băm, hiệu suất cao nhưng không đảm bảo thứ tự,
• TreeMap: triển khai cây tìm kiếm nhị phân cân bằng (red-black tree), duy trì thứ tự tự nhiên hoặc theo Comparator,
• ConcurrentHashMap: tối ưu hóa đồng bộ hóa từng bucket thay vì khóa toàn bộ cấu trúc như HashTable,
• ConcurrentSkipListMap: sử dụng cấu trúc Skip List, hỗ trợ truy cập thứ tự và đồng bộ hóa mà không cần khóa truyền thống.

Lưu ý, HashTable tương tự HashMap về cấu trúc, duy nhất khác biệt là toàn bộ phương thức đều bị synchronized, do đó an toàn về luồng nhưng hiệu suất kém hơn đáng kể.