Home
HashMap trong java với ví dụ cụ thể
Tags:

HashMap trong java với ví dụ cụ thể

November 20, 2019

HashMap là một implement của Map interface trong java. Mỗi phần tử trong HashMap là một cặp giá trị key-value, nghĩa là với mỗi key chúng ta sẽ tìm ra một value duy nhất. Do đó việc tìm kiếm trong HashMap sẽ thông qua giá trị key để lấy giá trị tương ứng.

Các bạn có thể đặt câu hỏi rằng `Tại sao không lưu các giá trị vào List mà phải cần đến HashMap?`, lý do đơn giản là hiệu xuất tìm kiếm. Nếu chúng ta muốn tìm kiếm một phần tử trong List, thì time complexity là  O(n), nếu List được sắp xếp thì sẽ là O(log n) với binary search. Ưu điểm của HashMap là độ phức tạp về thời gian để insert và tìm kiếm một giá trị trung bình là  O(1).

HashMap tương tự như HashTable nhưng nó không được đồng bộ hóa. Nó cũng cho phép lưu trữ key có giá trị NULL, nhưng hãy lưu ý trong một HashMap chỉ được chứa một key duy nhất của giá trị NULL. Còn các value thì có thể NULL tùy ý. Các phần tử trong HashMap không được đảm thứ tự 

Constructor HashMap

Để khởi tạo HashMap chúng ta có 4 constructor sau:

  • HashMap(): Default constructor với sức chứa ban đầu là 16.
  • HashMap(int initialCapacity): Khởi tạo HashMap với sức chứa ban đầu initialCapacity.
  • HashMap(int initial capacity, float loadFactor): Khởi tạo HashMap với sức chứa ban đầu initialCapacity và loadFactor.
  • HashMap(Map map): Khởi tạo HashMap copy các phần tử từ Map(HaspMap, HashTable các implement của Map interface) truyền vào.
import java.util.HashMap; 
  
public class GFG { 
    
    public static void main(String[] args) 
    { 
        // Create an empty hash map 
        HashMap<String, Integer> map = new HashMap<>(); 
  
        // Add elements to the map 
        map.put("vishal", 10); 
        map.put("sachin", 30); 
        map.put("vaibhav", 20); 
  
        // Print size and content 
        System.out.println("Size of map is:- "
                           + map.size()); 
        System.out.println(map); 
  
        // Check if a key is present and if 
        // present, print value 
        if (map.containsKey("vishal")) { 
            Integer a = map.get("vishal"); 
            System.out.println("value for key"
                               + " \"vishal\" is:- " + a); 
        } 
    } 
}
Output:
Size of map is:- 3
{vaibhav=20, vishal=10, sachin=30}
value for key "vishal" is:- 10

Sơ đồ thứ bậc của HashMap

Khai kháo

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

Type Parameters:

  • K – Kiểu dữ liệu của KEY
  • V – Kiểu dữ liệu của Value

HashMap implement các interface  Serializable, Cloneable, Map <K, V>. HashMap extends  AbstractMap <K, V>. Các sub-class của nó có thể kể đến như LinkedHashMap, PrinterStateReasons.

Sử dụng HashMap cơ bản

Trước tiên để sử dụng HashMap chúng ta sẽ tạo ra một Product class dùng làm kiểu dữ liệu cho Value trong HashMap

public class Product {

    private String name;
    private String description;
    private List<String> tags;
    
    // standard getters/setters/constructors

    public Product addTagsOfOtherProdcut(Product product) {
        this.tags.addAll(product.getTags());
        return this;
    }
}

Thêm phần tử trong HashMap

Để thêm một phần tử vào HashMap, chúng ta có thể sử dụng phương thức put(). Tuy nhiên các bạn lưu ý rằng thứ tự thêm vào không được giữ lại trong Hashmap. Nội bộ bên trong HashMap, mỗi phần tử sẽ có một mã băm riêng, HashMap lập chỉ mục cho các phần tử dựa vào mã băm này, về cơ bản mã băm này rất khó trùng cho phép việc lập chỉ mục hiệu quả hơn.

