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 assortment bởi vì nó không được implement Assortment interface. Nhưng dĩ nhiên, một assortment view có thể đại diện cho map thông qua technique entrySet(), hoặc để lấy được assortment view của các khoá (key), java hỗ trợ technique 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 assortment. 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 – worth) của map.
  • hashCode(): HashMap cung cấp hoạt động put(key, worth) để lưu trữ và get(key) để lấy ra giá trị từ HashMap. Khi technique 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 worth, 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 worth – các key khác nhau nhưng lại có hash worth 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 worth được lưu bên trong một linked record). 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 worth tương ứng với key trong trường hợp một hash code trỏ tới nhiều worth.
Có Thể Bạn Quan Tâm :   LinkedIn là gì? Hướng dẫn cách tạo tài khoản LinkedIn hiệu quả

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 predominant(String[] args) { Map <Key, String> cityMap = new HashMap<Key, String>(); cityMap.put(new Key(1, “NY”),”New York Metropolis” ); 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(“measurement earlier than iteration ” + cityMap.measurement()); Iterator <Key> itr = cityMap.keySet().iterator(); whereas (itr.hasNext()){ System.out.println(cityMap.get(itr.subsequent())); } System.out.println(“measurement after iteration ” + cityMap.measurement()); } } // This class’ object is used as key // within the HashMap class Key{ int index; String Identify; Key(int index, String Identify){ this.index = index; this.Identify = Identify; } @Override // A really dangerous implementation of hashcode // achieved right here for illustrative goal solely public int hashCode(){ return 5; } @Override // A really dangerous implementation of equals // achieved right here for illustrative goal solely public boolean equals(Object obj){ return true; } } Output measurement earlier than iteration 1 Newport measurement 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 worth vào bên trong HashMap, nhưng output measurement 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ó Thể Bạn Quan Tâm :   Local disk là gì? sự khác biệt giữa ổ (C:) và ổ (D:)

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 worth 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() technique để examine xem worth sẽ được đưa vào trong nó có giống với worth đã 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 record. 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 worth. Ở đ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 worth, nếu hash worth này không tồn tại trong hash desk. thì insert Entry vào một bucket mới.
  • equals() được gọi khi hash worth 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 Listing ở bucket của Entry cũ.
  • equals() trả về false thêm một phần tử vào đằng sau Linked Listing ở bucket tương ứng với hash worth.
Có Thể Bạn Quan Tâm :   Shift Manager là gì? Các công việc của người Shift Manager

Hình minh họa: HashMap hoạt động như thế nào trong java ???

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. Efficiency 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 record 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 record 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ụ desk[0] tương ứng với bucket0, desk[1] tương ứng với bucket1.

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

Back to top button