HashMap hoạt động như thế nào bên trong?

Bạn dùng HashMap mỗi ngày. Nhưng khi một cái cache trả về null mặc dù key đúng, khi một service chạy chậm bất ngờ sau khi data tăng, khi một bug chỉ xảy ra dưới concurrent load - phần lớn những vấn đề đó có gốc rễ từ việc không hiểu HashMap hoạt động bên trong như thế nào. Bài này giải thích từng cơ chế từ góc độ thiết kế, không phải từ định nghĩa.

Tại sao HashMap tồn tại?

Trước khi HashMap, để tìm một product theo ID trong một danh sách, bạn phải duyệt qua từng phần tử:

List<Product> catalog = productRepository.findAll(); // 100,000 products

Product found = null;
for (Product p : catalog) {
    if (p.getId().equals(targetId)) {
        found = p;
        break;
    }
}

Với 100k products và 1,000 requests/giây, trung bình mỗi lookup duyệt qua 50k phần tử: 50 triệu phép so sánh mỗi giây. Khi catalog tăng lên 1 triệu products, con số đó nhân 10. Đây là bài toán mà HashMap giải quyết: thay vì tìm kiếm tuyến tính O(n), nó cung cấp lookup O(1) trung bình bằng cách ánh xạ key trực tiếp đến vị trí lưu trữ.

Trade-off: O(1) là trung bình, không phải worst case. Worst case vẫn là O(n) khi xảy ra quá nhiều collision. Hiểu bên trong HashMap là hiểu khi nào O(1) bị phá vỡ.

Cấu trúc bên trong: Mảng của Bucket

HashMap là một mảng của các “bucket”. Mỗi bucket là một linked list (hoặc tree từ Java 8) của các entry. Mảng này trong source code Java được gọi là table.

// Simplified từ java.util.HashMap source
transient Node<K,V>[] table;

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // trỏ đến entry tiếp theo trong cùng bucket
}

Default initial capacity là 16 bucket. Để xác định key nào vào bucket nào, HashMap tính:

// bucket index = hash(key) & (capacity - 1)
int index = (n - 1) & hash;

Với capacity 16 (binary: 10000), 16 - 1 = 15 (binary: 01111). Phép AND với 15 giữ lại 4 bit cuối của hash, cho giá trị 0-15. Đây là lý do capacity của HashMap luôn là lũy thừa của 2: phép & (capacity - 1) thay thế phép chia lấy dư % capacity, nhanh hơn đáng kể.

Tại sao cần hiểu điều này: Nếu bạn khởi tạo new HashMap<>(15), Java sẽ tự làm tròn lên 16 (lũy thừa 2 gần nhất). new HashMap<>(17) sẽ tạo mảng 32 bucket, không phải 17. Nếu bạn đặt initial capacity dựa trên số lượng entry dự kiến mà không tính load factor, HashMap sẽ resize sớm hơn bạn nghĩ.

Dưới đây là bức tranh thực tế bên trong một HashMap với 8 bucket. Bucket xám nhạt là empty. Bucket tối là occupied. Entry màu teal được nối bằng con trỏ next khi có collision:

hashCode: Key vào Bucket nào?

hashCode() ánh xạ một key object sang một số nguyên. HashMap dùng số này để tìm bucket. Java thêm một bước scramble trước khi dùng:

// HashMap.hash() - trộn các bit cao vào bit thấp
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Bước XOR với h >>> 16 giải quyết trường hợp hai key có hashCode khác nhau chỉ ở bit cao - nếu không trộn, với capacity nhỏ (16, 32), chúng sẽ vào cùng bucket vì phép & (capacity-1) chỉ lấy bit thấp.

Cái gì vỡ nếu hashCode kém: Nếu tất cả key trả về cùng hashCode, mọi entry đều vào bucket 0. HashMap trở thành một linked list với O(n) cho mọi thao tác.

// hashCode tệ nhất có thể
public class ProductId {
    private final String value;

    @Override
    public int hashCode() {
        return 42; // tất cả key vào cùng một bucket
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof ProductId)) return false;
        return value.equals(((ProductId) o).value);
    }
}

