Trước và sau khi đọc, mình muốn bạn dừng lại một chút để thử suy nghĩ và trả lời các câu hỏi dưới đây:
- Trình bày implementation của hashmap?
- Trình bày mối quan hệ giữa equals() và hashCode()?
- Nếu một hash conflict xảy ra, thì hashmap xử lý như nào?
- JDK 8 có cải tiến gì cho Hashmap?
- Red-black tree hoạt động như thế nào? ưu nhược điểm so với Linked List (trong ngữ cảnh hashmap)?
- Hashmap có phải thread-safe ko? Giải pháp ở đây là gì? nêu nguyên lý hoạt động của giải pháp đó?
1. Cấu trúc bên trong
HashMap trong Java được triển khai bằng cách sử dụng một mảng các bucket. Mỗi bucket là một danh sách liên kết (linked list) chứa các cặp key-value (Entry). Khi bạn thêm một cặp key-value vào HashMap, nó sẽ tính toán mã băm (hash code) của key để xác định bucket mà cặp này sẽ được lưu trữ. Nếu có nhiều cặp có cùng mã băm, chúng sẽ được lưu trữ trong cùng một bucket dưới dạng một danh sách liên kết.!
Hình ảnh trên cho thấy cách HashMap lưu trữ các phần tử của nó. Bên trong HashMap sử dụng một mảng Entry<K, V> được gọi là table[] để lưu trữ các cặp khóa-giá trị.
HashMap không chèn các đối tượng khi bạn đặt (put) chúng vào phần tử HashMap ngay. Thay vào đó, nó sử dụng mã băm (hashcode) của khóa để quyết định chỉ mục (index) cho cặp giá trị-cặp cụ thể. Nó được gọi là Hashing.
2. Hashing là gì?
Toàn bộ cấu trúc dữ liệu HashMap dựa trên nguyên tắc Hashing. Hashing là chức năng hoặc thuật toán hoặc phương pháp mà khi áp dụng cho bất kỳ đối tượng / biến trả về một giá trị số nguyên duy nhất đại diện cho rằng đối tượng / biến. Giá trị số nguyên duy nhất này được gọi là mã băm (hash code).
Hàm Hash được gọi là tốt nếu nó trả về cùng một mã băm mỗi khi nó được gọi trên cùng một đối tượng. Hai đối tượng có thể có cùng một mã băm (hash code).
Bất cứ khi nào bạn chèn cặp khóa-giá trị mới bằng cách sử dụng phương thức put(), HashMap không chèn lập tức vào table[]. Thay vào đó, nó sẽ gọi hàm băm trên khoá (key). HashMap có hàm băm riêng để tính toán mã băm của khoá (key).
3. Phương thức hashCode() và equals()
HashMap sử dụng phương thức hashCode và equals để thêm vào (put) và lấy lại (get) phần từ một tập hợp tương ứng. Khi hàm put() đuợc gọi, HashMap tính toán giá trị hash (giá trị băm) của khoá và lưu trữ cặp giá trị (key-value) đuợc đánh chỉ mục (index) thích hợp vào tập hợp. Nếu khoá đã tồn tại, giá trị của nó đuợc cập nhật (update) bằng giá trị mới.
Nếu 2 hàm này không đuợc cài đặt (implement) chính xác, như 2 khoá khác nhau lại cho ra hash code (giá trị đã băm) giống nhau và vì vậy chúng sẽ đuợc xem như là bằng nhau trong tập hợp. Hai hàm này còn sử dụng để phát hiện trùng lặp. Nên việc cài đặt 2 hàm là yếu tốt then chốt để kiểm tra tính đúng đắn của HashMap.
4. Các thành phần quan trọng
- Mảng bucket (table): Đây là một mảng các Node, mỗi Node đại diện cho một bucket. Mỗi Node chứa một tham chiếu đến Entry đầu tiên trong danh sách liên kết của bucket đó.
- Entry: Đây là một lớp bên trong của HashMap, đại diện cho một cặp key-value. Mỗi Entry chứa các trường sau:
- key: Khóa của cặp.
- value: Giá trị tương ứng với khóa.
- hash: Mã băm của khóa.
- next: Tham chiếu đến Entry tiếp theo trong danh sách liên kết (nếu có).
- load factor: Đây là một hệ số đại diện cho mức độ "đầy" của HashMap. Khi số lượng Entry trong HashMap vượt quá load factor nhân với kích thước của mảng bucket, HashMap sẽ tự động tăng kích thước mảng bucket (rehashing) để đảm bảo hiệu suất. Giá trị mặc định của load factor là 0.75.
- threshold: Đây là ngưỡng kích hoạt quá trình rehashing. Nó được tính bằng cách nhân load factor với kích thước của mảng bucket.
5. Các hoạt động chính
-
put(key, value): Thêm một cặp key-value vào HashMap.
- Tính toán mã băm của key.
- Xác định bucket tương ứng dựa trên mã băm.
- Nếu bucket trống, tạo một Entry mới và thêm vào bucket.
- Nếu bucket không trống, duyệt qua danh sách liên kết để kiểm tra xem key đã tồn tại chưa.
- Nếu key đã tồn tại, cập nhật giá trị của Entry tương ứng.
- Nếu key chưa tồn tại, tạo một Entry mới và thêm vào đầu danh sách liên kết.
- Nếu số lượng Entry vượt quá threshold, thực hiện rehashing.
Example Code:
public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table.length); for (Entry<K, V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null;
}
-
get(key): Lấy giá trị tương ứng với key.
- Tính toán mã băm của key.
- Xác định bucket tương ứng dựa trên mã băm.
- Nếu bucket trống, trả về null.
- Nếu bucket không trống, duyệt qua danh sách liên kết để tìm Entry có key tương ứng.
- Nếu tìm thấy, trả về giá trị của Entry.
- Nếu không tìm thấy, trả về null.
Example code:
public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entry<K , V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null;
}
- remove(key): Xóa cặp key-value tương ứng với key.
- Tính toán mã băm của key.
- Xác định bucket tương ứng dựa trên mã băm.
- Nếu bucket trống, không làm gì cả.
- Nếu bucket không trống, duyệt qua danh sách liên kết để tìm Entry có key tương ứng.
- Nếu tìm thấy, xóa Entry khỏi danh sách liên kết.
- rehashing: Tăng kích thước mảng bucket và phân phối lại các Entry.
- Tạo một mảng bucket mới với kích thước gấp đôi kích thước cũ.
- Duyệt qua từng Entry trong mảng bucket cũ.
- Tính toán lại mã băm của key và xác định bucket mới tương ứng trong mảng bucket mới.
- Thêm Entry vào bucket mới.
Why we need to resize the HashMap?
Đó là bởi vì nếu kích thước được cố định và khi ngày càng có nhiều phần tử được thêm vào hashmap, thì sẽ ngày càng có nhiều xung đột hơn và do đó danh sách liên kết được duy trì lâu hơn, do đó việc lặp lại chúng sẽ không còn với thời gian không đổi nữa mà có thể lên tới O( N). Vì vậy, để trải rộng các Nút đồng đều hơn, hãy thay đổi kích thước bản đồ băm khi tổng số nút trong đó vượt quá một số giá trị ngưỡng.
6. Tối ưu hóa
- Sử dụng cây đỏ-đen (red-black tree): Từ Java 8 trở đi, khi số lượng Entry trong một bucket vượt quá một ngưỡng nhất định (thường là 8), danh sách liên kết sẽ được chuyển đổi thành một cây đỏ-đen để cải thiện hiệu suất tìm kiếm trong trường hợp có nhiều va chạm hash.
- Hashing cải tiến: HashMap sử dụng một hàm băm cải tiến để giảm thiểu va chạm hash và phân phối các Entry đều hơn trên các bucket.
Lưu ý:
- HashMap không đảm bảo thứ tự của các phần tử.
- HashMap cho phép key là null, nhưng chỉ được có một key null.
- HashMap không đồng bộ (thread-safe). Nếu bạn cần sử dụng HashMap trong môi trường đa luồng, hãy sử dụng
ConcurrentHashMap. Ví dụ hoạt động của HashMap:
import java.util.HashMap;
import java.util.Map; /** * Java program to illustrate internal working of HashMap */
class Key { String key; Key(String key) { this.key = key; } @Override public int hashCode() { int hash = (int) key.charAt(0); System.out.println("hashCode for key: " + key + " = " + hash); return hash; } @Override public boolean equals(Object obj) { return key.equals(((Key) obj).key); }
} public class HashMapInternalWorking { public static void main(String[] args) { Map<Key, Integer> map = new HashMap<>(); // line 1 map.put(new Key("vishal"), 20); // line 2 map.put(new Key("sachin"), 30); // line 3 map.put(new Key("vaibhav"), 40); // line 4 System.out.println(); System.out.println("Value for key sachin: " + map.get(new Key("sachin"))); // line 5 System.out.println("Value for key vaibhav: " + map.get(new Key("vaibhav"))); // line 6 }
}
Output:
hashCode for key: vishal = 118
hashCode for key: sachin = 115
hashCode for key: vaibhav = 118 hashCode for key: sachin = 115
Value for key sachin: 30
hashCode for key: vaibhav = 118
Value for key vaibhav: 40
Giải thích hoạt động của chương trình trên:
line 1: Khởi tạo hashMap rỗng: bảng tính hashmap được kích thước là 16
Map<Key, Integer> map = new HashMap<>(); // line 1
line 2: Chèn cặp khóa-giá trị: Đặt một cặp khóa-giá trị ở trên HashMap
map.put(new Key("vishal"), 20); // line 2
Các bước:
- Tính mã băm (hash code) của khóa {“vishal”}. Nó sẽ được tạo ra là 118.
- Tính chỉ số (index) bằng cách sử dụng phương pháp chỉ số sẽ là 6.
- Tạo một đối tượng node như sau:
{ int hash = 118 Key key = {“vishal”} Integer value = 20 Node next = null }
- Đặt đối tượng này ở chỉ số 6, nếu không có đối tượng nào khác được trình bày ở đó.
Bây giờ HashMap trở thành:
line 3: Chèn cặp khóa-giá trị: Đặt một cặp khóa-giá trị khác ở trên HashMap
map.put(newKey("sachin"),30);// line 3
Các bước:
- Tính mã băm (hash code) của khóa {“sachin”}. Nó sẽ được tạo ra là 115.
- Tính chỉ số (index) bằng cách sử dụng phương pháp chỉ số sẽ là 3.
- Tạo một đối tượng node như sau:
{ int hash = 115 Key key = {“sachin”} Integer value = 30 Node next = null }
- Đặt đối tượng này ở chỉ số 3, nếu không có đối tượng nào khác được trình bày ở đó.
Bây giờ HashMap trở thành:
line 4: Chèn cặp khóa-giá trị: Đặt một cặp khóa-giá trị khác ở trên HashMap
map.put(newKey("vaibhav"),40);// line 4
Các bước:
- Tính mã băm (hash code) của khóa {“vaibhav”}. Nó sẽ được tạo ra là 118.
- Tính chỉ số (index) bằng cách sử dụng phương pháp chỉ số sẽ là 6.
- Tạo một đối tượng node như sau:
{ int hash = 118 Key key = {“vaibhav”} Integer value = 40 Node next = null }
- Đặt đối tượng này ở chỉ số 6, nếu không có đối tượng nào khác được đặt ở đó.
- Trong trường hợp này, một đối tượng nút được tìm thấy tại chỉ số 6. Do đó, cần kiểm tra qua phương thức hashCode() và equals() nếu cả hai khóa đều giống nhau.
- Nếu các khóa (key) giống nhau, hãy thay giá trị (value) bằng giá trị hiện tại.
- Nếu không thì thêm phần tử vào cuối danh sách liên kết (linked list) và cả hai đều được lưu trữ tại chỉ mục 6.
Bây giờ HashMap trở thành:
line 5:Tìm dữ liệu cho key “sachin”:
map.get(newKey("sachin");// line 5
Các bước:
- Tính mã băm (hashcode) của Key {“sachin”}. Nó sẽ được tạo ra là 115.
- Tính chỉ số (index) bằng cách sử dụng phương thức index sẽ là 3.
- Đi tới chỉ số 3 của mảng và so sánh phần tử của phần tử đầu tiên với khóa đã cho. Nếu cả hai đều bằng (equal) thì trả lại giá trị, nếu không thì kiểm tra các phần tử tiếp theo nếu có.
- Trong trường hợp này, nó được tìm thấy như là phần tử đầu tiên và giá trị trả về là 30.
line 6:Tìm dữ liệu cho key “sachin”:
map.get(newKey("vaibhav");// line 6
Các bước:
- Tính mã băm (hashcode) của Key {“vaibhav”}. Nó sẽ được tạo ra là 118.
- Tính chỉ số (index) bằng cách sử dụng phương thức index sẽ là 6.
- Đi tới chỉ số 6 của mảng và so sánh phần tử của phần tử đầu tiên với khóa đã cho. Nếu cả hai đều bằng (equal) thì trả lại giá trị, nếu không thì kiểm tra các phần tử tiếp theo nếu có.
- Trong trường hợp này, nó không được tìm thấy ở phần tử đầu tiên và giá trị tiếp theo của đối tượng nút (node) không phải là null.
- Nếu tiếp theo của nút (node) thì trả về null.
- Nếu nút (node) kế tiếp không phải là null thì đi qua phần tử thứ hai và lặp lại bước 3 cho đến khi không tìm thấy khóa hoặc tiếp theo không phải là null.
Nguồn tham khảo: https://anmolsehgal.medium.com/java-hashmap-internal-implementation-21597e1efec3
https://gpcoder.com/2645-hashmap-trong-java-hoat-dong-nhu-the-nao/