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

Giới thiệu HashMap trong Java

Lớp HashMap trong java là một lớp kế thừa lớp AbstractMap và triển khai của Map Interface trong Collections Framework nên nó sẽ có một vài đặc điểm và phương thức tương đồng với Map. HashMap được sử dụng để lưu trữ các phần tử dưới dạng "key/value". Key và value là kiểu dữ liệu bất kỳ, và bạn có thể try cập các giá trị của HasMap bằng một key cụ thể.

HashMap là một trong những cấu trúc dữ liệu hay được sử dụng nhất trong Java, nhưng bản thân map thì lại không phải được coi là là một collection bởi vì nó không được implement Collection interface. Nhưng dĩ nhiên, một collection view có thể đại diện cho map thông qua method entrySet(), hoặc để lấy được collection view của các khoá (key), java hỗ trợ method keySet().

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

Chúng ta hãy cùng xem xét các hoạt động bên trong HashMap hoạt động như thế nào trong Java - đây cũng là một câu hỏi phỏng vấn hay được hỏi thuộc Java collection. Có bốn thứ bạn nên biết trước khi tìm hiểu sâu hơn về HashMap:

1. HashMap hoạt động dựa trên nguyên lý của việc băm dữ liệu (hashing).
2. Map.Entry interface: Interface này là nơi đại diện chứa các entry (cặp key - value) của map.
3. Phương thức hashCode(): HashMap cung cấp hoạt động put(key, value) để lưu trữ và get(key) để lấy ra giá trị từ HashMap. Khi phương thức put được gọi, HashMap sẽ gọi phương thức hashCode() từ đối tượng key để tính toán giá trị hash, sau đó dùng hash để tìm đến bucket[1] tương ứng và lưu trữ đối tượng Entry trong đó. Khi get() được sử dụng để lấy ra value, một lần nữa đối tượng key được dùng để tính toán ra hash, từ đó tìm được bucket - nơi chứa dữ liệu của key đó.
4. Phương thức equals(): phương thức này thường dùng để so sánh 2 object. Trong trường hợp của HashMap là so sánh 2 key, ngoài ra phương thức equals() được dùng để xử lý hashing collision (xung đột hash value - các key khác nhau nhưng lại có hash value giống nhau, như vậy chúng được xếp chung vào cùng một bucket. Trong trường hợp đó, các đối tượng value được lưu bên trong một linked list). Trong khi hashCode() được dùng để tìm ra hash của key thì equals() giúp ta tìm được chính xác value tương ứng với key trong trường hợp một hash code trỏ tới nhiều value.

Ví dụ hoạt động của HashMap trong Java

Để có thể hiểu được tầm quan trọng của các phương thức hashCode() và equals() liên quan như thế nào đến việc HashMap hoạt động như thế nào trong Java. Ví dụ sau chúng ta sẽ ghi đè 2 phương thức này:

package vn.kienthuclaptrinh.collection.hashmap;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class HashMapTest {
    public static void main(String[] args) {
        Map<LangKey, String> langMap = new HashMap<LangKey, String>();
        langMap.put(new LangKey(1, "EN"), "English");
        langMap.put(new LangKey(2, "VI"), "Vietnamese");
        langMap.put(new LangKey(3, "ES"), "Spainish");
        langMap.put(new LangKey(4, "JP"), "Jaspanese");
        langMap.put(null, "Jaspanese");

        System.out.println("Size cua langMap la: " + langMap.size());
        System.out.print("Cac phan tu cua langMap: ");
        Iterator<LangKey> itr = langMap.keySet().iterator();
        while (itr.hasNext()) {
            System.out.print(langMap.get(itr.next()) + " ");
        }
        System.out.println("\nSize cua langMap la: " + langMap.size());
    }

}

/**
 * Các đối tượng của lớp Key được sử dụng 
 * như các key của HashMap
 */
class LangKey {
    int index;
    String name;

    LangKey(int index, String Name) {
        this.index = index;
        this.name = Name;
    }

