Sử dụng Map hiệu quả trong Java

Chào mừng các bạn đã quay trở lại với thachleblog. Ở các bài trước, mình đã có chia sẻ về ArrayList, LinkedList, Stack và Queue. Bài viết hôm nay, mình sẽ giới thiệu về Map, một trong những cấu trúc dữ liệu được sử dụng phổ biến và hiệu quả nhất trong Java. Hy vọng qua bài viết này các bạn sẽ hiểu thêm về Map và có thể sử dụng Map hiệu quả hơn. Nào, chúng ta cùng bắt đầu nhé.

Giới thiệu

Map là interface thiết kế để lưu trữ cấu trúc dữ liệu theo dạng (key, value). Cả key và value đều là object (không chấp nhận kiểu dữ liệu primitives). Mỗi key sẽ tương ứng với duy nhất 1 value. Các implementation của Map bao gồm HashMap, HashTable, LinkedHashMap, ConcurrentHashMap, TreeMap… Bài viết hôm nay mình sẽ chủ yếu đi sâu vào cấu trúc HashMap.

Cấu trúc

Cấu trúc dữ liệu của Map dựa vào Array và LinkedList. Mỗi value được lưu trữ trong array dựa vào hash value. Khi một phần tử thêm vào có cùng hash value, phần tử này sẽ chiếm chỗ phần tử cũ và phần tử cũ sẽ được linked đến phần tử mới này.

Cơ chế put and get

Khi chúng ta thêm một phần tử vào Map, phương thức hash code sẽ “hash” key và tạo ra một giá trị (hash code). Giá trị này sẽ dùng để xác định bucket để lưu trữ. Tương tự, method equal() được sử dụng để xác định chính xác vị trí lưu trữ chính xác của phần tử. Do key là thuộc tính duy nhất nên khi thêm phần tử có key trùng với phần tử cũ. Value của key mới sẽ ghi đè lên value key cũ. (Xem thêm bài về hashCode() và equal() tại đây)

Lưu ý hash map chấp nhận key và value null.

Tương tự, khi get một phần tử, phương thức hashCode() và equal() cũng được sử dụng để xác định vị trí của phần tử trong Map.

Cấu trúc lưu trữ của HashMap để put và get

Cấu trúc lưu trữ của HashMap để put và get

Độ phức tạp của phương thức put() và get() là O(1).

Một vài API thường dùng

  • containsKey(Object key): trả và true nếu Map có chứa key, ngược lại trả về false

  • get (Object key): trả về giá trị của key nếu key tồn tại, ngược lại trả về null

  • put (K key, V value): thêm vào một phần tử có key và value tương ứng

Duyệt map

Các bạn có thể xem các cách duyệt Map tại đây, lưu ý là duyệt, các phần tử của Hash Map sẽ không đúng thứ tự như khi thêm vào. Nếu cần Map khi duyệt các phần tử đúng thứ tự khi thêm vào các bạn có thể sử dụng LinkedHashMap.

Sử dụng

Yêu cầu

Giả sử mình cần lưu trữ danh sách danh bạ với tên tương ứng với số điện thoại. Khi nhập tên sẽ in ra số điện thoại tương ứng. Ngược lại in là “Không tìm thấy”.

Input:

3
sam 99912222
tom 11122222
harry 12299933
sam
edward
harry

Output:

sam=99912222
“Không tìm thấy”
harry=12299933

Giải thuật

– Mình sẽ sử dụng method put để thêm tên – số điện thoại vào Map. Sau đó có thể sử dụng:

+ containsKey(String tên) để kiểm tra số điện thoại có tồn tại hay không, nếu có, dùng get(String tên) để in ra, ngược lại in “Không tìm thấy”.

Hoặc

+ get(String tên) để lấy ra số điện thoại. Kiểm tra kết quả nếu khác null in ra giá trị, ngược lại in “Không tìm thấy”

import java.util.Scanner;
 
/**
 *
 * @author thachlp
 */
import java.util.*;
 
class Solution{
    public static void main(String []argh){
        Map<String, String> phoneAddress = new HashMap<>();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            String name = in.next();
            int phone = in.next();
            phoneAddress.put(name, phone);
 
        }
        while (in.hasNext()) {
            String s = in.next();
            //cach 1
            if(phoneAddress.containsKey(s)){
                System.out.printf("%s=%d\n", s, phoneAddress.get(s));
            } else {
                System.out.println("Không tìm thấy");
            }
 
            //cach 2            
            String number = phoneAddress.get(s);
            if (number != null) {
                System.out.printf("%s=%d\n", s, phoneAddress.get(s));
            } else {
                System.out.println("Không tìm thấy");
            }
        }
        in.close();
    }
}

 

Kết quả 2 cách là như nhau. Tuy nhiên, lưu ý về performence.

Ở cách 1, Map thực hiện 2 thao tác là check (containsKey) và get, nên sẽ tốn resource hơn so với cách 2 là get và so sánh String. Với số lượng phần tử lên đến 100k phần tử, tốc độ chênh lệch rõ.

Dù vậy, cũng cần lưu ý là với giá trị là null, kết quả của cách 2 sẽ là “Không tìm thấy”. Cách 1 sẽ trả về kết quả là true.

Vừa rồi là phần giới thiệu về Map và một vài lưu ý. Về Map thì cũng có rất nhiều thứ để nói. Tạm thời hôm nay mình nói nhiêu đây thôi. Hôm nào có vấn đề gì hay ho mình sẽ nói tiếp. Hẹn gặp lại các bạn ở các bài viết sau nhé. Mọi góp ý vui lòng comment bên dưới, mình sẽ follow. Thanks.

Xem thêm:

https://docs.oracle.com/javase/7/docs/api/java/util/Map.html

Tham gia bình luận