HashMapcó hai tính chất quan trọng: sizevà load factor. Tôi đã xem qua tài liệu Java và nó nói 0.75flà hệ số tải ban đầu. Nhưng tôi không thể tìm thấy việc sử dụng thực tế của nó.
Đang xem: Load factor là gì
Ai đó có thể mô tả các kịch bản khác nhau mà chúng ta cần đặt hệ số tải là gì và một số giá trị lý tưởng mẫu cho các trường hợp khác nhau là gì không?
Các tài liệu giải thích nó khá tốt:
Một phiên bản của HashMap có hai tham số ảnh hưởng đến hiệu suất của nó: dung lượng ban đầu và hệ số tải. Dung lượng là số lượng xô trong bảng băm và công suất ban đầu chỉ đơn giản là công suất tại thời điểm bảng băm được tạo. Hệ số tải là thước đo mức độ đầy đủ của bảng băm được phép nhận trước khi công suất của nó được tự động tăng lên. Khi số lượng mục trong bảng băm vượt quá sản phẩm của hệ số tải và công suất hiện tại, bảng băm được thử lại (nghĩa là cấu trúc dữ liệu nội bộ được xây dựng lại) để bảng băm có số lượng gấp đôi số lượng.
Theo nguyên tắc chung, hệ số tải mặc định (.75) mang lại sự đánh đổi tốt giữa thời gian và chi phí không gian. Các giá trị cao hơn làm giảm chi phí không gian nhưng tăng chi phí tra cứu (được phản ánh trong hầu hết các hoạt động của lớp HashMap, bao gồm cả lấy và đặt). Số lượng mục dự kiến trong bản đồ và hệ số tải của nó phải được tính đến khi thiết lập công suất ban đầu, để giảm thiểu số lượng các hoạt động làm lại. Nếu công suất ban đầu lớn hơn số lượng mục nhập tối đa chia cho hệ số tải, sẽ không có hoạt động làm lại nào xảy ra.
Xem thêm: Nghĩa Của Từ Get Through Là Gì, Get In Là Gì
Như với tất cả các tối ưu hóa hiệu suất, một ý tưởng tốt là tránh tối ưu hóa mọi thứ sớm (nghĩa là không có dữ liệu cứng về nơi tắc nghẽn).
Các câu trả lời khác đang đề xuất chỉ định capacity = N/0.75để tránh luyện tập lại, nhưng suy nghĩ ban đầu của tôi mới được đặt ra load factor = 1. Sẽ có nhược điểm cho cách tiếp cận đó? Tại sao yếu tố tải ảnh hưởng get()và put()chi phí vận hành?
Hệ số tải = 1 hashmap với số lượng mục = dung lượng sẽ thống kê có số lượng va chạm đáng kể (= khi nhiều khóa tạo ra cùng một hàm băm). Khi xảy ra xung đột, thời gian tra cứu tăng lên, vì trong một nhóm sẽ có> 1 mục khớp, trong đó khóa phải được kiểm tra riêng cho sự bằng nhau. Một số phép toán chi tiết: preshing.com/20110504/hash-collision-probabilities
— atimb
8
Tôi không theo dõi bạn
atimb; Thuộc tính loadset chỉ được sử dụng để xác định khi nào cần tăng kích thước lưu trữ phải không? – Làm thế nào để có một bộ tải của một tăng khả năng va chạm băm? – Thuật toán băm không có kiến thức về số lượng vật phẩm trong bản đồ hoặc tần suất sử dụng “xô” lưu trữ mới, v.v … Đối với bất kỳ nhóm đối tượng nào có cùng kích thước, bất kể chúng được lưu trữ như thế nào, bạn nên có cùng xác suất của các giá trị băm lặp đi lặp lại …
Xác suất va chạm băm là ít hơn, nếu kích thước của bản đồ lớn hơn. Ví dụ: các phần tử có mã băm 4, 8, 16 và 32 sẽ được đặt trong cùng một nhóm, nếu kích thước của bản đồ là 4, nhưng mọi mục sẽ có một nhóm riêng, nếu kích thước của bản đồ lớn hơn 32. Bản đồ với kích thước ban đầu 4 và hệ số tải 1.0 (4 xô, nhưng tất cả 4 yếu tố trong một nhóm) sẽ trong ví dụ này trung bình chậm hơn hai lần so với một hệ số khác với hệ số tải 0,75 (8 xô, hai xô đầy – với phần tử “4” và với các phần tử “8”, “16”, “32”).
— 30h
1
Chi phí tra cứu
Adelin được tăng cho các yếu tố tải cao hơn vì sẽ có nhiều xung đột hơn cho các giá trị cao hơn và cách Java xử lý các xung đột là bằng cách đặt các mục có cùng mã băm vào cùng một nhóm bằng cấu trúc dữ liệu. Bắt đầu trong Java 8, cấu trúc dữ liệu này là một cây tìm kiếm nhị phân. Điều này làm cho việc tìm kiếm phức tạp trong trường hợp xấu nhất O (lg (n)) với trường hợp xấu nhất xảy ra nếu tất cả các yếu tố được thêm vào có cùng mã băm.
Công suất ban đầu mặc định của HashMapmất là 16 và hệ số tải là 0,75f (tức là 75% kích thước bản đồ hiện tại). Hệ số tải thể hiện ở mức độ nào HashMapnên tăng gấp đôi công suất.
Xem thêm: About To Là Gì – Be Going To Là Gì
Ví dụ sản phẩm của công suất và hệ số tải như 16 * 0.75 = 12. Điều này thể hiện rằng sau khi lưu trữ cặp khóa – giá trị thứ 12 vào HashMap, dung lượng của nó trở thành 32.
Mặc dù câu trả lời của bạn rất rõ ràng, bạn có thể vui lòng cho biết ngay sau khi lưu trữ 12 cặp khóa-giá trị, dung lượng trở thành 32 hay là khi mục thứ 13 được thêm vào, tại thời điểm đó, dung lượng thay đổi và sau đó mục nhập được chèn.
