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

Shallow Copy và Deep Copy

Chào mừng các bạn đã quay trở lại với thachleblog. Trước khi bắt đầu với chủ đề ngày hôm nay, mình có 1 câu hỏi muốn hỏi các bạn “Các bạn đã bao giờ tạo một object mà không dùng toán tử new() chưa?”. Nếu câu trả lời là chưa, thì bài viết về shallow copy và deep copy này chắc chắn là dành cho bạn. Tuy nhiên, các bạn đã biết cũng có thể đọc và cho nhận xét để chúng ta có thể trao đổi thêm. Nào, chúng ta cùng bắt đầu với chủ Shallow Copy và Deep Copy nhé.

Clone object

Trước khi đến với Shallow Copy và Deep Copy, chúng ta cùng tìm hiểu về clone object

Thông thường, chúng ta tạo object bằng lệnh new Object(). Object này sẽ được tạo mới trong vùng nhớ của JVM. Khác với new, clone object là quá trình tạo object từ object đã tồn tại trong vùng nhớ. Trong java, phương thức clone(), dùng để clone 1 object từ object có sẵn. Để 1 object có thể clone, object đó cần phải implement Clonable interface.

Shallow Copy và Deep Copy là các quá trình tạo object bằng phương pháp clone. Mặc định của method clone() là Shallow Copy. Để 1 object được Deep Copy. Chúng ta cần override method clone. Chúng ta cùng xem Shallow Copy và Deep Copy là như nào nhé.

Shallow Copy 

Shallow Copy là quá trình tạo object copy mà trong đó nếu object đó có chứa object chứa trong khác thì quá trình copy chỉ copy reference (địa chỉ vùng nhớ) của object chứa trong đó.

Hình minh họa shallow copy

Hình minh họa shallow copy 

Điều đó cả nghĩa là ContainObject1 của 2 object MainObject1 và MainObject2 cùng trỏ tới một giá trị. Khi thay đổi giá trị của ContainObject1 trên MainObject1, giá trị của ContainObject2 trên MainObject2 sẽ thay đổi theo.

Code minh họa Shallow Copy 

Class Student

package shallow.copy;
 
/**
 *
 * @author thachlp
 */
public class Student implements Cloneable{
 
    private String name;
    private Course course;
 
    public String getName() {
        return name;
    }
 
    public void setName(String name) {
        this.name = name;
    }
 
    public Student(String name, Course course){
        this.course = course;
        this.name = name;
    }
 
    public Course getCourse() {
        return course;
    }
 
    public void setCourse(Course course) {
        this.course = course;
    }
 
    @Override
    protected Object clone() throws CloneNotSupportedException {
        return super.clone(); //To change body of generated methods
    }
 
}

 

Để có thể clone object, Student cần implement Cloneable interface. Trong Student object sẽ có Course object.

Class Course

package shallow.copy;
 
/**
 *
 * @author thachlp
 */
public class Course {
    private String name;
    private int lenght;
 
    public int getLenght() {
        return lenght;
    }
 
    public void setLenght(int lenght) {
        this.lenght = lenght;
    }
 
    public String getName() {
        return name;
    }
 
    public void setName(String name) {
        this.name = name;
    }
 
    public Course(String name, int lenght){
        this.name = name;
        this.lenght = lenght;
    }
 
}

 

Class Test

package shallow.copy;
 
/**
 *
 * @author thachlp
 */
public class TestShallowCopy {
 
    public static void main(String[] args) throws CloneNotSupportedException {
        Student student1 = new Student("Thach", new Course("Java programming", 4));
        System.out.println(student1.getCourse().getName());
 
        Student student2 = (Student) student1.clone();
        student2.getCourse().setName("Python programming");
        System.out.println(student1.getCourse().getName());
 
    }
 
}

 

Kết quả : khi update giá trị cho course object ở student1, giá trị của course ở object2 cũng sẽ thay đổi theo, kết quả khi chạy chương trình:

Java programming
Python programming

Deep Copy

Khác với Shallow Copy, Deep Copy sẽ tạo ra object mới với reference độc lập với object gốc. Mọi thay đổi object chứa trong sẽ không ảnh hưởng đến nhau.

Hình minh hạo Deep Copy

Hình minh họa deep copy

Code minh họa Deep Copy 

Class Student

package deep.copy;
 
 
/**
 *
 * @author thachlp
 */
public class Student implements Cloneable {
 
    private String name;
     Course course;
 
    public String getName() {
        return name;
    }
 
    public void setName(String name) {
        this.name = name;
    }
 
    public Student(String name, Course course) {
        this.course = course;
        this.name = name;
    }
 
    public Course getCourse() {
        return course;
    }
 
    public void setCourse(Course course) {
        this.course = course;
    }
 
    @Override
    public Object clone() throws CloneNotSupportedException {
        Student student = (Student) super.clone();
        student.course = (Course) course.clone();
 
        return student; //To change body of generated methods
    }
 
}

 

Class Course 

package deep.copy;
 
 
/**
 *
 * @author thachlp
 */
public class Course implements Cloneable{
    private String name;
    private int lenght;
 
    public int getLenght() {
        return lenght;
    }
 
    public void setLenght(int lenght) {
        this.lenght = lenght;
    }
 
    public String getName() {
        return name;
    }
 
    public void setName(String name) {
        this.name = name;
    }
 
    public Course(String name, int lenght){
        this.name = name;
        this.lenght = lenght;
    }
 
    @Override
    protected Object clone() throws CloneNotSupportedException {
        return super.clone(); //To change body of generated methods, choose Tools | Templates.
    }
 
}

 

Cần chú ý là để Deep Copy, class Course cũng cần implement Cloneable interface.

Class Test

package deep.copy;
 
/**
 *
 * @author thachlp
 */
public class TestDeepCopy {
    public static void main(String[] args) throws CloneNotSupportedException {
        Student student1 = new Student("Thach", new Course("Java programming", 4));
 
        System.out.println(student1.getCourse().getLenght());
 
        Student student2 = (Student) student1.clone();
        student2.getCourse().setLenght(3);
        System.out.println(student1.getCourse().getLenght());
 
    }
 
}

 

Kết quả : object course bên trong object student1 và student2 là độc lập. Thay đổi course bên student1 sẽ không ảnh hưởng đến course của student2.

Java programming
Java programming

Kết luận

Vừa rồi mình vừa trình bày về clone() method, Shallow Copy và Deep Copy. Tùy theo trường hợp cụ thể mà ta sử dụng Shallow hoặc Deep. Sắp tới mình sẽ viết bài về prototype design pattern sẽ liên quan đến clone() method, các bạn nhớ đón đọc nhé. Mọi góp ý về bài viết này xin vui lòng comment bên dưới, mình sẽ follow.

Xin cảm ơn.

Xem thêm:

http://javaconceptoftheday.com/difference-between-shallow-copy-vs-deep-copy-in-java/ 

http://www.jusfortechies.com/java/core-java/deepcopy_and_shallowcopy.php