Những gì chính xác là xô trong hashmap?

Question

Gần đây, trong một cuộc phỏng vấn tôi đã được hỏi, chính xác là một cái xô trong hashmap? Cho dù đó là một mảng hoặc một mảng danh sách hoặc những gì?

Tôi đã nhầm lẫn. Tôi biết hashmaps được hỗ trợ bởi mảng. Vì vậy, tôi có thể nói rằng xô là một mảng với công suất 16 trong đầu lưu trữ hashcodes và danh sách liên kết có con trỏ bắt đầu của họ?

Tôi biết cách thức một hashmap hoạt động nội bộ, chỉ muốn biết chính xác là một nhóm về cấu trúc dữ liệu.

Answer 1

Không, thùng là mỗi phần tử trong mảng mà bạn đang đề cập đến. Trong các phiên bản Java trước đó, mỗi nhóm chứa một danh sách liên kết các mục nhập Bản đồ. Trong các phiên bản Java mới, mỗi nhóm chứa một cấu trúc cây của các mục nhập hoặc một danh sách các mục nhập liên kết.

Từ các ghi chú thực hiện trong Java 8:

/* 
* Implementation notes. 
* 
* This map usually acts as a binned (bucketed) hash table, but 
* when bins get too large, they are transformed into bins of 
* TreeNodes, each structured similarly to those in 
* java.util.TreeMap. Most methods try to use normal bins, but 
* relay to TreeNode methods when applicable (simply by checking 
* instanceof a node). Bins of TreeNodes may be traversed and 
* used like any others, but additionally support faster lookup 
* when overpopulated. However, since the vast majority of bins in 
* normal use are not overpopulated, checking for existence of 
* tree bins may be delayed in the course of table methods. 
... 

Answer 2

Tôi hy vọng điều này có thể giúp bạn hiểu việc thực hiện bản đồ băm tốt.

Answer 3

Xô cơ bản là cấu trúc dữ liệu đang được sử dụng trong thuật toán Phân trang của Hệ điều hành. Để có một ngôn ngữ rất Laymans.

Đối tượng đại diện cho một hashcode đặc biệt đang được lưu trữ trong thùng đó. (Về cơ bản bạn có thể xem xét các tiêu đề của cấu trúc danh sách dữ liệu liên quan đến là giá trị hashcode đó được thể hiện trong các điều khoản của xô)

Các tài liệu tham khảo của đối tượng đang được lưu trữ trong danh sách liên kết, có tiêu đề đại diện cho giá trị của Hashcode.

JVM tạo chúng và kích thước, phụ thuộc vào bộ nhớ được JVM phân bổ.

Answer 4

Xô chính xác là một mảng nút. Vì vậy, một thùng là một thể hiện của lớp java.util.HashMap.Node. Mỗi nút là một cấu trúc dữ liệu tương tự như LinkedList, hoặc có thể giống như một TreeMap (kể từ Java 8), HashMap tự quyết định cái gì tốt hơn cho hiệu suất - giữ các nhóm như LinkedList hoặc TreeMap. TreeMap sẽ chỉ được chọn trong trường hợp hàm hashCode() được thiết kế kém, khi nhiều mục nhập sẽ được đặt trong một thùng duy nhất. Xem cách xô trông giống như trong HashMap:

/** 
    * The table, initialized on first use, and resized as 
    * necessary. When allocated, length is always a power of two. 
    * (We also tolerate length zero in some operations to allow 
    * bootstrapping mechanics that are currently not needed.) 
    */ 
    transient Node<K,V>[] table;