Các tham số khởi tạo HashMap (tải/initialcapacity)

Question

Tôi nên chuyển các giá trị nào để tạo ra các cấu trúc dựa trên HashMap/HashMap hiệu quả cho N mục?

Trong số ArrayList, số hiệu quả là N (N đã giả định tương lai tăng). Các tham số cho HashMap là gì? ((int) (N * 0,75d), 0,75d)? Hơn? Ít hơn? Hiệu ứng của việc thay đổi hệ số tải là gì?

Answer 1

Về hệ số tải, tôi sẽ chỉ đơn giản là trích dẫn từ HashMap javadoc:

Theo nguyên tắc chung, các hệ số tải mặc định (.75) cung cấp một sự cân bằng tốt giữa chi phí thời gian và không gian. 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 lấy và đặt). Số lượng các mục nhập dự kiến ​​trong bản đồ và hệ số tải của nó cần được tính đến khi thiết lập dung lượng ban đầu của nó, để giảm thiểu số lượng các hoạt động phục hồ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, thì sẽ không có hoạt động phục hồi nào xảy ra.

Có nghĩa là, hệ số tải không được thay đổi từ .75, trừ khi bạn có một số tối ưu hóa cụ thể mà bạn sẽ làm. Dung lượng ban đầu là thứ duy nhất bạn muốn thay đổi và đặt giá trị theo giá trị N - nghĩa là (N/0.75) + 1 hoặc một thứ gì đó trong khu vực đó. Điều này sẽ đảm bảo rằng bảng sẽ luôn đủ lớn và không có sự phục hồi sẽ xảy ra.

Answer 2

Trong một ArrayList, số hiệu quả là N (N đã giả định tương lai phát triển).

Erm, không, trừ khi tôi hiểu nhầm những gì bạn đang nói ở đây. Khi bạn chuyển một số nguyên vào hàm tạo của Arraylist, nó sẽ tạo một mảng cơ bản có kích thước chính xác. Nếu nó chỉ ra bạn cần ngay cả một phần tử phụ, ArrayList sẽ cần phải thay đổi kích thước mảng bên dưới khi bạn gọi hàm add() tiếp theo, khiến cuộc gọi này mất nhiều thời gian hơn bình thường.

Nếu mặt khác, bạn đang nói về giá trị N của bạn có tính đến tăng trưởng tài khoản - thì có, nếu bạn có thể đảm bảo giá trị sẽ không bao giờ vượt quá điều này thì gọi một hàm tạo Arraylist là phù hợp. Và trong trường hợp này, như được chỉ ra bởi Hank, nhà xây dựng tương tự cho một bản đồ sẽ là N và 1.0f. Điều này nên thực hiện hợp lý ngay cả khi bạn thực sự vượt quá N (mặc dù nếu bạn mong đợi điều này xảy ra một cách thường xuyên, bạn có thể muốn vượt qua trong một số lượng lớn hơn cho kích thước ban đầu).

Hệ số tải, trong trường hợp bạn không biết, là điểm mà tại đó bản đồ sẽ có khả năng tăng lên, như một phần nhỏ trong tổng dung lượng.

Chỉnh sửa: Yuval có lẽ đúng là nên để hệ số tải khoảng 0,75 cho bản đồ mục đích chung. Hệ số tải 1.0 sẽ thực hiện rực rỡ nếu các khóa của bạn có mã băm tuần tự (chẳng hạn như các phím số nguyên tuần tự), nhưng đối với bất kỳ thứ gì khác bạn có thể gặp phải xung đột với các nhóm băm, nghĩa là tra cứu mất nhiều thời gian hơn cho một số phần tử. Việc tạo ra nhiều nhóm hơn mức cần thiết sẽ làm giảm nguy cơ va chạm này, có nghĩa là có nhiều cơ hội hơn các thành phần nằm trong nhóm riêng của chúng và do đó có thể khôi phục trong khoảng thời gian ngắn nhất. Như các tài liệu nói, đây là một thời gian so với sự cân bằng không gian. Nếu một trong hai là đặc biệt quan trọng với bạn (như được hiển thị bởi một profiler chứ không phải là tối ưu hóa sớm!), Bạn có thể nhấn mạnh rằng; nếu không, hãy gắn bó với mặc định.

Answer 3

Cũng đáng chú ý là việc có HashMap ở phía nhỏ làm cho va chạm băm dễ xảy ra hơn, điều này có thể làm chậm quá trình tìm kiếm. Do đó, nếu bạn thực sự lo lắng về tốc độ của bản đồ, và ít hơn về kích thước của nó, nó có thể là giá trị làm cho nó một chút quá lớn cho các dữ liệu nó cần phải giữ. Vì bộ nhớ có giá rẻ, tôi thường khởi tạo HashMaps cho một số mục đã biết với

