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

HashMap là một trong những cấu trúc dữ liệu hay được sử dụng nhất trong Java, nhưng bản thân map thì lại không phải được coi là là một collection bởi vì nó không được implement Collection interface. Nhưng dĩ nhiên, một collection view có thể đại diện cho map thông qua method entrySet(), hoặc để lấy được collection view của các khoá (key), java hỗ trợ method keySet().

Chúng ta hãy cùng xem xét cách xử lý bên trong HashMap - câu hỏi phỏng vấn ưa thích thuộc Java collection. Có bốn thứ chúng ta cần biết trước khi đào sâu hơn về HashMap:

• HashMap hoạt động dựa trên nguyên lý của việc băm dữ liệu (hashing).
• Map.Entry interface: Interface này là nơi đại diện chứa các entry (cặp key - value) của map.
• hashCode(): HashMap cung cấp hoạt động put(key, value) để lưu trữ và get(key) để lấy ra giá trị từ HashMap. Khi method put được gọi, HashMap sẽ gọi phương thức hashCode từ key object để tính toán giá trị hash, sau đó dùng hash để tìm đến bucket[1] tương ứng và lưu trữ Entry object trong đó. Khi get() được sử dụng để lấy ra value, một lần nữa key object được dùng để tính toán ra hash, từ đó tìm được bucket - nơi chứa dữ liệu của key đó.
• equals() - phương thức này thường dùng so sánh 2 object. Trong trường hợp của HashMap là so sánh 2 key, equals() ngoài ra được dùng để xử lý hashing collision (xung đột hash value - các key khác nhau nhưng lại có hash value giống nhau, như vậy chúng được xếp chung vào cùng một bucket. Trong trường hợp đó, objects value được lưu bên trong một linked list). Trong khi hashCode() được dùng để tìm ra hash của key thì equals() giúp ta tìm được chính xác value tương ứng với key trong trường hợp một hash code trỏ tới nhiều value.

Chúng ta có thể hiểu được tầm quan trọng khi có một hashCode() và equals() được viết một cách chính xác thông qua đoạn code dưới:

public class HashMapTest {
    public static void main(String[] args) {
        Map <Key, String> cityMap = new HashMap<Key, String>();
        cityMap.put(new Key(1, "NY"),"New York City" );
        cityMap.put(new Key(2, "ND"), "New Delhi");
        cityMap.put(new Key(3, "NW"), "Newark");
        cityMap.put(new Key(4, "NP"), "Newport");

        System.out.println("size before iteration " + cityMap.size());
        Iterator <Key> itr = cityMap.keySet().iterator();
        while (itr.hasNext()){
            System.out.println(cityMap.get(itr.next()));     
        }
        System.out.println("size after iteration " + cityMap.size());    
    }
 
}

// This class' object is used as key
// in the HashMap
class Key{
 int index;
 String Name;
 Key(int index, String Name){
  this.index = index;
  this.Name = Name;
 }
 
 @Override
 // A very bad implementation of hashcode
 // done here for illustrative purpose only 
 public int hashCode(){
  return 5;
 }
 
 @Override
 // A very bad implementation of equals
 // done here for illustrative purpose only 
 public boolean equals(Object obj){
  return true;
 }
}

Output

size before iteration 1
Newport
size after iteration 1

Hãy xem qua một lượt đoạn code để xem chuyện gì sảy ra. Chú ý rằng, tôi đã insert 4 value vào bên trong HashMap, nhưng output size thì chỉ có một và khi duyệt nó chỉ in ra phần tử cuối cùng trong 4 giá trị đó. Tại sao?

Câu trả lời gắn với việc bạn implement hashCode() và equals() ra sao. Hãy hình vào hashCode() trong Key class, nó luôn trả về 5 và equals() luôn trả về true.

Khi một giá trị được lưu vào trong HashMap, nó tính toán hash dựa trên key object và đương nhiên là nó sử dụng hashCode() để làm việc này. Dựa trên hash nhận được, HashMap sẽ quyết định bucket nào dùng để chứa Entry object.

Với hashCode() luôn trả về 5. Đó có nghĩa là những hash đã được tính toán giống i hệt nhau với những value khác nhau. Cho nên toàn bộ tất cả Entry được lưu vào trong cùng 1 bucket.

Điều thứ 2, HashMap sử dụng equals() method để check xem value sẽ được đưa vào trong nó có giống với value đã nằm trong nó với trường hợp trùng hash hay không. Như đã nhắc ở trên, (Entry Object) được lưu dưới dạng linked list. Nó giống trường hợp của chúng ta ở hashCode() nhưng lại khác ở equals() vì equals() lúc này trả về false - có nghĩa là có một key chứa nhiều hơn một value. Ở đoạn code trên equals() luôn trả về true cho nên HashMap nghĩ rằng các key này đều giống nhau và bắt đầu ghi đè giá trị cũ.

Nói vắn tắt, sẽ có ba trường hợp sảy ra khi put cái gì đó vào HashMap:

• hashCode() được gọi và tính ra hash value, nếu hash value này không tồn tại trong hash table. thì insert Entry vào một bucket mới.
• equals() được gọi khi hash value tồn tại, nếu trả về true tức là đã có key tồn tại trong HashMap, ghi đè Entry cũ bằng Entry mới trên Linked List ở bucket của Entry cũ.
• equals() trả về false thêm một phần tử vào đằng sau Linked List ở bucket tương ứng với hash value.

Hình minh họa:

Thế còn trường hợp null thì sao? HashMap cho phép chứa key null, nếu key mà null, nó luôn lưu vào cũng như trả về bucket0.

Thay đổi của HashMap trong java 8 Mặc dù nhìn qua có vẻ HashMap get() và put() có độ phức tạp O(1) nhưng đó chỉ là điều kiện lý tưởng khi không có hash collision. Performance của HashMap có thể bị kéo xuống khá nhiều nếu như có càng nhiều hash collision, bởi vì hash collision sảy ra tương đương với chúng ta sẽ phải thực hiện search trên linked list với độ dài > 1. Và tìm kiếm trên linked-list nó có độ phức tạp của một hàm tuyến tính, trong trường hợp tệ nhất sẽ là O(n).

Để giải quyết vấn đề này, Java 8 sử dụng cây cân bằng thay cho linked list với điều kiện số phần tử vượt quá một ngưỡng nào đó. Như vậy trong trường hợp tệ nhất độ phức tạp thay vì là O(n) sẽ giảm xuống còn O(log n).

Chú thích [1] bucket thường dùng để chỉ chỉ số của một mảng mà cụ thể ở đây là nó chỉ chỉ số của HashTable. Ví dụ table[0] tương ứng với bucket0, table[1] tương ứng với bucket1.

nguồn: http://netjs.blogspot.in/2015/05/how-hashmap-internally-works-in-java.html