Map

 

A. Map Interface

Map là một interface trong Java được sử dụng để ánh xạ các cặp khóa-giá trị. Nó là một phần của gói java.util. Map không kế thừa từ Collection interface nhưng vẫn là một phần của cấu trúc dữ liệu tập hợp trong Java.

Một Map lưu trữ các phần tử dưới dạng các cặp khóa-giá trị, trong đó mỗi khóa là duy nhất và không thể thay đổi. Giá trị có thể là bất kỳ đối tượng nào, bao gồm cả null, và một khóa chỉ có thể ánh xạ tới một giá trị duy nhất.

Một số triển khai phổ biến của interface Map:

1. Cấu trúc dữ liệu	Đặc điểm	Thời gian truy cập/Thêm/Xóa trung bình
   1. HashMap	Sử dụng bảng băm (hash table)	O(1)
   	Các phần tử không được sắp xếp theo bất kỳ thứ tự nào
   2. LinkedHashMap	Duy trì thứ tự chèn của các phần tử bằng danh sách liên kết	O(1)
   	Các phần tử được duy trì theo thứ tự chèn
   3. TreeMap	Sử dụng cây đỏ-đen (red-black tree) để lưu trữ và sắp xếp các phần tử	O(log n)
   	Các phần tử được sắp xếp theo thứ tự tăng dần của khóa

   Trong đó, HashMap và TreeMap được sử dụng phổ biến.

Dựa vào mục đích và chức năng của từng phương thức, chúng ta có thể phân loại các phương thức trong Map như sau:

Phương thức	Mô tả
1. Xử lý Phần Tử
put(K key, V value)	Thêm một cặp khóa-giá trị mới vào Map hoặc ghi đè giá trị nếu khóa đã tồn tại.
remove(Object key)	Xóa cặp khóa-giá trị tương ứng với khóa đã cho khỏi Map.
putAll(Map<? extends K,? extends V> m)	Thêm tất cả các cặp khóa-giá trị từ một Map đã cho vào Map hiện tại.
clear()	Xóa tất cả các cặp khóa-giá trị khỏi Map.
2. Truy Xuất và Kiểm Tra
get(Object key) getOrDefault(Object key, V defaultValue)	Trả về giá trị tương ứng với khóa đã cho, hoặc null nếu không tìm thấy khóa. Trả về giá trị tương ứng với key đã cho, hoặc defaultValue nếu không tìm thấy key.
containsKey(Object key)	Kiểm tra xem Map có chứa khóa đã cho không.
containsValue(Object value)	Kiểm tra xem Map có chứa giá trị đã cho không.
isEmpty()	Kiểm tra xem Map có rỗng không.
3. Thông Tin Về Map
size()	Trả về số lượng cặp khóa-giá trị trong Map.
4. Trả về Collection của Keys và Values
keySet()	Trả về một Set chứa tất cả các khóa có trong Map.
values()	Trả về một Collection chứa tất cả các giá trị có trong Map.
entrySet()	Trả về một Set chứa tất cả các cặp khóa-giá trị dưới dạng các đối tượng Map.Entry.
5. So Sánh và Kiểm Tra
equals(Object obj)	So sánh Map hiện tại với một Object khác.
hashCode()	Trả về mã băm của Map.
6. Iterating và Traversing
forEach(BiConsumer<? super K,? super V> action)	Duyệt qua tất cả các cặp khóa-giá trị của Map và thực thi một hành động cho mỗi cặp.

------

(*) Map.Entry interface

Interface Map.Entry trong Java có mục đích chính là đại diện cho một cặp key-value trong một Map. Bằng cách này, nó cung cấp một cách tiện lợi để làm việc với các phần tử trong Map theo cặp key-value.