Với 1,000 products dùng ProductId này làm key, mỗi get() duyệt qua linked list 1,000 phần tử. Bạn vừa tạo ra một data structure tệ hơn List.

Production bug thực tế: Custom domain object làm key mà không override hashCode().

// OrderKey chỉ override equals, quên hashCode
class OrderKey {
    String orderId;
    String customerId;

    @Override
    public boolean equals(Object o) {
        OrderKey other = (OrderKey) o;
        return orderId.equals(other.orderId) && customerId.equals(other.customerId);
    }
    // hashCode KHÔNG được override → dùng Object.hashCode() (địa chỉ memory)
}

Map<OrderKey, OrderDetails> orderIndex = new HashMap<>();
OrderKey k1 = new OrderKey("ORD-001", "CUST-42");
orderIndex.put(k1, details);

// Sau đó ở một service khác
OrderKey k2 = new OrderKey("ORD-001", "CUST-42"); // cùng giá trị, khác object
orderIndex.get(k2); // null - k1 và k2 có hashCode khác nhau (khác địa chỉ memory)

k1.equals(k2) trả về true, nhưng k1.hashCode() != k2.hashCode(). HashMap tìm bucket theo hashCode của k2, không thấy key, trả về null. Cache bị bypass hoàn toàn.

Trade-off: String.hashCode() duyệt qua tất cả ký tự mỗi lần gọi - O(n) theo độ dài chuỗi. Java String caches kết quả trong field hash vì String là immutable. Với mutable object, bạn không nên cache hashCode nếu các field dùng trong tính toán có thể thay đổi.

Collision: Khi hai Key vào cùng Bucket

Dù hashCode có tốt đến đâu, hai key khác nhau vẫn có thể rơi vào cùng bucket - gọi là collision. Đây là điều không thể tránh hoàn toàn (pigeonhole principle). Java giải quyết bằng chaining.

Trước Java 8: Mỗi bucket là một linked list. Worst case với n collision trong cùng bucket: O(n) per lookup.

Java 8+: Khi số entry trong một bucket đạt TREEIFY_THRESHOLD = 8, linked list chuyển sang Red-Black tree. Worst case giảm từ O(n) xuống O(log n).

// Từ HashMap source
static final int TREEIFY_THRESHOLD = 8;   // linked list → tree
static final int UNTREEIFY_THRESHOLD = 6; // tree → linked list khi entry giảm
static final int MIN_TREEIFY_CAPACITY = 64; // chỉ treeify nếu table đủ lớn

Linked list khi bucket chưa đạt threshold, tất cả 8 entry phải duyệt tuần tự để tìm key cuối cùng:

Sau khi đạt threshold 8, cùng bucket đó được convert sang Red-Black tree. Lookup prod-411 giờ chỉ cần 3 bước thay vì 8:

Tại sao treeification tồn tại: Trước Java 8, có thể tấn công DoS vào web application bằng cách gửi form POST với hàng nghìn parameter được tính toán để hash vào cùng bucket. Server tốn O(n²) xử lý một request duy nhất - CPU leo 100%. Java 8 giải quyết bằng tree + hash randomization cho String.

Production implication: Nếu bạn dùng custom class làm key, class đó phải implement Comparable để treeification hoạt động đúng (Red-Black tree cần thứ tự để so sánh). Nếu không implement Comparable, Java dùng identity hash làm tiebreaker - vẫn hoạt động nhưng không đảm bảo O(log n) trong mọi trường hợp.

Trade-off: TreeNode tốn bộ nhớ nhiều hơn Node (cần thêm parent, left, right, red pointer). Convert linked list sang tree có chi phí upfront. Treeification chỉ có lợi khi thực sự có nhiều collision. Nếu hashCode tốt, bucket hiếm khi đạt threshold 8 và bạn không bao giờ trả chi phí này.

Load Factor và Resize

Load factor = số entry hiện tại / capacity. Khi vượt ngưỡng (default 0.75), HashMap tạo array mới gấp đôi kích thước và rehash tất cả entry.