Bây giờ chúng ta có thể tạo HashMap với Key là String và Value là Product.

Map<String, Product> productsByName = new HashMap<>();

Và thêm sản phẩm vào HashMap của chúng tôi:

Product eBike = new Product("E-Bike", "A bike with a battery");
Product roadBike = new Product("Road bike", "A bike for competition");
productsByName.put(eBike.getName(), eBike);
productsByName.put(roadBike.getName(), roadBike);

Cập nhật phần tử trong HashMap

Sau khi thêm các phần tử nếu muốn cập nhật lại, thì chúng ta có thể sử dụng lại phương thức put (). Vì các phần tử trong bản đồ được lập chỉ mục bằng cách sử dụng các key, nên giá trị của khóa có thể được thay đổi bằng cách chỉ cần chèn value cho key tương ứng mà chúng ta muốn cập nhật.

Product eBike = new Product("E-Bike", "A bike with a battery");
productsByName.put("1", eBike);

// Cập nhật roadBike cho key = "1"
Product roadBike = new Product("Road bike", "A bike for competition");
productsByName.put("1", roadBike );

Xóa phần tử trong HashMap

Để xóa một phần tử khỏi HashMap, chúng ta có thể sử dụng phương thức remove (). Phương thức này nhận giá trị key và xóa phần tử trong HashMap có giá trị key tương ứng với key được truyền vào.

productsByName.remove("E-Bike");
assertNull(productsByName.get("E-Bike"));

Truy xuất phần tử trong HashMap

Chúng ta có thể lấy một value dựa vào key được cung cấp thông qua get() method

productsByName.remove("E-Bike");
assertNull(productsByName.get("E-Bike"));
Product nextPurchase = productsByName.get("E-Bike");
assertEquals("A bike with a battery", nextPurchase.getDescription());

Nếu chúng ta cố gắng tìm giá trị cho một key không tồn tại trong HashMap, get() sẽ trả về NULL.

Product nextPurchase = productsByName.get("Car");
assertNull(nextPurchase);

Key có giá trị null trong HashMap

Như đã đề cập ở trên thì HashMap có thể lưu trữ một key có giá trị NULL

roduct defaultProduct = new Product("Chocolate", "At least buy chocolate");
productsByName.put(null, defaultProduct);

Product nextPurchase = productsByName.get(null);
assertEquals("At least buy chocolate", nextPurchase.getDescription());

Kiểm tra key hoặc value tồn tại trong HashMap

Để kiểm tra xem một key có xuất hiện trong HashMap hay không, chúng ta có thể sử dụng phương thức containsKey ():

productsByName.containsKey("E-Bike");

Hoặc, để kiểm tra xem một value có trong HashMap hay không, chúng ta có thể sử dụng phương thức containsValue ():

productsByName.containsValue(eBike);

Cả hai lời gọi phương thức sẽ trả về true trong ví dụ của chúng ta. Mặc dù chúng trông rất giống nhau, có một sự khác biệt quan trọng về hiệu suất giữa hai phương pháp này là. Độ phức tạp để kiểm tra xem một key có tồn tại hay không là O (1), trong khi độ phức tạp để kiểm tra một value là O (n), vì cần phải duyệt qua tất cả các phần tử trong HashMap.

Duyệt HashMap

Có ba cách cơ bản để lặp lại tất cả các cặp key-value trong HashMap. Chúng tôi có thể lặp lại tập hợp tất cả các khóa:

for(String key : productsByName.keySet()) {
    Product product = productsByName.get(key);
}

Hoặc chúng ta có thể lặp lại tập hợp tất cả các mục:

for(Map.Entry<String, Product> entry : productsByName.entrySet()) {
    Product product =  entry.getValue();
    String key = entry.getKey();
    //do something with the key and value
}

