Số lượng các nhóm trong HashMap có ý nghĩa gì?

Question

Tôi đã đọc về Hashmap.

Ví dụ về HashMap có hai tham số ảnh hưởng đến hiệu suất của nó: công suất ban đầu và hệ số tải. Dung lượng là số lượng nhóm trong bảng băm.

Nếu có 10 cặp giá trị khóa trong Hashmap. Giả sử có Hashcode khác nhau.

Mỗi người sẽ nằm trong một thùng phải không? Hoặc một nhóm có thể có nhiều nhóm khóa-giá trị?

Vì bucket bằng tiếng Anh có nghĩa là một điều lớn mà nhiều đối tượng có thể cư trú.

Answer 1

Có, chính xác, mỗi nhóm có thể có nhiều cặp khóa-giá trị.

Đối tượng của hashCode() xác định xem nó đi vào cái gì, thông qua biểu thức này: object.hashCode() % n, trong đó n = tổng số nhóm và % là toán tử mô đun.

Thông thường các đối tượng sẽ được phân phối tốt trên các nhóm, nhưng bạn không bảo đảm nơi chúng đi. Điều này phụ thuộc vào dữ liệu và hàm hashCode.

Rõ ràng, khi triển khai hashCode kém, hiệu suất của hashmap sẽ giảm.

Đồng thời đọc thêm về hợp đồng equals/hashcode, có liên quan.

Answer 2

Bucket with hashcode 1 Bucket with hashcode 2 and similar 
    K and V     K and V 
    K and V     K and V 

Vì vậy, các hashCode() của khóa quyết định, trong đó bộ chứa các cặp K V đi và cùng hashCode được sử dụng để tìm ra cặp K V trong khi tra cứu.

hashCode() không được trả lại giá trị hằng số giá trị. Điều đó có nghĩa là tất cả các vật thể sẽ ở trong một thùng. Và điều đó sẽ giống như không sử dụng một số Map ngay từ đầu. Vì tất cả các cặp giá trị khóa sẽ nằm trong cùng một nhóm, Java sẽ phải lặp qua tất cả các đối tượng để tìm khóa.

Answer 3

Trong java nếu bạn lưu trữ một đối tượng trong HashMap, triển khai HashMap đầu tiên gọi phương thức hashCode() để tìm vị trí nhóm. Sau đó, nó lưu trữ cả hai: khóa và giá trị như một Entry. NB! nó lưu trữ khóa cũng vì nó rất quan trọng trong quá trình truy xuất đối tượng. Hai đối tượng có thể có cùng một hashcode vì vậy nếu điều này xảy ra thì HashMap sẽ sử dụng cùng một vị trí nhóm và lưu trữ đối tượng thứ hai ở đó. Bên trong nó sử dụng một LinkedList cho việc này. (không phải java.util.LinkedList, nhưng triển khai đơn giản hơn)

Trong khi truy xuất: bạn có một khóa -> hashCode() -> vị trí nhóm -> tìm kiếm trong LinkedList theo khóa -> đối tượng trả về.

EDIT: Vì vậy, bạn có một nhóm trên cùng một vị trí nhưng một nhóm là một LinkedList để có thể lưu trữ nhiều mục nhập. Vì vậy, số lượng nhóm là khả năng của Hashmap và mô tả số lượng Mục bạn có thể lưu trữ mà không liên kết chúng trong danh sách.

Bạn có thể tìm thấy một bài viết tuyệt vời và giải thích chi tiết hơn ở đây: http://javahungry.blogspot.com/2013/08/hashing-how-hash-map-works-in-java-or.html http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html