Tại sao 0.75: Đây là điểm cân bằng thực nghiệm giữa tốc độ và bộ nhớ. Load factor thấp hơn (0.5) nghĩa là nhiều bucket trống, ít collision hơn, lookup nhanh hơn, nhưng tốn bộ nhớ gấp đôi. Load factor cao hơn (0.9) tiết kiệm bộ nhớ nhưng nhiều collision, lookup chậm hơn. Ở 0.75, xác suất collision ở mức chấp nhận được với mức tiêu thụ bộ nhớ hợp lý.

Cái gì vỡ khi bỏ qua resize cost:

// Cache khởi tạo không có initial capacity
Map<String, Product> productCache = new HashMap<>();

// Load 50,000 products
products.forEach(p -> productCache.put(p.getId(), p));
// Resize xảy ra tại: 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144, 12288, 24576, 49152
// 13 lần resize, mỗi lần O(n) rehash - tổng overhead đáng kể

Mỗi resize: cấp phát array mới, tính lại index cho từng entry và copy sang. Với 50k entries, lần resize cuối rehash 25k entries. Tổng công việc resize: khoảng 100k operations thừa.

Production fix: Pre-size khi biết trước số lượng:

// Công thức: initialCapacity = expectedSize / loadFactor + 1
int expectedEntries = 50_000;
Map<String, Product> productCache = new HashMap<>((int) (expectedEntries / 0.75) + 1);
// Hoặc dùng Guava
Map<String, Product> productCache = Maps.newHashMapWithExpectedSize(expectedEntries);

Trade-off: Pre-sizing allocates memory upfront. Nếu bạn tạo nhiều HashMap nhỏ per-request (ví dụ trong service layer để nhóm dữ liệu), pre-sizing 10,000 cho một map thực tế chỉ có 10 entry gây GC pressure nghiêm trọng. Pre-sizing có giá trị nhất với long-lived cache có kích thước dự đoán được. Với short-lived local map, để mặc định.

hashCode + equals Contract: Quy tắc không được phá vỡ

Contract: nếu a.equals(b) là true, thì a.hashCode() == b.hashCode() cũng phải là true.

Tại sao contract này tồn tại: HashMap tìm key theo hai bước. Bước 1: dùng hashCode để tìm bucket. Bước 2: dùng equals để tìm đúng entry trong bucket. Nếu hai object “bằng nhau” theo equals nhưng có hashCode khác nhau, bước 1 tìm sai bucket và bước 2 không bao giờ được thực thi.

Chiều ngược lại không bắt buộc: a.hashCode() == b.hashCode() không đòi hỏi a.equals(b). Đây là collision bình thường - nhiều object có thể share cùng hashCode.

Production bug: mutable object làm key

class CacheKey {
    private String region;
    private String userId;

    // Đúng contract: equals và hashCode nhất quán
    @Override
    public boolean equals(Object o) {
        CacheKey other = (CacheKey) o;
        return region.equals(other.region) && userId.equals(other.userId);
    }

    @Override
    public int hashCode() {
        return Objects.hash(region, userId);
    }

    // Setter - đây là vấn đề
    public void setRegion(String region) { this.region = region; }
}

Map<CacheKey, UserSession> sessionCache = new HashMap<>();
CacheKey key = new CacheKey("VN", "user-42");
sessionCache.put(key, session);

// Sau đó, ai đó thay đổi field dùng trong hashCode
key.setRegion("SG");

// Bây giờ key.hashCode() đã khác - key nằm trong bucket cũ
// nhưng HashMap tìm theo bucket mới
sessionCache.get(key);    // null - bucket sai
sessionCache.remove(key); // no-op - không tìm thấy để xóa
// Entry "orphaned" trong map: không thể get, không thể remove
// → memory leak vì key giữ strong reference đến session object

Entry đó sẽ tồn tại trong map mãi mãi, không thể accessed và không được GC thu dọn vì map còn giữ reference. Đây là một dạng memory leak thực sự.