Cuối cùng, chúng ta có thể lặp lại trên tất cả các value của HashMap:

List<Product> products = new ArrayList<>(productsByName.values());

Hiểu rõ Key trong HashMap

Chúng ta có thể sử dụng một class do chính chúng ta tự định nghĩa để làm kiểu dữ liệu cho key của HashMap. Tuy nhiên, để HashMap hoạt động bình thường, chúng ta cần override các method equals () và hashCode (). Nếu không, mọi Product Object đều được xem là một key khác nhau cho dù giá trị của các thuộc tính dùng làm key bằng nhau.

class Product {

    private String name;
    private String description;
    private List<String> tags;
    // ... constructor,setter, getter
     @Override
    public boolean equals(Object o) {
       if (this == o) {
         return true;
       }
      if (o == null || getClass() != o.getClass()) {
        return false;
      }

     Product product = (Product) o;
     return Objects.equals(name, product.name) &&
       Objects.equals(description, product.description);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, description);
    }

    public Product addTagsOfOtherProdcut(Product product) {
        this.tags.addAll(product.getTags());
        return this;
    }
}

Lưu ý rằng hashCode () và equals () chỉ cần được ghi đè cho các class mà chúng ta muốn sử dụng làm key cho HashMap. 

Một số method bổ sung cho HashMap trong Java 8

Java 8 đã thêm một số method vào HashMap theo phong cách functional-style mà chúng ta sẽ tìm hiểu trong phần này.

forEach trong HashMap

forEach method cho phép duyệt qua tất cả các phần tử trong HashMap

productsByName.forEach( (key, product) -> {
    System.out.println("Key: " + key + " Product:" + product.getDescription());
    //do something with the key and value
});

Thay vì các phiên bản trước Java 8 thì chúng ta phải duyệt bằng cách sau:

for(Map.Entry<String, Product> entry : productsByName.entrySet()) {
    Product product =  entry.getValue();
    String key = entry.getKey();
    //do something with the key and value
}

getOrDefault

Sử dụng phương thức getOrDefault (), chúng ta có thể lấy một giá trị từ HashMap hoặc trả về một phần tử mặc định trong trường hợp không có value nào tương ứng với key đã cho.

Product chocolate = new Product("chocolate", "something sweet");
Product defaultProduct = productsByName.getOrDefault("horse carriage", chocolate); 
Product bike = productsByName.getOrDefault("E-Bike", chocolate);

Ở các phiên bản trước Java 8 chúng ta cần phải viết dài dòng hơn như sau

Product bike2 = productsByName.containsKey("E-Bike") 
    ? productsByName.get("E-Bike") 
    : chocolate;
Product defaultProduct2 = productsByName.containsKey("horse carriage") 
    ? productsByName.get("horse carriage") 
    : chocolate;

putIfAbsent

Với phương pháp này, chúng ta có thể thêm một phần tử mới, nhưng chỉ khi chưa có một phần tử tồn tại với key đã cho:

productsByName.putIfAbsent("E-Bike", chocolate);

Tương ứng với các phiên bản trước Java 8

if(productsByName.containsKey("E-Bike")) {
    productsByName.put("E-Bike", chocolate);
}

merge

Và với merge (), chúng ta có thể sửa đổi value cho một key nhất định nếu tồn tại một phần tử hoặc thêm một value mới:

Product eBike2 = new Product("E-Bike", "A bike with a battery");
eBike2.getTags().add("sport");
productsByName.merge("E-Bike", eBike2, Product::addTagsOfOtherProdcut);

Trước Java 8

if(productsByName.containsKey("E-Bike")) {
    productsByName.get("E-Bike").addTagsOfOtherProdcut(eBike2);
} else {
    productsByName.put("E-Bike", eBike2);
}

compute

Với phương thức compute (), chúng ta có thể thao tác trên value của một key tương ứng:

