HashMap là một trong những cấu trúc dữ liệu phổ biến được sử dụng hàng ngày của các lập trình viên.
Trong bài viết này, chúng ta sẽ xem xét nó là gì và tại sao và làm thế nào để sử dụng HashMap một cách hiệu quả nhất.
Ví dụ: Bạn đang có 1 shop quần áo với rất nhiều mặt hàng và sản phẩm. Để nhớ được tất cả giá tiền của các sản phẩm này bạn sẽ phải viết ra danh sách sản phẩm và giá tương ứng. Bất cứ khi nào có khách hỏi mua 1 sản phẩm bạn phải nhìn vào danh sách để tìm giá của chúng.
Nếu tên của các sản phẩm không viết theo thứ tự từ điển thì sẽ mất nhiều thời gian để tìm kiếm mỗi lần bán. Nếu xét về góc độ thuật toán thì độ phức tạp của việc này sẽ là O(n). Nhưng nếu tên các sản phầm được viết theo thứ tự từ điển thì độ phức tạp sẽ giảm xuống còn log n, tất nhiên là O(log n) sẽ tốt hơn là O(n).
Mặc dù O(log n) có thể xem xét là ít thời gian nhưng nó vẫn chưa tối ưu. Để tốt nhất với trường hợp này có lẽ là bạn nên nhớ tất cả những sản phẩm này, chỉ cần người mua hỏi là bạn có thể trả lời luôn.
Kịch bản này có thể sử dụng HashMap để giải quyết, chúng ta có thể nhập tên của sản phẩm và giá của chúng trong HashMap tương ứng là key và value trong HashMap, HashMap sẽ trả về value tương ứng với key với thời gian rất nhanh.
HashMap là gì? HashMap là 1 cấu trúc dữ liệu key-value, độ phức tạp cả get và put là O(1)
Thử 1 ví dụ:
// tạo map java 11
var productPrice = new HashMap<String, Double>();
//java 8
Map<String, Double> productPrice = new HashMap<>();
// thêm value, key và value tương ứng
productPrice.put(“Gạo”, 6.9);
productPrice.put(“Bột mỳ”, 3.9);
productPrice.put(“Đường”, 4.9);
Hiện tại chúng ta cần truy cập giá của sản phẩm với key(tên sản phẩm) từ HashMap. HasMap cung cấp hàm get để thực hiện việc này.
//get value
Double egg = productPrice.get(“Trứng”);
System.out.println(“Giá của trứng là: ” + Trứng);
Trên đây chỉ là các chứ năng cơ bản của HashMap, chúng ta sẽ đi sâu hơn và cách sử dụng HashMap ở phía dưới của bài này.
Hiển thị tất cả các key và value của HashMap
Có số cách để in tất cả các key và value của Hashmap.
- Hiển thỉ tất cả các key
Set<String> keys = productPrice.keySet();
//show all keys
for (String key : keys) {
System.out.println(key);
}
Hay
keys.forEach(key -> System.out.println(key));
Mình thích dùng forEach cùng với việc sử dụng lambda cho ngắn gọn.
2. Hiển thị tất cả các value.
Collection<Double> values = productPrice.values();
values.forEach(value -> System.out.println(value));
3. Hiển thị tất cả các key và value cùng nhau
Set<Map.Entry<String, Double>> entries = productPrice.entrySet();
for (Map.Entry<String, Double> entry : entries) {
System.out.print(“key: “+ entry.getKey());
System.out.println(“, Value: “+ entry.getValue());
}
Hay có thể sử dụng forEach lamda.
productPrice.forEach((key, value) -> {
System.out.print(“key: “+ key);
System.out.println(“, Value: “+ value);
});
Mình sẽ cho 1 ví dụ để các bạn thấy được tính hữu ích của việc sử dụng HashMap, đó là ví dụ về việc tạo dãy số Fibonacci.
Chuỗi Fiboncci là một chuỗi số rất nổi tiếng mà ai cũng nghe qua. Công thức của nó như sau.
f(n) = f(n-1) + f(n-2)
Chúng ta sẽ minh họa ví dụ tạo ra 50 số trong dãy fibonacci bằng 2 cách khác nhau:
Cách 1: Không dùng HashMap – Dùng hàm fibonacci1 trong hàm main.
Cách 2: Sử dụng HashMap- Dùng hàm fibonacci trong hàm main.
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
public class Fibonacci {
private Map<Integer, BigInteger> memoizeHashMap = new HashMap<>();
{
memoizeHashMap.put(0, BigInteger.ZERO);
memoizeHashMap.put(1, BigInteger.ONE);
memoizeHashMap.put(2, BigInteger.ONE);
}
private BigInteger fibonacci(int n) {
if (memoizeHashMap.containsKey(n)) {
return memoizeHashMap.get(n);
} else {
BigInteger result = fibonacci(n - 1).add(fibonacci(n - 2));
memoizeHashMap.put(n, result);
return result;
}
}
private BigInteger fibonacci1(int n) {
if (n == 1 || n == 2) {
return BigInteger.ONE;
}
return fibonacci1(n - 1).add(fibonacci1(n - 2));
}
public static void main(String[] args) {
Fibonacci fibonacci = new Fibonacci();
long begin = System.currentTimeMillis();
for (int i = 1; i < 50; i++) {
System.out.println(fibonacci.fibonacci1(i));
}
long end= System.currentTimeMillis();
long count = end - begin;
System.out.println("count = end - begin: " + count);
//System.out.println("Begin " +lbegin);
}
}
Ghi chú: Hàm put() sẽ thay thế value hiện tại nếu key đã tồn tại trong map.
Kiểm tra thời gian thực hiện:
Với cấu hình máy của mình để tạo ra được 40 số trong dãy Fibonaci thì cần tầm 5- 6s còn dùng HashMap thời gian chỉ tính bằng milisecond, đến đây thấy sự khác biệt rất lớn.
Tiếp theo chúng ra sẽ xem xét một số hàm
So sánh: computeIfAbsent() và puIfAbsent()
Chúng ta có thể viết gọn lại đoạn code trên bằng việc sử dụng các hàm này như sau.
private BigInteger fibonacci(int n) {
return memoizeHashMap.computeIfAbsent(n,
(key) -> fibonacci(n – 1).add(fibonacci(n – 2)));
}
Hàm này có 2 tham số. Một là key và tham số còn lại là 1 hàm, ý tưởng là nếu key đã có trong Map thì nó sẽ trả lại value, ngược lại nó sẽ tính toán và thêm giá trị vào map.
Có 1 hàm khác tên là putIfAbsent() hàm này sẽ thực hiện thêm giá trị vào Map nếu chưa có trong map.
productPrice.putIfAbsent(“Fish”, 4.5);
Sự khác nhau giữa putIfAbsent() và computeIfAbsent()
Phần này các bạn phải để ý để phân biệt được sự khác nhau.
Khác nhau 1
computeIfAbsent có 1 tham số là là hàm mapping function, hàm này được gọi khi key là null hoặc key chưa tồn tại trong map.
putIfAbsent tham số là giá trị truyền vào.
Khác nhau 2
computeIfAbsent:Trả về giá trị hiện tại(đã tồn tại hay do tính toán) với 1 key chỉ định hoặc null nếu giá trị tính toán là null.
putIfAbsent trả về giá trị có key trùng với key nhâp vào hoặc null nếu key chưa có.
Vì vậy cả 2 hàm nếu key đã tồn tại sẽ trả về giá trị của key đã có trong map nhưng nếu key chưa có trong map thì computeIfAbsent sẽ trả về giá trị tính toán còn putIfAbsent sẽ trả vể null.
Khác nhau 3
computeIfAbsent sẽ không thêm vào 1 giá trị null nếu key là null.
putIfAbsent sẽ thêm vào giá trị nếu key là null thậm chí nếu value là null.
compute() và computeIfPresent()
computeIfPresent sẽ thực hiện tính toán để lấy value sau đó thêm vào HashMap trong trường hợp key đã có ngược lại hàm compute sẽ thực hiện tương tự mặc dù key có tồn tại hay không?
getOrDefault()
Trong một số trường hợp, áp dụng trong trường hợp lấy giá trị trong 1 map nhưng không có nó sẽ trả về giá trị mặc định
productPriceMap.getOrDefault(“Fish”, 29.4);
Tổng kết,
Qua bài này mình muốn giới thiệu 1 số tính năng hữu ích củ HashMap, bài viết có tham khảo trên 1 số thông tin từ các nguồn khác nhau. Nếu các bạn thấy vấn đề nào chưa đúng vui lòng comment để mình bổ sung. Cảm ơn các bạn.