Phương thức	Mô tả
getKey()	Trả về key tương ứng với cặp key-value này.
getValue()	Trả về giá trị tương ứng với cặp key-value này.
setValue(V value)	Thay thế giá trị tương ứng với cặp key-value này bằng giá trị được chỉ định.
equals(Object o)	So sánh đối tượng đã chỉ định với cặp key-value này để kiểm tra tính bằng nhau.
hashCode()	Trả về giá trị hash code cho cặp key-value này.
comparingByKey()	Trả về Comparator để so sánh Map.Entry theo key, sắp xếp theo thứ tự tự nhiên.
comparingByValue()	Trả về Comparator để so sánh Map.Entry theo value, sắp xếp theo thứ tự tự nhiên.
comparingByKey(Comparator<? super K> cmp)	Trả về Comparator để so sánh Map.Entry theo key, sử dụng Comparator được chỉ định.
comparingByValue(Comparator<? super V> cmp)	Trả về Comparator để so sánh Map.Entry theo value, sử dụng Comparator được chỉ định.

Ví dụ :

import java.util.*;

public class MapEntryExample {
    public static void main(String[] args) {
        // Tạo một Map đơn giản với key là String và value là Integer
        Map<String, Integer> map = new HashMap<>();
        map.put("apple", 10);
        map.put("banana", 20);
        map.put("orange", 30);

        // Lặp qua mỗi cặp key-value trong Map sử dụng for-each và sử dụng Map.Entry
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            // Lấy key và value từ mỗi cặp key-value
            String key = entry.getKey();
            Integer value = entry.getValue();

            // In ra key và value của mỗi cặp
            System.out.println("Key: " + key + ", Value: " + value);

            // Thực hiện một số thao tác khác trên cặp key-value nếu cần
            // Ví dụ: Kiểm tra điều kiện hoặc thay đổi giá trị value
            if (key.equals("banana")) {
                // Nếu key là "banana", thay đổi giá trị value thành 100
                entry.setValue(100);
            }
        }

        // In ra các cặp key-value sau khi thay đổi (nếu có)
        System.out.println("Map sau khi thay đổi:");
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }
    }
}

Output (với giá trị mới của key "banana"):

Key: apple, Value: 10
Key: banana, Value: 100
Key: orange, Value: 30
Map sau khi thay đổi:
Key: apple, Value: 10
Key: banana, Value: 100
Key: orange, Value: 30

B.HashMap

Một số điểm chính về HashMap:

1. Đặc Điểm	Mô Tả
   1. Bảng Băm	Triển khai dữ liệu bằng bảng băm, lưu trữ và truy xuất dữ liệu dựa trên giá trị băm của khóa.
   2. Khóa-Giá Trị	Mỗi phần tử là một cặp khóa-giá trị, khóa là duy nhất và không thay đổi, giá trị có thể là bất kỳ đối tượng nào.
   3. Không Thứ Tự	Không bảo đảm về thứ tự của các phần tử.
   4. Không Phần Tử Trùng Lặp	Mỗi khóa là duy nhất và không thể trùng lặp. Nếu thêm một cặp khóa-giá trị mới với một khóa đã tồn tại, giá trị cũ sẽ bị ghi đè bởi giá trị mới.
   5. Không Đồng Bộ	Không đồng bộ (Non-synchronized).
   6. Tối Ưu Tìm Kiếm	Thời gian truy cập gần như là O(1), giúp giảm thời gian xử lý trong các tác vụ liên quan đến dữ liệu lớn.
   Sử Dụng Phổ Biến	Được sử dụng rộng rãi để lưu trữ và quản lý dữ liệu theo cặp khóa-giá trị, đặc biệt trong trường hợp dữ liệu lớn.

Ví du :

import java.util.HashMap;

