“Cơ chế làm việc của HashMap”
Dĩ nhiên là HashMap làm việc dựa trên nguyên lý Hashing – băm. Thế nhưng chẳng ai muốn nghe những câu trả lời chung chung kiểu như thế.
Để hiểu về Hashing, chúng ta cần nắm được 3 khái niệm: Hash function, hash value và bucket.
Hash function, hay còn gọi là hàm băm, là một hàm mà khi ta lấy đầu vào là một giá trị bất kỳ thì ở đầu ra, hash fuction sẽ cho ta một dãy code – được gọi là hash value. Mỗi đầu vào chỉ có duy nhất một hash value.
Bucket là nơi mà chúng ta lưu trữ các cặp key-value. (Map vốn là một cấu trúc dữ liệu sử dụng key-value để lưu trữ và truy xuất các phần tử). Trong HashMap, bucket dùng LinkedList để lưu trữ (LinkedList ở đây được implement riêng trong HashMap, nó khác với LinkedList trong gói java.util.LinkedList).
“Cơ chế Hashing liên quan gì tới việc lưu và truy xuất phần value trong HashMap?”
Nhiều người sẽ nghĩ rằng, phần value được lưu trong bucket và chúng được truy xuất trực tiếp thông qua phần key. Nhưng sự thực không phải như vậy.
Hãy xem class HashMap chứa những gì:
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry[] table;Theo chân lý từ thời nguyên thủy thì Map lưu trữ dữ liệu dưới dạng key-value. truy xuất value thông qua key.
Tuy nhiên HashMap thì lưu các Object dưới dạng các instance kiểu Entry, không lưu dưới dạng key-value.
Entry class?
Hãy nhìn tiếp vào class HashMap, bạn sẽ thấy một class tên là Entry:
static class Entry<K,V> implements Map.Entry<K,V>
{
final K key;
V value;
Entry<K,V> next;
final int hash;
........
}Bạn thấy đấy, tại Entry class, dữ liệu mới được lưu dưới dạng key và value. Còn HashMap thì lưu các instance của Entry class. Để lưu một value vào HashMap, ta phải gọi method put().
Cơ chế làm việc của method put()
Khi bạn đọc phần implement của put(), bạn sẽ thấy:
public V put(K key, V value)
{
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
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;
}Đầu tiên khối code này check key được truyền vào có bị null không. Nếu null, nó được lưu ở vị trí 0, điều này đồng nghĩa với hashCode() = 0
Tiếp đó, nếu key không bị null, nó sẽ tạo hashCode() cho key.
Method indexFor() được gọi để mang đến thông tin chính xác về vị trí lưu Entry object này.
Và đây là phần quan trọng nhất: nếu 2 object có hash code giống nhau, chúng được lưu chung 1 bucket. Để xử lý phần này, hãy nghĩ về cấu trúc dữ liệu LinkedList, mỗi nút trong Linked List đều chứa con trỏ trỏ tới nút tiếp theo. Trong Entry class cũng thế, mỗi object của Entry class đều chứa con trỏ đẻ trỏ tới object tiếp theo, cứ thế tuần tự đến hết.
Nếu có xung đột xảy ra, HashMap sẽ kiểm tra giá trị của thuộc tính tiếp theo, nếu thuộc tính tiếp theo là NULL thì nó chèn Entry object vào vị trí còn trống đó. Nếu không, HashMap duy trì vòng lặp đế khi thuộc tính tiếp theo trống thì nó mới lưu Entry object vào đó.
Ngăn chặn các key trùng nhau
HashMap không cho phép các key trùng nhau dưới mọi hình thức.
import java.util.HashMap;
import java.util.Map;
public class HashMapExample
{
public static void main(String[] args)
{
Map map = new HashMap();
map.put(1,"Topica");
map.put(1,"Fpt");
map.put(1,"Techmaster");
map.put(null,"deptrai");
System.out.println(map);
}
}Đoạn code trên là một ví dụ. Ở đây, bạn cố ý put() vào HashMap các cặp key-value có key giống nhau, value khác nhau. Tuy nhiên khi chạy, bạn thấy kết quả như sau:
{null=deptrai; 1=Techmaster}Như vậy, “Techmaster” là giá trị value cuối cùng được put vào kèm với key = 1, các value khác như “Topica” và “Fpt” đã bị “ghi đè”…
Mấu chốt ở đây chính là hàm equals().
Như đã đề cập ở đầu bài viết, bucket sử dụng cấu trúc dữ liệu LinkedList và nó là nơi lưu trữ key-value. Nếu một hashValue chỉ đến một bucket có nhiều Entry, nó sẽ duyệt LinkedList và so sánh các key của từng Entry một bằng hàm equals(). Khi key.equals() trả về true, giá trị value tương ứng sẽ được put() vào vị trí đó.
Tất cả các class đều có thể là key nếu đó được @Override hàm equals() và hashCode(), việc này cũng giúp biến các class trở thành immutable class.
Method get() làm việc như thế nào?
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;
}
Ta thấy một logic gần tương tự với put() cũng được áp dụng ở đây.
Đầu tiên, check hashCode() từ key.
Nếu tìm được, trả về value, nếu không, trả về null.
Nói về performance
Với HashMap, có 2 yếu tố ảnh hưởng trực tiếp tới performance là:
- Initial Capacity – kích thước khởi tạo
- Load factor – hệ số tải
Capacity là con số nói về số lượng bucket trong HashMap.
Load factor là chỉ số để đo xem đến ngưỡng nào thì capacity của HashMap sẽ tự động tăng lên. Khi số lượng entry trong HashMap đạt đến ngưỡng vượt quá Load Factor cũng như Initial Capacity thì HashMap sẽ được rehash, sau đó tăng số lượng bucket lên gấp đôi. Giá trị mặc định của Load Factor là 0.75.
Cảm ơn và hẹn gặp lại.
Bài này đã được tôi dịch và đăng trên Techmaster Blog
Busy_Buggy 