HashMap<Foo> myMap = new HashMap<Foo>(numberOfElements * 2); 

Hãy cảm thấy không đồng ý, trên thực tế tôi rất muốn ý tưởng này được xác minh hoặc loại bỏ.

Answer 4

Đề cập đến mã nguồn HashMap sẽ giúp ích.

Nếu số lượng mục nhập đạt đến ngưỡng (hệ số tải công suất *), việc khôi phục được thực hiện tự động. Điều đó có nghĩa là yếu tố tải quá nhỏ có thể phải phục hồi thường xuyên khi các mục phát triển.

Answer 5

Đối với HashMaps rất lớn trong các hệ thống quan trọng, khi sai số ban đầu có thể rất khó, bạn có thể cần thông tin thực nghiệm để xác định cách khởi tạo bản đồ tốt nhất.

Bộ sưu tậpSpy (collectionspy.com) là một trình thu gọn Java mới cho phép bạn xem trong nháy mắt mà HashMaps gần cần khôi phục, số lần chúng đã được khôi phục trong quá khứ và hơn thế nữa. Một công cụ lý tưởng để xác định các đối số công suất ban đầu an toàn cho các nhà xây dựng container dựa trên dung lượng.

Answer 6

Câu trả lời mà Yuval đưa ra chỉ đúng cho Hashtable. HashMap sử dụng sức mạnh của hai nhóm, vì vậy đối với HashMap, Zarkonnen thực sự là chính xác. Bạn có thể xác minh điều này từ mã nguồn:

// Find a power of 2 >= initialCapacity 
    int capacity = 1; 
    while (capacity < initialCapacity) 
    capacity <<= 1; 

Vì vậy, mặc dù hệ số tải của 0.75f ​​là vẫn như nhau giữa Hashtable và HashMap, bạn nên sử dụng công suất ban đầu n * 2 trong đó n là số phần tử bạn có kế hoạch lưu trữ trong HashMap. Điều này sẽ đảm bảo tốc độ lấy/đặt nhanh nhất.

Answer 7

An toàn trong hầu hết các trường hợp là List và Map khởi tạo để thực hiện List hoặc Map với các tham số kích thước sau.

List<T>(numElements + (numElements/2)); 
Map<T,T>(numElements + (numElements/2)); 

này sau sự cai trị .75 cũng như tiết kiệm chi phí ít hơn các hoạt động * 2 mô tả ở trên.

Answer 8

Tôi chạy một số unit tests để xem những câu trả lời là đúng và nó bật ra rằng việc sử dụng:

(int) Math.ceil(requiredCapacity/loadFactor); 

như công suất ban đầu cho những gì bạn muốn cho cả một HashMap hoặc một Hashtable. Bởi "những gì bạn muốn" Tôi có nghĩa là thêm requiredCapacity các yếu tố vào bản đồ sẽ không gây ra mảng mà nó gói để thay đổi kích thước và mảng sẽ không lớn hơn yêu cầu. Kể từ khi công suất tải mặc định là 0,75, khởi tạo một HashMap như vậy hoạt động:

... = new HashMap<KeyType, ValueType>((int) Math.ceil(requiredCapacity/0.75)); 

Từ một HashSet là một cách hiệu quả chỉ là một wrapper cho một HashMap, logic tương tự cũng được áp dụng ở đó, ví dụ:bạn có thể xây dựng một HashSet hiệu quả như thế này: câu trả lời

.... = new HashSet<TypeToStore>((int) Math.ceil(requiredCapacity/0.75)); 

@Yuval của Adam là đúng cho mọi trường hợp trừ trường hợp (requiredCapacity/0.75) là một sức mạnh của 2, trong trường hợp này nó phân bổ quá nhiều bộ nhớ.
@ câu trả lời NotEdible của sử dụng quá nhiều bộ nhớ trong nhiều trường hợp, như constructor của HashMap tự quyết các vấn đề mà nó muốn mảng bản đồ để có một kích thước mà là một sức mạnh của 2.

Answer 9

Trong guava libraries từ Google có được một chức năng mà tạo ra một HashMap tối ưu hóa cho một số dự kiến ​​các hạng mục: newHashMapWithExpectedSize

từ các tài liệu:

tạo một trường hợp HashMap, với mức cao đủ "công suất ban đầu" mà nó nên giữ yếu tố expectedSize mà không tăng trưởng ...