productsByName.compute("E-Bike", (k,v) -> {
    if(v != null) {
        return v.addTagsOfOtherProdcut(eBike2);
    } else {
        return eBike2;
    }
});

Trước Java 8

if(productsByName.containsKey("E-Bike")) {    
    productsByName.get("E-Bike").addTagsOfOtherProdcut(eBike2); 
} else {
    productsByName.put("E-Bike", eBike2); 
}

Cách HashMap hoạt động bên trong

Trong phần này chúng ta sẽ cùng nhau tìm hiểu xem bên trong HashMap hoạt động như thế nào để nó có thể đạt được hiệu xuất tìm kiếm O(1).

HashMap lưu trữ các phần tử trong một nơi gọi là các bucket, số lượng các bucket được gọi là capacity tất là sức chứa của HashMap. Khi một cặp giá trị key-value được thêm vào HashMap. Phương thức hashCode() của key sẽ được dùng để xác định một bucket nơi để chứa value.

Để truy xuất lại value tương ứng với key, HashMap sẽ tìm ra bucket bằng cách tương tự sử dụng hashCode() method để tính ra được bucket nào đang chứa value của key, bucket này có thể chứa nhiều key-value do các hashCode() method của các key khác nhau có thể trả về cùng một giá trị. Để giải quyết cho trường hợp này, nó sẽ duyệt qua các phần tử trong bucket và sử dụng equals() của key để tìm ra value tương ứng.

Các method trong HashMap

  1. void clear(): Xóa tất cả các phần tử trong HashMap
  2. boolean containsKey(Object key): Kiểm tra sự tồn tại của key trong HashMap.
  3. boolean containsValue(Object value): Trả về true nếu một hoặc nhiều khóa có chứa value.
  4. Object clone(): Copy HashMap.
  5. boolean isEmpty(): Trả về true nếu HashMap không chứa bất kỳ cặp key-value nào.
  6. Set entrySet(): Trả về tập Set<Map.Entry> dùng trong duyệt HashMap.
  7. Object get(Object key): Trả về value của key trong HashMap
  8. Set keySet(): Trả về tập key trong HashMap.
  9. int size(): Trả về số lượng phần tử của HashMap.
  10. Object put(Object key, Object value): Thêm cặp giá trị key – value vào HashMap.
  11. putAll(Map M): Thêm một implement của Map vào HashMap như HashMap khác, HashTable etc.
  12. Object remove(Object key): Xóa phần tử trong HashMap.
  13. Collection values(): Trả về tập value trong HashMap.
  14. compute(K key, BiFunction<K, V> remappingFunction): Update value theo key.
  15. computeIfAbsent(K key, Function<K> mappingFunction): Update value nếu  key không tồn tại hoặc value là null.
  16. computeIfPresent(K key, BiFunction<K, V> remappingFunction): Nếu key tồn tại trong HashMap và update value theo remappingFunction. Nếu value null thì apply giá trị mới theoremappingFunction
  17. forEach(BiConsumer<K, V> action): This method Performs the given action for each entry in this map until all entries have been processed or the action throws an exception.
  18. getOrDefault(Object key, V defaultValue): Trả về value của phần tử ứng với key được truyền vào. Trả về defaultValue nếu key không tồn tại trong HashMap.
  19. putIfAbsent(K key, V value): Nếu key được chỉ định không chứa trong HashMap hoặc có value null thì sẽ được thay thế bởi giá giá trị value mới và được thêm vào HashMap nếu key không tồn tại.
  20. replace(K key, V value): Thay thế value của key được chỉ định.
  21. replace(K key, V oldValue, V newValue): Thay thế value có giá trị là oldValue của key được chỉ định thành newValue.
  22. replaceAll(BiFunction<K, V> function): Thay thế tất cả các phần tử của HashMap theo BiFunction.

Nguồn tham khảo

https://www.geeksforgeeks.org/java-util-hashmap-in-java-with-examples/

Baedung

 

0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x