Hướng dẫn và ví dụ Java HashMap
1. HashMap
HashMap<K,V> là một lớp nằm trong nền tảng tập hợp của Java (Java Collection Framework), và implements interface Map<K,V>. HashMap hỗ trợ đầy đủ tất cả các tính năng được đặc tả trong interface Map bao gồm cả các tính năng tuỳ chọn.
HashMap cho phép lưu trữ các cặp khoá và giá trị (key & value), các khoá không thể trùng lặp.
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
- Map
- TreeMap
- WeakHashMap
- LinkedHashMap
- IdentityHashMap
- ConcurrentHashMap
- ConcurrentSkipListMap
- EnumMap
Các đặc điểm của HashMap:
- HashMap chứa các cặp khoá và giá trị.
- Nó có thể có một khóa null và nhiều giá trị null.
- HashMap không duy trì thứ tự với các khoá.
- Nó hoạt động trên kỹ thuật băm (hashing technique). (Xem thêm giải thích về kỹ thuật này ở phần dưới).
Hãy đến với một ví dụ đơn giản, sử dụng HashMap để mô phỏng một danh bạ điện thoại, trong đó số điện thoại là khoá (key) và tên người sở hữu là giá trị (value). Các khoá sẽ không bao giờ trùng lặp.
HashMapEx1.java
package org.o7planning.hashmap.ex;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
public class HashMapEx1 {
public static void main(String[] args) {
Map<String, String> phonebook = new HashMap<String, String>();
phonebook.put("01000005", "Tom");
phonebook.put("01000002", "Jerry");
phonebook.put("01000003", "Tom");
phonebook.put("01000004", "Donald");
Set<String> phoneNumbers = phonebook.keySet();
for (String phoneNumber : phoneNumbers) {
String name = phonebook.get(phoneNumber);
System.out.println("Phone Number: " + phoneNumber + " ==> Name: " + name);
}
}
}Output:
Phone Number: 01000004 ==> Name: Donald
Phone Number: 01000003 ==> Name: Tom
Phone Number: 01000005 ==> Name: Tom
Phone Number: 01000002 ==> Name: JerryVề cơ bản tất cả các tính năng của HashMap đều tuân thủ theo đặc tả của interface Map, vì vậy bạn có thể đọc bài viết về Map dưới đây để hiểu thêm về cách sử dụng HashMap:
Xem thêm: Lớp WeakHashMap là một biến thể tiết kiệm bộ nhớ của lớp HashMap. Các ánh xạ không thực sự cần thiết sẽ bị loại bỏ một cách tự động bởi Java Garbage Collector (Trình gom rác của Java)
2. HashMap làm việc thế nào?
Các nhà thiết kế Java đã sử dụng kỹ thuật băm (hashing technique) cho lớp HashMap để lưu trữ dữ liệu và nâng cao hiệu xuất của nó, và bây giờ chúng ta sẽ xem kỹ thuật này được sử dụng thế nào trong HashMap. Về cơ bản chúng ta phân tích xem điều gì sẽ xẩy ra khi gọi các phương thức HashMap.put(K,V), HashMap.get(K) và HashMap.remove(key).
HashMap<K,V> quản lý một mảng các đối tượng Node<K,V>, mảng này sẽ được thay thế bởi một mảng khác có kích thước lớn hơn nếu tất cả các phần tử của nó đã được gán giá trị.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}Lớp Node<K,V> bao gồm 4 trường (field). Và trường next là một tham chiếu tới đối tượng Node tiếp theo, nó có thể không phải là phần tử tiếp theo trong mảng.
static class Node<K,V> implements Map.Entry<K,V> {
int hashcode;
K key;
V value;
Node<K,V> next;
}
HashMap đảm bảo rằng các Node cùng một hashcode (mã băm) sẽ có tham chiếu liên tiếp nhau, điều này giúp nó nhanh chóng tìm được tất cả các Node có cùng hashcode được chỉ định.
HashMap.put(key,value)
Khi gọi phương thức HashMap.put(key,value), HashMap sẽ tìm kiếm các Node với thoả mãn điều kiện node.hashcode == hash(key). Nếu không tìm thấy thì một đối tượng Node mới sẽ được gán vào mảng. (Xem hình dưới)
Ngược lại, HashMap sẽ nhanh chóng xác định được các Node liên tiếp nhau thoả mãn điều kiện node.hashcode == hash(key) và thu hẹp đáng kể phạm vi các Node cần tìm kiếm theo key.
- Nếu tìm thấy Node tương ứng với key, giá trị mới sẽ được gán cho Node.value.
- Ngược lại, một đối tượng Node mới sẽ được tạo ra và gán vào mảng (Xem hình dưới).
HashMap.get(key)
Khi phương thức HashMap.get(key) được gọi, HashMap sẽ nhanh xác định được các Node liên tiếp nhau thoả mãn điều kiện node.hashcode == hash(key), điều này thu hẹp đáng kể phạm vi các Node cần tìm kiếm theo key. Tiếp theo nó tìm kiếm Node theo key và trả về node.value nếu tìm thấy, ngược lại nó sẽ trả về null.
HashMap.remove(key)
Kết luận: Phương thức Object.hashcode() trả về hashcode (mã băm) của một đối tượng, giá trị này theo mặc định được tạo ra bởi JVM, và rất hiếm khi trùng lặp. Các lớp con của lớp Object có thể ghi đè (override) phương thức này để trả về hashcode tuỳ biến.HashMap sử dụng kỹ thuật băm (hashing technique) giúp nâng cao hiệu xuất của nó, vì so sánh 2 số bao giờ cũng nhanh hơn so với việc so sánh 2 đối tượng.
Các hướng dẫn Java Collections Framework
- Hướng dẫn và ví dụ Java List
- Hướng dẫn và ví dụ Java Iterator
- Hướng dẫn và ví dụ Java ListIterator
- Hướng dẫn và ví dụ Java ArrayList
- Hướng dẫn và ví dụ Java CopyOnWriteArrayList
- Hướng dẫn và ví dụ Java LinkedList
- Hướng dẫn và ví dụ Java Set
- Hướng dẫn và ví dụ Java SortedSet
- Hướng dẫn và ví dụ Java NavigableSet
- Hướng dẫn và ví dụ Java TreeSet
- Hướng dẫn và ví dụ Java CopyOnWriteArraySet
- Hướng dẫn và ví dụ Java Queue
- Hướng dẫn và ví dụ Java Deque
- Hướng dẫn và ví dụ Java PriorityQueue
- Hướng dẫn và ví dụ Java BlockingQueue
- Hướng dẫn và ví dụ Java ArrayBlockingQueue
- Hướng dẫn và ví dụ Java PriorityBlockingQueue
- Hướng dẫn và ví dụ Java TransferQueue
- Hướng dẫn và ví dụ Java Map
- Hướng dẫn và ví dụ Java SortedMap
- Hướng dẫn và ví dụ Java NavigableMap
- Hướng dẫn và ví dụ Java HashMap
- Hướng dẫn và ví dụ Java TreeMap
- Hướng dẫn và ví dụ Java IdentityHashMap
- Hướng dẫn và ví dụ Java WeakHashMap
- Hướng dẫn sử dụng nền tảng tập hợp trong Java (Java Collection Framework)
Show More
