Hashmap Là Gì

HashMap là một trong những giữa những cấu trúc dữ liệu hay được dùng độc nhất vô nhị trong Java, tuy thế bạn dạng thân bản đồ thì lại chưa phải được xem là là một collection chính vì nó ko được implement Collection interface. Nhưng dĩ nhiên, một collection view hoàn toàn có thể đại diện đến maps thông qua method entrySet(), hoặc để lấy được collection view của những khoá (key), java hỗ trợ method keySet().

Bạn đang xem: Hashmap là gì

Chúng ta hãy thuộc lưu ý giải pháp xử lý phía bên trong HashMap - thắc mắc vấn đáp ái mộ thuộc Java collection. Có tư máy chúng ta cần phải biết trước khi đào sâu rộng về HashMap:

HashMap vận động dựa vào nguyên tắc của vấn đề băm dữ liệu (hashing).Map.Entry interface: Interface này là địa điểm đại diện thay mặt cất những entry (cặp key - value) của bản đồ.hashCode(): HashMap hỗ trợ hoạt động put(key, value) nhằm lưu giữ trữ và get(key) nhằm rước ra giá trị từ bỏ HashMap. Khi method put được điện thoại tư vấn, HashMap đã Gọi cách làm hashCode tự key object nhằm tính tân oán cực hiếm hash, sau đó cần sử dụng hash nhằm tìm tới bucket<1> tương xứng với tàng trữ Entry object trong những số ấy. Khi get() được thực hiện để đưa ra value, một đợt tiếp nhữa key object được dùng để làm tính toán ra hash, tự đó tìm được bucket - vị trí cất tài liệu của key đó.equals() - cách làm này thường dùng so sánh 2 object. Trong ngôi trường vừa lòng của HashMap là đối chiếu 2 key, equals() ngoài ra được dùng để làm giải pháp xử lý hashing collision (xung thốt nhiên hash value - những key không giống nhau cơ mà lại có hash value giống nhau, điều đó bọn chúng được xếp chung vào và một bucket. Trong ngôi trường phù hợp đó, objects value được lưu giữ bên phía trong một linked list). Trong Lúc hashCode() được dùng để tìm thấy hash của key thì equals() giúp chúng ta kiếm được đúng mực value tương ứng với key vào ngôi trường vừa lòng một hash code trỏ tới các value.

Chúng ta rất có thể hiểu được khoảng quan trọng lúc tất cả một hashCode() và equals() được viết một biện pháp đúng mực thông qua đoạn code dưới:

public class HashMapTest public static void main(String<> args) Map cityMap = new HashMap(); cityMap.put(new Key(1, "NY"),"Thành Phố 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 itr = cityMap.keySet().iterator(); while (itr.hasNext()) System.out.println(cityMap.get(itr.next())); System.out.println("kích thước after iteration " + cityMap.size()); // This class" object is used as key// in the HashMapclass 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 sầu purpose only public boolean equals(Object obj) return true; Outputkích cỡ before iteration 1Newportform size after iteration 1Hãy xem sang 1 lượt đoạn code giúp thấy cthị trấn gì sảy ra. Crúc ý rằng, tôi vẫn insert 4 value vào phía bên trong HashMap, nhưng mà output kích cỡ thì chỉ tất cả một cùng khi phê chuẩn nó chỉ in ra bộ phận ở đầu cuối vào 4 giá trị đó. Tại sao?

Câu vấn đáp đính thêm với vấn đề các bạn implement hashCode() với equals() ra làm sao. Hãy hình vào hashCode() vào Key class, nó luôn luôn trả về 5 cùng equals() luôn trả về true.

lúc một quý hiếm được lưu lại vào trong HashMap, nó tính tân oán hash dựa trên key object và dĩ nhiên là nó thực hiện hashCode() để làm Việc này. Dựa trên hash cảm nhận, HashMap vẫn ra quyết định bucket làm sao dùng để chứa Entry object.

Xem thêm: Mathtype Trên Máy Tính - Hướng Dẫn Cách Tải Và Cài Đặt

Với hashCode() luôn luôn trả về 5. Đó có nghĩa là đa số hash đã được tính tân oán như thể i hệt nhau cùng với hầu như value khác nhau. Cho đề nghị tổng thể tất cả Entry được lưu vào vào thuộc 1 bucket.

Điều trang bị 2, HashMap áp dụng equals() method để kiểm tra xem value sẽ tiến hành gửi vào vào nó tất cả kiểu như với value đang phía trong nó cùng với ngôi trường thích hợp trùng hash hay là không. Nhỏng vẫn kể làm việc trên, (Entry Object) được giữ bên dưới dạng linked danh sách. Nó giống ngôi trường hợp của chúng ta sống hashCode() nhưng lại lại không giống sống equals() bởi vì equals() lúc này trả về false - có nghĩa là có một key chứa nhiều rộng một value. Tại đoạn code bên trên equals() luôn trả về true do đó HashMap nghĩ rằng các key này đa số như là nhau với bước đầu ghi đnai lưng quý giá cũ.

Nói vắn tắt, sẽ sở hữu được cha ngôi trường vừa lòng sảy ra khi put dòng gì đó vào HashMap:

hashCode() được Hotline cùng 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 call Khi hash value trường thọ, nếu trả về true tức là đang bao gồm key lâu dài vào HashMap, ghi đtrần Entry cũ bởi Entry bắt đầu bên trên Linked List nghỉ ngơi bucket của Entry cũ.equals() trả về false thêm một trong những phần tử vào đằng sau Linked List làm việc bucket tương xứng cùng với hash value.

Hình minc họa:

*

Thế còn trường vừa lòng null thì sao?HashMap được cho phép đựng key null, nếu key nhưng null, nó luôn lưu lại vào tương tự như trả về bucket0.

Tgiỏi thay đổi của HashMap trong java 8Mặc cho dù nhìn qua có vẻ như HashMap get() cùng put() có độ phức tạp O(1) tuy nhiên đó chỉ nên điều kiện lphát minh Khi không có hash collision. Performance của HashMap có thể bị kéo xuống tương đối nhiều nếu như nlỗi bao gồm càng nhiều hash collision, bởi vì hash collision sảy ra tương tự cùng với họ vẫn buộc phải thực hiện search trên linked các mục cùng với độ dài > 1. Và tra cứu tìm trên linked-menu nó gồm độ phức hợp của một hàm đường tính, trong trường vừa lòng tệ tuyệt nhất đã là O(n).

Để xử lý vấn đề này, Java 8 áp dụng cây cân bằng cố cho linked list với điều kiện số thành phần quá thừa một ngưỡng nào đó. Vậy nên trong ngôi trường hợp tệ tuyệt nhất độ phức tạp nỗ lực vì là O(n) sẽ sụt giảm còn O(log n).

Crúc thích<1> bucket hay dùng làm chỉ chỉ số của một mảng mà ví dụ sinh hoạt đó là nó chỉ chỉ số của HashTable. lấy một ví dụ table<0> tương xứng cùng với bucket0, table<1> tương xứng cùng với bucket1.