public class HashMapExample {
    public static void main(String[] args) {
        // Khởi tạo một HashMap để lưu trữ thông tin sinh viên
        HashMap<Integer, String> studentMap = new HashMap<>();

        // Thêm thông tin của các sinh viên vào HashMap
        studentMap.put(101, "John Smith");
        studentMap.put(102, "Emily Johnson");
        studentMap.put(103, "Michael Williams");
        studentMap.put(104, "Emma Brown");

        // Hiển thị thông tin của sinh viên có mã số 102
        System.out.println("Thông tin của sinh viên có mã số 102: " + studentMap.get(102));

        // Hiển thị tất cả các sinh viên trong HashMap
        System.out.println("\nDanh sách sinh viên:");
        for (Integer id : studentMap.keySet()) {
            String name = studentMap.get(id);
            System.out.println("Mã số: " + id + ", Tên: " + name);
        }

        // Xóa thông tin của sinh viên có mã số 103
        studentMap.remove(103);
        System.out.println("\nSinh viên có mã số 103 đã bị xóa.");

        // Hiển thị lại danh sách sinh viên sau khi xóa
        System.out.println("\nDanh sách sinh viên sau khi xóa:");
        for (Integer id : studentMap.keySet()) {
            String name = studentMap.get(id);
            System.out.println("Mã số: " + id + ", Tên: " + name);
        }
    }
}

Kết quả :

Thông tin của sinh viên có mã số 102: Emily Johnson

Danh sách sinh viên:
Mã số: 101, Tên: John Smith
Mã số: 102, Tên: Emily Johnson
Mã số: 103, Tên: Michael Williams
Mã số: 104, Tên: Emma Brown

Sinh viên có mã số 103 đã bị xóa.

Danh sách sinh viên sau khi xóa:
Mã số: 101, Tên: John Smith
Mã số: 102, Tên: Emily Johnson
Mã số: 104, Tên: Emma Brown

HashMap hoạt động như thế nào?

Cách hoạt động	Mô tả
HashMap sử dụng băm dữ liệu (hashing)	HashMap ánh xạ các key vào các bucket bằng cách tính toán giá trị băm (hash code) của key. Điều này giúp truy cập và tìm kiếm phần tử trong HashMap nhanh chóng (O(1) trung bình).
Interface Map.Entry	Interface này đại diện cho một cặp key-value trong HashMap. Các đối tượng Entry được sử dụng để lưu trữ mỗi phần tử trong HashMap.
Phương thức hashCode()	Khi sử dụng put(key, value), HashMap tính toán giá trị băm (hash code) của key để xác định vị trí (bucket) để lưu trữ đối tượng Entry.
Phương thức equals()	Phương thức này được sử dụng để so sánh hai key trong HashMap. Trong trường hợp xung đột hash (collision), nó giúp tìm ra đúng value tương ứng.
Ví dụ hoạt động	Khi ghi đè phương thức hashCode() và equals() trong lớp LangKey, tất cả các phần tử được thêm vào trong HashMap đều được xếp chung vào cùng một bucket, với cùng một value.

Ví dụ :

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class HashMapTest {
    public static void main(String[] args) {
        Map<LangKey, String> langMap = new HashMap<>();
        langMap.put(new LangKey(1, "EN"), "English");
        langMap.put(new LangKey(2, "VI"), "Vietnamese");
        langMap.put(new LangKey(3, "ES"), "Spanish");
        langMap.put(new LangKey(4, "JP"), "Japanese");
        langMap.put(null, "Japanese");

        System.out.println("Kích thước của langMap là: " + langMap.size());
        System.out.print("Các phần tử của langMap: ");
        for (LangKey key : langMap.keySet()) {
            System.out.print(langMap.get(key) + " ");
        }
        System.out.println("\nKích thước của langMap là: " + langMap.size());
    }
}

class LangKey {
    int index;
    String name;

    LangKey(int index, String name) {
        this.index = index;
        this.name = name;
    }

    @Override
    public int hashCode() {
        
        return 5;
    }

    @Override
    public boolean equals(Object obj) {
        
        return true;
    }
}

