HashMap là một trong những cấu trúc dữ liệu được sử dụng phổ biến nhất trong lập trình Java để quản lý các cặp khóa-giá trị. Kể từ JDK 8, cấu trúc bên trong của HashMap đã trải qua nhiều cải tiến đáng kể, bao gồm việc tích hợp cây Đỏ-Đen (Red-Black Tree) và tối ưu hóa quá trình thay đổi kích thước. Bài viết này sẽ phân tích chi tiết cách HashMap hoạt động, tập trung vào những thay đổi quan trọng từ JDK 7 sang JDK 8.
Tổng quan về các lớp triển khai Map
Giao diện java.util.Map trong Java định nghĩa cấu trúc cho các ánh xạ dữ liệu. Có bốn lớp triển khai chính của giao diện này mà các nhà phát triển thường xuyên sử dụng:
- HashMap: Lưu trữ dữ liệu dựa trên giá trị
hashCodecủa khóa, cho phép truy cập nhanh chóng trong hầu hết các trường hợp. Thứ tự duyệt các phần tử không được đảm bảo.HashMapcho phép một khóanullduy nhất và nhiều giá trịnull. Đây là một cấu trúc dữ liệu không an toàn cho môi trường đa luồng (non-thread-safe), có thể dẫn đến mất nhất quán dữ liệu nếu nhiều luồng cùng sửa đổi đồng thời. Để đảm bảo an toàn luồng, có thể sử dụng phương thứcCollections.synchronizedMap()hoặcConcurrentHashMap. - Hashtable: Là một lớp kế thừa từ thời kỳ đầu của Java, cung cấp chức năng tương tự
HashMapnhưng là an toàn luồng (thread-safe). Tuy nhiên, hiệu suất đồng thời củaHashtablekém hơnConcurrentHashMap(do sử dụng khóa toàn bộ đối tượng thay vì khóa phân đoạn).Hashtablekhông được khuyến khích sử dụng trong mã mới; thay vào đó, hãy dùngHashMapcho các trường hợp không cần an toàn luồng vàConcurrentHashMapcho các trường hợp cần. - LinkedHashMap: Là một lớp con của
HashMap, duy trì thứ tự chèn các phần tử. Khi duyệt quaLinkedHashMapbằngIterator, các phần tử sẽ được trả về theo đúng thứ tự chúng được thêm vào. Ngoài ra, nó cũng có thể được cấu hình để duy trì thứ tự truy cập. - TreeMap: Triển khai giao diện
SortedMap, cho phép lưu trữ và sắp xếp các phần tử theo khóa. Mặc định, các khóa sẽ được sắp xếp theo thứ tự tăng dần, hoặc có thể chỉ định một bộ so sánh (Comparator) tùy chỉnh. Khi duyệtTreeMap, các phần tử luôn được trả về theo thứ tự đã sắp xếp. Để sử dụngTreeMap, các khóa phải triển khai giao diệnComparablehoặc mộtComparatorphải được cung cấp trong hàm tạo, nếu không sẽ gặp lỗijava.lang.ClassCastException.
Điều quan trọng cần lưu ý đối với tất cả các loại Map trên là các khóa (keys) nên là đối tượng bất biến (immutable). Một đối tượng bất biến là đối tượng mà giá trị băm (hash code) của nó không thay đổi sau khi được tạo. Nếu giá trị băm của khóa thay đổi, Map có thể không còn xác định được vị trí lưu trữ chính xác của nó.
Trong các lớp triển khai Map, HashMap nổi bật nhờ khả năng đáp ứng hầu hết các yêu cầu sử dụng, trở thành lựa chọn hàng đầu của các nhà phát triển. Trong các phần tiếp theo, chúng ta sẽ đi sâu vào cấu trúc lưu trữ, các phương thức phổ biến, cơ chế thay đổi kích thước (resizing) và vấn đề an toàn luồng của HashMap.
Cấu trúc bên trong của HashMap
Về mặt cấu trúc, HashMap trong JDK 8 được xây dựng dựa trên sự kết hợp của mảng, danh sách liên kết và cây Đỏ-Đen. Cụ thể, nó bao gồm một mảng các "bucket", mỗi bucket có thể chứa một danh sách liên kết các phần tử, và khi danh sách này trở nên quá dài, nó sẽ được chuyển đổi thành một cây Đỏ-Đen để tối ưu hiệu suất.
Điều gì thực sự được lưu trữ ở tầng thấp nhất? Và tại sao lại chọn cách lưu trữ này?
Cốt lõi của HashMap là một mảng có tên Node[] table, hay còn gọi là mảng các hash bucket. Mỗi phần tử trong mảng này là một đối tượng Node (trong JDK 8) hoặc Entry (trong JDK 7). Hãy xem cấu trúc của lớp Node trong JDK 8:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // Giá trị hash của khóa, dùng để xác định vị trí trong mảng
final K key;
V value;
Node<K,V> next; // Con trỏ tới Node tiếp theo trong danh sách liên kết
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
// Các phương thức getter, setter và equals, hashCode...
public final K getKey(){ return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); }
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this) return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
Mỗi đối tượng Node thực chất là một cặp khóa-giá trị (key-value pair) và đóng vai trò như một phần tử trong danh sách liên kết.
HashMap sử dụng bảng băm để lưu trữ dữ liệu. Để giải quyết các va chạm băm (hash collision), Java HashMap áp dụng phương pháp "chuỗi liên kết" (separate chaining). Theo phương pháp này, mỗi phần tử của mảng băm chứa một danh sách liên kết. Khi một cặp khóa-giá trị được băm và cho ra một chỉ số mảng, nó sẽ được thêm vào danh sách liên kết tại chỉ số đó. Ví dụ, khi thực hiện map.put("Apple", "Táo");, hệ thống sẽ gọi phương thức hashCode() của khóa "Apple", sau đó sử dụng thuật toán băm để xác định vị trí lưu trữ. Nếu hai khóa khác nhau lại cho ra cùng một chỉ số, một va chạm băm xảy ra.
Hiệu suất của HashMap phụ thuộc vào mức độ phân tán của kết quả băm. Để đạt được hiệu suất tốt, cần cân bằng giữa kích thước mảng băm và chất lượng của hàm băm. Mảng quá lớn tốn bộ nhớ, mảng quá nhỏ dễ gây va chạm. Các yếu tố quan trọng ảnh hưởng đến hiệu quả của HashMap bao gồm thuật toán băm và cơ chế thay đổi kích thước (resizing).
Hãy tìm hiểu một số trường quan trọng trong HashMap từ hàm tạo mặc định:
class HashMap<K,V> {
transient Node<K,V>[] table; // Mảng hash bucket
int size; // Số lượng cặp khóa-giá trị thực tế
int threshold; // Ngưỡng tối đa trước khi thực hiện resize
final float loadFactor; // Tỷ lệ tải (mặc định 0.75)
transient int modCount; // Đếm số lần cấu trúc HashMap thay đổi
// ...
}
table: Mảng lưu trữ cácNode. Chiều dài khởi tạo mặc định là 16.loadFactor: Tỷ lệ tải mặc định là 0.75. Đây là một yếu tố quan trọng quyết định khi nàoHashMapcần thay đổi kích thước.threshold: Ngưỡng chứa số lượng cặp khóa-giá trị tối đa màHashMapcó thể chấp nhận trước khi thực hiện thay đổi kích thước. Giá trị này được tính bằnglength * loadFactor. Khi số lượng phần tử thực tế (size) vượt quáthreshold, mảngtablesẽ được mở rộng gấp đôi. Tỷ lệ tải 0.75 là một lựa chọn cân bằng giữa hiệu suất thời gian và không gian.size: Là số lượng cặp khóa-giá trị thực sự có trongHashMap, khác với chiều dài của mảngtablevàthreshold.modCount: Theo dõi số lần cấu trúc bên trong củaHashMapthay đổi (ví dụ: thêm/xóa phần tử). Nó được sử dụng để hỗ trợ cơ chế "fail-fast" cho các iterator. Lưu ý rằng việc ghi đè giá trị cho một khóa hiện có không được tính là thay đổi cấu trúc.
Chiều dài của mảng table trong HashMap luôn là một lũy thừa của 2 (ví dụ: 16, 32, 64...). Đây là một thiết kế khác thường so với việc sử dụng số nguyên tố (như Hashtable sử dụng 11), mục đích chính là để tối ưu hóa các phép toán lấy phần dư (modulo) và thay đổi kích thước. Để giảm va chạm, HashMap cũng kết hợp các bit cao của giá trị băm trong quá trình tính chỉ số.
Ngay cả với thuật toán băm và tỷ lệ tải được thiết kế tốt, vẫn có thể xảy ra tình trạng các danh sách liên kết quá dài, gây ảnh hưởng nghiêm trọng đến hiệu suất. Để giải quyết vấn đề này, JDK 8 đã giới thiệu cây Đỏ-Đen. Khi một danh sách liên kết tại một bucket cụ thể vượt quá một ngưỡng nhất định (mặc định là 8 phần tử), nó sẽ được chuyển đổi thành một cây Đỏ-Đen. Cây Đỏ-Đen giúp cải thiện hiệu suất tìm kiếm, thêm và xóa từ O(n) xuống O(log n) trong trường hợp xấu nhất.
Các phương thức chính của HashMap
Để hiểu rõ hơn về HashMap, chúng ta sẽ xem xét cách nó thực hiện ba chức năng quan trọng: xác định chỉ số mảng, phương thức put() và cơ chế thay đổi kích thước.
1. Xác định chỉ số mảng băm
Việc định vị chính xác vị trí trong mảng băm là bước đầu tiên và quan trọng cho mọi thao tác thêm, xóa, hoặc tìm kiếm. Mục tiêu là phân bố các phần tử càng đều càng tốt để giảm thiểu việc duyệt danh sách liên kết. HashMap đạt được điều này thông qua một thuật toán băm hiệu quả.
Thuật toán băm trong HashMap (JDK 8) gồm ba bước chính:
- Lấy giá trị
hashCodecủa khóa. - Kết hợp các bit cao và thấp của giá trị
hashCode. - Tính chỉ số mảng bằng phép toán bitwise AND.
Đoạn mã dưới đây minh họa quá trình tính giá trị băm cuối cùng:
static final int calculateHash(Object key) {
int h;
// Bước 1 & 2: Lấy hashCode và kết hợp bit cao/thấp
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Sau khi có giá trị băm đã được điều chỉnh, chỉ số mảng được xác định bằng phép toán sau:
// Tính chỉ số mảng
int bucketIndex = finalHashValue & (tableLength - 1);
Phương pháp h & (length - 1) này rất hiệu quả vì khi length là một lũy thừa của 2, phép toán AND bitwise sẽ tương đương với phép toán modulo h % length nhưng nhanh hơn đáng kể. Việc kết hợp các bit cao và thấp của hashCode (h ^ (h >>> 16)) giúp phân tán các giá trị băm tốt hơn, đặc biệt khi mảng table có kích thước nhỏ, đảm bảo rằng cả các bit cao và thấp đều đóng góp vào việc tính toán vị trí, giảm thiểu va chạm.
2. Phân tích phương thức put()
Phương thức put() trong HashMap (JDK 8) có một luồng thực thi phức tạp nhưng được tối ưu hóa. Dưới đây là các bước chính:
- Nếu mảng
tablechưa được khởi tạo hoặc rỗng, nó sẽ được khởi tạo và thay đổi kích thước (resize()). - Tính toán giá trị băm (hash) của khóa và xác định chỉ số
itrong mảng. Nếutable[i]rỗng, mộtNodemới sẽ được tạo và đặt vào vị trí đó. - Nếu
table[i]không rỗng, kiểm tra xem khóa của phần tử đầu tiên tạitable[i]có trùng với khóa mới không (bằng cách so sánh hash, sau đó làequals()). Nếu trùng, giá trị cũ sẽ bị ghi đè. - Nếu
table[i]là mộtTreeNode(tức là đã chuyển thành cây Đỏ-Đen), phần tử mới sẽ được chèn vào cây. - Nếu
table[i]là một danh sách liên kết thông thường, duyệt qua danh sách.- Trong quá trình duyệt, nếu tìm thấy một khóa trùng, giá trị sẽ được ghi đè.
- Nếu không tìm thấy khóa trùng và danh sách liên kết đạt đến độ dài tối đa (mặc định là 8), danh sách sẽ được chuyển đổi thành cây Đỏ-Đên (
treeifyBin()) và phần tử mới được thêm vào. - Nếu không, phần tử mới sẽ được thêm vào cuối danh sách liên kết.
- Sau khi chèn thành công, nếu số lượng phần tử thực tế (
size) vượt quá ngưỡngthreshold,HashMapsẽ thực hiện thay đổi kích thước (resize()).
Dưới đây là một phần mã nguồn của phương thức putVal trong JDK 8 để minh họa các bước trên:
public V put(K key, V value) {
return putVal(calculateHash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] currentTable; Node<K,V> currentNode; int tableCapacity, index;
// Bước 1: Khởi tạo/Mở rộng mảng nếu cần
if ((currentTable = table) == null || (tableCapacity = currentTable.length) == 0)
tableCapacity = (currentTable = resize()).length;
// Bước 2: Xác định vị trí và chèn nếu bucket rỗng
if ((currentNode = currentTable[index = (tableCapacity - 1) & hash]) == null)
currentTable[index] = newNode(hash, key, value, null);
else {
Node<K,V> existingEntry; K k;
// Bước 3: Kiểm tra khóa trùng tại đầu bucket
if (currentNode.hash == hash &&
((k = currentNode.key) == key || (key != null && key.equals(k))))
existingEntry = currentNode;
// Bước 4: Nếu là cây Đỏ-Đen
else if (currentNode instanceof TreeNode)
existingEntry = ((TreeNode<K,V>)currentNode).putTreeVal(this, currentTable, hash, key, value);
// Bước 5: Nếu là danh sách liên kết
else {
for (int binCounter = 0; ; ++binCounter) {
if ((existingEntry = currentNode.next) == null) {
currentNode.next = newNode(hash, key, value, null);
// Chuyển đổi sang cây Đỏ-Đen nếu danh sách quá dài
if (binCounter >= TREEIFY_THRESHOLD - 1) // TREEIFY_THRESHOLD mặc định là 8
treeifyBin(currentTable, hash);
break;
}
// Nếu tìm thấy khóa trùng trong danh sách
if (existingEntry.hash == hash &&
((k = existingEntry.key) == key || (key != null && key.equals(k))))
break;
currentNode = existingEntry;
}
}
if (existingEntry != null) { // Khóa đã tồn tại
V oldValue = existingEntry.value;
if (!onlyIfAbsent || oldValue == null)
existingEntry.value = value; // Ghi đè giá trị
afterNodeAccess(existingEntry);
return oldValue;
}
}
++modCount;
// Bước 6: Kiểm tra và thay đổi kích thước nếu vượt quá ngưỡng
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
3. Cơ chế thay đổi kích thước (Resizing)
Cơ chế thay đổi kích thước (resize) là quá trình mở rộng mảng bên trong của HashMap khi nó không còn đủ chỗ cho các phần tử mới. Điều này xảy ra khi số lượng phần tử thực tế (size) vượt quá threshold. HashMap sẽ tạo một mảng mới có kích thước gấp đôi mảng cũ, sau đó di chuyển tất cả các phần tử từ mảng cũ sang mảng mới.
Điểm cải tiến đáng chú ý trong JDK 8 so với JDK 7 nằm ở cách các phần tử được di chuyển sang mảng mới. Do kích thước mảng mới luôn là gấp đôi (tức là một lũy thừa của 2), vị trí mới của một phần tử trong mảng mới sẽ chỉ có hai khả năng: hoặc là vẫn ở chỉ số cũ, hoặc là ở chỉ số cũ cộng thêm kích thước mảng cũ (oldCap).
Cụ thể, khi kích thước mảng tăng gấp đôi từ n lên 2n, phép tính chỉ số mới hash & (2n - 1) có thể được xem xét dựa trên bit cao nhất mới được thêm vào mặt nạ (mask) (2n - 1). Nếu bit này là 0, chỉ số mới vẫn là hash & (n - 1) (tức là chỉ số cũ). Nếu bit này là 1, chỉ số mới sẽ là hash & (n - 1) + n (tức là chỉ số cũ cộng oldCap).
Nhờ tối ưu hóa này, HashMap trong JDK 8 không cần tính toán lại toàn bộ giá trị băm cho từng phần tử. Thay vào đó, nó chỉ cần kiểm tra một bit cụ thể trong giá trị băm ban đầu của phần tử để xác định vị trí mới. Điều này giúp phân tán các phần tử trong các danh sách liên kết một cách đồng đều vào các bucket mới mà không tốn kém về mặt tính toán. Hơn nữa, không giống như JDK 7, thứ tự của các phần tử trong danh sách liên kết không bị đảo ngược trong quá trình thay đổi kích thước ở JDK 8.
Dưới đây là một cái nhìn đơn giản về phần quan trọng trong mã nguồn resize() của JDK 8:
final Node<K,V>[] resize() {
Node<K,V>[] oldTable = table;
int oldCapacity = (oldTable == null) ? 0 : oldTable.length;
int oldThreshold = threshold;
int newCapacity, newThreshold = 0;
if (oldCapacity > 0) {
if (oldCapacity >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTable;
}
else if ((newCapacity = oldCapacity << 1) < MAXIMUM_CAPACITY &&
oldCapacity >= DEFAULT_INITIAL_CAPACITY)
newThreshold = oldThreshold << 1; // Tăng gấp đôi ngưỡng
}
// ... xử lý các trường hợp khởi tạo ban đầu ...
threshold = newThreshold; // Cập nhật ngưỡng mới
Node<K,V>[] newTable = (Node<K,V>[])new Node[newCapacity];
table = newTable; // Gán mảng mới
if (oldTable != null) {
// Di chuyển các phần tử từ mảng cũ sang mảng mới
for (int j = 0; j < oldCapacity; ++j) {
Node<K,V> currentNode;
if ((currentNode = oldTable[j]) != null) {
oldTable[j] = null; // Giải phóng tham chiếu cũ
if (currentNode.next == null) // Nếu chỉ có 1 phần tử
newTable[currentNode.hash & (newCapacity - 1)] = currentNode;
else if (currentNode instanceof TreeNode) // Nếu là cây Đỏ-Đen
((TreeNode<K,V>)currentNode).split(this, newTable, j, oldCapacity);
else { // Xử lý danh sách liên kết
Node<K,V> lowHead = null, lowTail = null; // Cho các phần tử giữ nguyên vị trí
Node<K,V> highHead = null, highTail = null; // Cho các phần tử chuyển vị trí
Node<K,V> nextNode;
do {
nextNode = currentNode.next;
if ((currentNode.hash & oldCapacity) == 0) { // Kiểm tra bit để xác định vị trí mới
if (lowTail == null) lowHead = currentNode;
else lowTail.next = currentNode;
lowTail = currentNode;
} else {
if (highTail == null) highHead = currentNode;
else highTail.next = currentNode;
highTail = currentNode;
}
} while ((currentNode = nextNode) != null);
// Đặt các danh sách vào vị trí mới trong mảng
if (lowTail != null) {
lowTail.next = null;
newTable[j] = lowHead;
}
if (highTail != null) {
highTail.next = null;
newTable[j + oldCapacity] = highHead;
}
}
}
}
}
return newTable;
}
An toàn luồng (Thread Safety)
HashMap không an toàn cho môi trường đa luồng. Việc sử dụng HashMap trong các ứng dụng đa luồng mà không có cơ chế đồng bộ hóa phù hợp có thể dẫn đến các lỗi nghiêm trọng, bao gồm vòng lặp vô hạn (infinite loop) trong quá trình truy xuất dữ liệu (ví dụ: khi gọi get()).
Lỗi vòng lặp vô hạn thường xảy ra trong JDK 7 do cách phương thức transfer() xử lý việc di chuyển các phần tử trong quá trình thay đổi kích thước. Khi nhiều luồng cùng cố gắng thay đổi kích thước HashMap đồng thời, các con trỏ next trong danh sách liên kết có thể bị thao tác sai cách, tạo thành một chuỗi vòng lặp (circular linked list). Nếu một luồng sau đó cố gắng duyệt qua danh sách này, nó sẽ bị kẹt trong một vòng lặp vô hạn.
Ví dụ minh họa vấn đề này trong JDK 7:
public class ConcurrentHashMapIssue {
private static HashMap<Integer, String> testMap = new HashMap<>(2, 0.75f); // Kích thước ban đầu 2, threshold 1.5
public static void main(String[] args) throws InterruptedException {
testMap.put(5, "Value for 5"); // Đặt phần tử đầu tiên
// threshold = 2 * 0.75 = 1.5. Sau khi put(5, ...), size = 1.
// Khi put() phần tử thứ 2, size sẽ là 2, vượt ngưỡng 1.5, cần resize.
// Luồng 1 cố gắng thêm phần tử gây resize
new Thread("Thread 1") {
public void run() {
testMap.put(7, "Value for 7"); // Sẽ gây resize
System.out.println("Thread 1 map: " + testMap);
}
}.start();
// Luồng 2 cố gắng thêm phần tử gây resize
new Thread("Thread 2") {
public void run() {
testMap.put(3, "Value for 3"); // Cũng sẽ gây resize
System.out.println("Thread 2 map: " + testMap);
}
}.start();
// Đợi các luồng kết thúc (hoặc cố gắng lấy giá trị sau đó)
Thread.sleep(100);
// Nếu một luồng bị kẹt trong vòng lặp, lệnh get này sẽ không bao giờ trả về
// testMap.get(11); // Ví dụ: khóa không tồn tại nhưng có thể gây vòng lặp vô hạn nếu va chạm
System.out.println("Final map state: " + testMap);
}
}
Trong ví dụ trên, khi cả hai luồng cùng cố gắng gọi put() sau khi HashMap đã chứa 1 phần tử, cả hai đều có thể kích hoạt quá trình thay đổi kích thước đồng thời. Nếu quá trình này không được đồng bộ hóa, các con trỏ next trong danh sách liên kết có thể bị xáo trộn, dẫn đến việc tạo thành vòng lặp. Khi một luồng khác cố gắng tìm kiếm một khóa (ví dụ: map.get(someKey)), nó có thể đi vào vòng lặp vô hạn khi duyệt qua danh sách bị hỏng.
Để tránh các vấn đề về an toàn luồng, trong môi trường đa luồng, bạn nên sử dụng ConcurrentHashMap thay cho HashMap. ConcurrentHashMap được thiết kế để cung cấp hiệu suất cao trong môi trường đồng thời.
So sánh hiệu suất giữa JDK 8 và JDK 7
Hiệu suất của HashMap phụ thuộc nhiều vào chất lượng của hàm băm của khóa. Nếu tất cả các khóa có chỉ số băm khác nhau (phân tán lý tưởng), thao tác get() có độ phức tạp thời gian là O(1). Tuy nhiên, nếu hàm băm kém, dẫn đến nhiều va chạm và danh sách liên kết dài, độ phức tạp có thể lên tới O(n). JDK 8 đã cải thiện điều này bằng cách giới thiệu cây Đỏ-Đen, giảm độ phức tạp trong trường hợp xấu nhất xuống O(log n).
Trường hợp hàm băm phân tán tốt
Chúng ta sẽ sử dụng một lớp khóa (Key) có hàm hashCode() tốt, nghĩa là mỗi khóa có một giá trị băm duy nhất:
class UniqueKey implements Comparable<UniqueKey> {
private final int value;
UniqueKey(int value) {
this.value = value;
}
@Override
public int compareTo(UniqueKey other) {
return Integer.compare(this.value, other.value);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
UniqueKey uniqueKey = (UniqueKey) o;
return value == uniqueKey.value;
}
@Override
public int hashCode() {
return value; // Hàm hashCode lý tưởng
}
}
// Lớp hỗ trợ để cache các đối tượng UniqueKey nhằm tránh khởi tạo lặp lại
public class KeyFactory {
public static final int MAX_KEY_VALUE = 10_000_000;
private static final UniqueKey[] KEY_CACHE = new UniqueKey[MAX_KEY_VALUE];
static {
for (int i = 0; i < MAX_KEY_VALUE; ++i) {
KEY_CACHE[i] = new UniqueKey(i);
}
}
public static UniqueKey getUniqueKey(int value) {
return KEY_CACHE[value];
}
}
Thực hiện thử nghiệm với các kích thước HashMap khác nhau (1, 10, 100, ..., 10,000,000) và đo thời gian truy xuất:
public class HashMapPerformanceTest {
static void measureGetPerformance(int mapSize) {
HashMap<UniqueKey, Integer> testMap = new HashMap<>(mapSize);
for (int i = 0; i < mapSize; ++i) {
testMap.put(KeyFactory.getUniqueKey(i), i);
}
long startTime = System.nanoTime();
for (int i = 0; i < mapSize; i++) {
testMap.get(KeyFactory.getUniqueKey(i));
}
long endTime = System.nanoTime();
System.out.println("Map size: " + mapSize + ", Time taken: " + (endTime - startTime) + " ns");
}
public static void main(String[] args) {
System.out.println("--- Performance with Good Hash Code ---");
for (int i = 10; i <= 10_000_000; i *= 10) {
measureGetPerformance(i);
}
}
}
Trong trường hợp hàm băm tốt, hiệu suất của JDK 8 thường cao hơn JDK 7, đôi khi lên tới hơn 15%. Tuy nhiên, vì các va chạm băm là hiếm, lợi ích từ cây Đỏ-Đen trong JDK 8 không thực sự nổi bật ở đây.
Trường hợp hàm băm phân tán rất kém
Bây giờ, hãy thử nghiệm với một lớp Key mà tất cả các thể hiện đều trả về cùng một giá trị hashCode. Đây là kịch bản tồi tệ nhất cho HashMap:
class BadHashKey implements Comparable<BadHashKey> {
private final int value;
BadHashKey(int value) {
this.value = value;
}
@Override
public int compareTo(BadHashKey other) {
return Integer.compare(this.value, other.value);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
BadHashKey badHashKey = (BadHashKey) o;
return value == badHashKey.value;
}
@Override
public int hashCode() {
return 1; // Hàm hashCode kém, luôn trả về 1
}
}
// Lớp hỗ trợ để cache các đối tượng BadHashKey
public class BadKeyFactory {
public static final int MAX_KEY_VALUE = 10_000_000;
private static final BadHashKey[] KEY_CACHE = new BadHashKey[MAX_KEY_VALUE];
static {
for (int i = 0; i < MAX_KEY_VALUE; ++i) {
KEY_CACHE[i] = new BadHashKey(i);
}
}
public static BadHashKey getBadHashKey(int value) {
return KEY_CACHE[value];
}
}
Chạy lại thử nghiệm với BadHashKey:
public class HashMapPerformanceTestBadHash {
static void measureGetPerformance(int mapSize) {
HashMap<BadHashKey, Integer> testMap = new HashMap<>(mapSize);
for (int i = 0; i < mapSize; ++i) {
testMap.put(BadKeyFactory.getBadHashKey(i), i);
}
long startTime = System.nanoTime();
for (int i = 0; i < mapSize; i++) {
testMap.get(BadKeyFactory.getBadHashKey(i));
}
long endTime = System.nanoTime();
System.out.println("Map size: " + mapSize + ", Time taken: " + (endTime - startTime) + " ns");
}
public static void main(String[] args) {
System.out.println("--- Performance with Bad Hash Code ---");
for (int i = 10; i <= 10_000_000; i *= 10) {
measureGetPerformance(i);
}
}
}
Kết quả cho thấy, khi kích thước HashMap tăng lên, thời gian thực thi trong JDK 7 tăng tuyến tính (O(n)), trong khi ở JDK 8, thời gian này tăng chậm hơn đáng kể, theo dạng logarit (O(log n)). Sự khác biệt này là do cơ chế chuyển đổi danh sách liên kết thành cây Đỏ-Đen của JDK 8, giúp duy trì hiệu suất ngay cả trong trường hợp va chạm băm tồi tệ nhất. Điều này cũng nhấn mạnh tầm quan trọng của việc thiết kế một hàm hashCode() tốt.
Tóm tắt
HashMap là một công cụ mạnh mẽ trong Java, và việc hiểu rõ hoạt động bên trong của nó là rất quan trọng. Dưới đây là những điểm chính:
- Thao tác thay đổi kích thước (resize) rất tốn kém về hiệu năng. Do đó, khi khởi tạo
HashMap, nếu có thể ước tính được kích thước cần thiết, hãy cung cấp một dung lượng ban đầu hợp lý để tránh các lần thay đổi kích thước không cần thiết. - Tỷ lệ tải (
loadFactor) có thể được điều chỉnh, nhưng khuyến nghị không nên thay đổi giá trị mặc định (0.75) trừ khi có lý do rất đặc biệt. HashMapkhông an toàn luồng. Tuyệt đối không sử dụngHashMaptrong môi trường đa luồng mà không có cơ chế đồng bộ hóa phù hợp. Thay vào đó, hãy sử dụngConcurrentHashMapđể đảm bảo an toàn và hiệu suất cao trong môi trường đồng thời.- JDK 8 đã mang lại những cải tiến đáng kể cho
HashMapthông qua việc tích hợp cây Đỏ-Đen và tối ưu hóa quá trình thay đổi kích thước, giúp cải thiện hiệu suất đáng kể, đặc biệt trong các trường hợp va chạm băm cao.