Nguyên tắc: Dùng immutable object làm HashMap key bất cứ khi nào có thể. String, Integer, Long, UUID là những lựa chọn tốt. Nếu cần dùng custom class, đảm bảo các field tham gia vào hashCode và equals không thể thay đổi sau khi object được tạo.

Thread Safety: HashMap không phải là Thread-Safe

HashMap không được thiết kế cho concurrent access. Khi nhiều thread đọc ghi đồng thời:

• Lost update: hai thread cùng put() vào cùng bucket, một update bị ghi đè
• Infinite loop (Java 7): khi resize, linked list có thể tạo thành vòng tròn do race condition - thread duyệt qua next không bao giờ kết thúc, CPU leo 100%
• Inconsistent read: thread đọc trong khi thread khác đang resize - đọc được array chưa khởi tạo hoàn chỉnh

Java 8 đã sửa lỗi infinite loop nhưng HashMap vẫn không safe cho concurrent write.

Production bug thường gặp:

@Service
public class ProductCacheService {

    // WRONG: HashMap shared giữa nhiều threads
    private final Map<String, Product> cache = new HashMap<>();

    public Product getProduct(String id) {
        if (!cache.containsKey(id)) {
            Product product = productRepository.findById(id)
                .orElseThrow(() -> new ProductNotFoundException(id));
            cache.put(id, product); // race condition với thread khác
        }
        return cache.get(id);
    }
}

Hai thread đồng thời gọi getProduct("prod-42"). Cả hai thấy containsKey trả về false. Cả hai gọi database. Cả hai gọi put(). Trong khi đó, một thread thứ ba đang đọc một bucket khác bị ảnh hưởng bởi resize đang xảy ra. Kết quả: inconsistent state, potential NullPointerException, double database call.

Fix:

// Option 1: ConcurrentHashMap - lựa chọn đúng cho phần lớn trường hợp
// Java 8+: dùng CAS + synchronized per-bin, không lock toàn bộ map
private final Map<String, Product> cache = new ConcurrentHashMap<>();

// Quan trọng: dùng computeIfAbsent thay vì containsKey + put
// computeIfAbsent là atomic trong ConcurrentHashMap
public Product getProduct(String id) {
    return cache.computeIfAbsent(id, key ->
        productRepository.findById(key)
            .orElseThrow(() -> new ProductNotFoundException(key))
    );
}

// Option 2: Collections.synchronizedMap - lock toàn bộ map cho mỗi operation
// Đơn giản hơn nhưng serializes tất cả access, bottleneck khi concurrent cao
private final Map<String, Product> cache = Collections.synchronizedMap(new HashMap<>());

// Option 3: HashMap per-thread (không share)
// Không có contention, phù hợp cho local processing
public Map<String, List<Order>> groupOrdersByCustomer(List<Order> orders) {
    Map<String, List<Order>> grouped = new HashMap<>(); // local, không share
    orders.forEach(o -> grouped
        .computeIfAbsent(o.getCustomerId(), k -> new ArrayList<>())
        .add(o));
    return grouped;
}

Trade-off: ConcurrentHashMap tốn bộ nhớ hơn HashMap nhờ metadata nội bộ. Với read-heavy workload (cache), overhead gần như không đáng kể. Với write-heavy workload có nhiều thread update cùng key, vẫn có contention dù ở mức per-bin thay vì toàn map. computeIfAbsent trong ConcurrentHashMap là atomic - nhưng lưu ý: hàm mapping truyền vào không nên có side effect nặng (như gọi database với lock) vì nó có thể chặn bin đó trong thời gian dài.

Tổng kết

Mental model cuối: HashMap là một mảng nơi index được tính từ key. Phần khó là: đảm bảo mọi key luôn đến đúng index (hashCode+equals contract), xử lý khi nhiều key đến cùng index (collision), giữ cho mảng không quá đầy (resize), và đảm bảo nhiều thread không can thiệp vào nhau (thread safety). Hiểu bốn điều này, bạn có thể dự đoán và giải thích mọi behavior của HashMap.