Dưới đây là bảng tóm tắt về lý do tại sao kích thước của HashMap chỉ có một và khi duyệt nó chỉ in ra phần tử cuối cùng trong 4 phần tử được thêm vào:

Lý do	Mô tả
Phương thức hashCode() luôn trả về 5	Trong lớp LangKey, phương thức hashCode() luôn trả về 5 cho mọi đối tượng. Điều này dẫn đến tình trạng mà tất cả các hash code được tính toán giống nhau cho các key khác nhau.
Tất cả các đối tượng Entry được lưu vào cùng một bucket	Do tất cả các hash code đều giống nhau, HashMap đặt tất cả các đối tượng Entry vào cùng một bucket. Điều này có nghĩa là tất cả các phần tử được lưu trữ trong cùng một vị trí trong HashMap.
Phương thức equals() luôn trả về true	Trong lớp LangKey, phương thức equals() luôn trả về true cho mọi đối tượng. Điều này dẫn đến tình trạng mà HashMap tin rằng mọi key là giống nhau và không xử lý việc ghi đè giá trị khi có các key trùng nhau.
Kết quả: chỉ có một phần tử và in ra phần tử cuối cùng	Vì tất cả các key được coi là giống nhau, và mỗi khi thêm một phần tử mới, nó ghi đè giá trị cũ. Do đó, chỉ có một phần tử cuối cùng được giữ lại trong HashMap. Khi duyệt qua, chỉ có phần tử cuối cùng này được in ra, do phần tử trước đó đã bị ghi đè.

C.LinkedHashMap

Một số điểm chính về LinkedHashMap:

1. 1. Duy trì các phần tử theo thứ tự chèn.

2. 2. Được triển khai bằng danh sách liên kết: sử dụng một danh sách liên kết nội bộ để duy trì thứ tự chèn của các phần tử.

3. 3. Không chứa phần tử trùng lặp.

4. 4. Không đồng bộ.

5. 5. Hiệu suất truy cập cao: cung cấp thời gian truy cập gần như là O(1) cho các phép tìm kiếm và truy xuất, nhưng với độ phức tạp thêm và xóa phần tử nhẹ hơn so với HashMap.

LinkedHashMap thường được sử dụng khi bạn cần duy trì thứ tự chèn của các phần tử trong bản ghi, cũng như khi bạn cần truy cập dữ liệu theo thứ tự chúng được thêm vào.

D.TreeMap

Một số điểm chính về TreeMap:

1. 1. Sắp xếp tự nhiên theo thứ tự tăng dần.

2. 2. Chứa các key duy nhất.

3. 3. Hiệu suất tìm kiếm tốt: cung cấp thời gian truy cập gần như là O(log n) cho các phép tìm kiếm và truy xuất, nơi "n" là số lượng phần tử trong TreeMap

4. 4. Không đồng bộ.

5. TreeMap thường được sử dụng khi bạn cần duy trì thứ tự tự nhiên của các phần tử trong bản ghi, hoặc khi bạn cần thực hiện các thao tác tìm kiếm, thêm và xóa phần tử với hiệu suất cao trên dữ liệu lớn.

Bảng so sánh giữa HashMap, LinkedHashMap và TreeMap:

Đặc Điểm	HashMap	LinkedHashMap	TreeMap
Thứ tự lưu trữ	Không đảm bảo	Duy trì thứ tự chèn	Sắp xếp theo khóa
Hiệu suất	Thời gian truy cập O(1) (trừ xung đột băm)	Thời gian truy cập O(1) (nhưng có overhead nhỏ)	Thời gian truy cập O(log n)
Đồng bộ hóa	Không đồng bộ	Không đồng bộ	Không đồng bộ
Sử dụng	Thích hợp cho các tác vụ nhanh chóng không cần quan trọng về thứ tự	Thích hợp khi cần duy trì thứ tự chèn	Thích hợp khi cần sắp xếp các phần tử theo thứ tự tự nhiên của khóa