    /**
     *  Ghi đè phương thức hashCode()
     *  Phương thức này luôn trả về: 5
     */
    @Override
    public int hashCode() {
        return 5;
    }

    /**
     *  Ghi đè phương thức equals()
     *  Phương thức này luôn trả về: true
     */
    @Override
    public boolean equals(Object obj) {
        return true;
    }
}

Biên dịch và chạy chương trình trên sẽ cho ra kết quả như sau:

Chú ý rằng, tôi đã thêm 4 phần tử vào bên trong HashMap, nhưng kích thước của HashMap thì chỉ có một, và khi duyệt nó chỉ in ra phần tử cuối cùng trong 4 phần tử đó. Tại sao?

Điều thứ nhất: Bạn hãy chú ý đến các phương thức hashCode() và equals(). Trong đó phương thức hashCode() trong lớp LangKey, nó luôn trả về 5 và equals() luôn trả về true.

Khi một giá trị được lưu vào trong HashMap, nó tính toán hash dựa trên đối tượng key và nó sử dụng phương thức hashCode() để làm việc này. Dựa trên hash nhận được, HashMap sẽ quyết định bucket nào dùng để chứa đối tượng Entry mới này.

Với hashCode() luôn trả về 5. Điều này có nghĩa là những hash đã được tính toán giống i hệt nhau với những value khác nhau. Cho nên tất cả các đối tượng Entry được lưu vào trong cùng 1 bucket.

Điều thứ 2, HashMap sử dụng phương thức equals() để check xem value sẽ được thêm vào có giống với value đã nằm trong nó với trường hợp trùng hash hay không. Như đã nhắc ở trên, (Entry Object) được lưu dưới dạng linked list. Nó giống trường hợp của chúng ta ở hashCode() nhưng lại khác ở equals() vì equals() lúc này trả về false - có nghĩa là có một key chứa nhiều hơn một value. Ở đoạn code trên equals() luôn trả về true cho nên HashMap nghĩ rằng các key này đều giống nhau và bắt đầu ghi đè giá trị cũ.

Hoạt động put của HashMap trong Java

Khi gọi phương thức put() của đối tượng HashMap, sẽ có ba trường hợp sảy ra như sau:

1. Phương thức hashCode() được gọi và tính ra hash value, nếu hash value này không tồn tại trong hash table, thì chèn Entry vào một bucket mới.
2. Phương thức equals() được gọi khi hash value tồn tại, nếu trả về true tức là đã có key tồn tại trong HashMap, ghi đè Entry cũ bằng Entry mới trên Linked List ở bucket của Entry cũ.
3. Phương thức equals() trả về false thêm một phần tử vào đằng sau Linked List ở bucket tương ứng với hash value.

Hình ảnh minh họa HashMap trong Java hoạt động như thế nào?

Trường hợp key của HashMap là null

Thay đổi của HashMap trong java 8

Mặc dù nhìn qua có vẻ HashMap get() và put() có độ phức tạp O(1) nhưng đó chỉ là điều kiện lý tưởng khi không có hash collision. Performance của HashMap có thể bị kéo xuống khá nhiều nếu như có càng nhiều hash collision, bởi vì hash collision sảy ra tương đương với chúng ta sẽ phải thực hiện search trên linked list với độ dài > 1. Và tìm kiếm trên linked-list nó có độ phức tạp của một hàm tuyến tính, trong trường hợp tệ nhất sẽ là O(n).

Để giải quyết vấn đề này, Java 8 sử dụng cây cân bằng thay cho linked list với điều kiện số phần tử vượt quá một ngưỡng nào đó. Như vậy trong trường hợp tệ nhất độ phức tạp thay vì là O(n) sẽ giảm xuống còn O(log n).

Chú thích [1] bucket thường dùng để chỉ chỉ số của một mảng mà cụ thể ở đây là nó chỉ chỉ số của HashTable. Ví dụ table[0] tương ứng với bucket0, table[1] tương ứng với bucket1.