Hiệu suất của HashMap với công suất ban đầu khác nhau và hệ số tải

Question

Đây là tình huống của tôi. Tôi đang sử dụng hai java.util.HashMap để lưu trữ một số dữ liệu thường được sử dụng trong một ứng dụng web Java chạy trên Tomcat. Tôi biết chính xác số lượng các mục nhập vào mỗi Hashmap. Các phím sẽ là chuỗi và int tương ứng.

Câu hỏi của tôi là, cách tốt nhất để đặt công suất ban đầu và máy tính tải là gì?

Tôi có nên đặt dung lượng bằng số lượng phần tử sẽ có và khả năng tải lên 1.0 không? Tôi muốn có hiệu suất tốt nhất tuyệt đối mà không cần sử dụng quá nhiều bộ nhớ. Tuy nhiên, tôi sợ rằng bàn sẽ không lấp đầy tối ưu. Với một bảng kích thước chính xác cần thiết, sẽ không có va chạm chính, gây ra một (thường ngắn) quét để tìm các yếu tố chính xác?

Giả sử (và đây là một đoạn dài) hàm băm là một mod đơn giản 5 của các phím số nguyên, điều đó có nghĩa là các phím 5, 10, 15 sẽ trúng cùng một nhóm và sau đó gây ra tìm kiếm các thùng bên cạnh chúng? Liệu hiệu suất tăng cường công suất ban đầu lớn hơn?

Ngoài ra, nếu có cơ sở hạ tầng tốt hơn so với băm bản đồ cho điều này, tôi cũng hoàn toàn mở cửa cho điều đó.

Answer 1

Trong sự vắng mặt của một hàm băm hoàn hảo cho dữ liệu của bạn, và giả định rằng điều này thực sự không phải là một vi-tối ưu hóa của một cái gì đó thực sự không quan trọng, tôi sẽ thử như sau:

Giả tải mặc định dung lượng (0,75) được HashMap sử dụng là một giá trị tốt trong hầu hết các trường hợp. Trong trường hợp đó, bạn có thể sử dụng nó và thiết lập dung lượng ban đầu của HashMap dựa trên kiến ​​thức của riêng bạn về số lượng mục sẽ giữ - đặt nó sao cho dung lượng ban đầu x .75 = số mục (làm tròn).

Nếu đó là bản đồ lớn hơn, trong trường hợp tra cứu tốc độ cao thực sự quan trọng, tôi khuyên bạn nên sử dụng một số loại trie thay vì bản đồ băm. Đối với các chuỗi dài, trong các bản đồ lớn, bạn có thể tiết kiệm không gian, và một thời gian, bằng cách sử dụng một cấu trúc dữ liệu định hướng chuỗi hơn, chẳng hạn như một trie.

Answer 2

Mục nhập được phân bổ cho các nhóm theo cách ngẫu nhiên. Vì vậy, ngay cả khi bạn có nhiều thùng như mục, một số thùng sẽ có va chạm.

Nếu bạn có nhiều nhóm hơn, bạn sẽ có ít va chạm hơn. Tuy nhiên, nhiều nhóm hơn có nghĩa là trải rộng trong bộ nhớ và do đó chậm hơn. Nói chung một yếu tố tải trong khoảng 0,7-0,8 là gần như tối ưu, do đó, nó có lẽ không có giá trị thay đổi.

Như mọi khi, nó có thể có giá trị profiling trước khi bạn bị treo lên trên microtuning những điều này.

Answer 3

Giả sử (và điều này là một đoạn) là hàm băm là một mod đơn giản 5 của các phím số nguyên

Nó không phải. Từ HashMap.java:

static int hash(int h) { 
    // This function ensures that hashCodes that differ only by 
    // constant multiples at each bit position have a bounded 
    // number of collisions (approximately 8 at default load factor). 
    h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 
} 

Tôi thậm chí không giả vờ tôi hiểu điều đó, nhưng có vẻ như nó được thiết kế để xử lý tình huống đó.

Cũng lưu ý rằng số lượng nhóm cũng luôn là sức mạnh của 2, bất kể bạn yêu cầu kích thước nào.

Answer 4

Tôi tìm thấy nó tốt nhất không để fiddle xung quanh với các thiết lập mặc định, trừ khi tôi thực sự thực sự cần phải.

Điểm phát sóng làm tốt công việc tối ưu hóa cho bạn.

Trong mọi trường hợp; Tôi sẽ sử dụng một profiler (Say Netbeans Profiler) để đo lường vấn đề đầu tiên.

Chúng tôi thường lưu trữ bản đồ với 10000 phần tử và nếu bạn có bằng và thực thi mã băm tốt (và chuỗi và số nguyên), điều này sẽ tốt hơn bất kỳ thay đổi tải nào bạn có thể thực hiện.

Answer 5

Giả sử rằng hàm băm của bạn là "tốt", điều tốt nhất cần làm là đặt kích thước ban đầu thành số lượng dự kiến ​​của các phần tử, giả sử rằng bạn có thể có được ước tính tốt với giá rẻ. Đó là một ý tưởng tốt để làm điều này bởi vì khi một HashMap thay đổi kích thước nó phải tính toán lại giá trị băm cho mỗi khóa trong bảng.

Giữ nguyên hệ số tải tại 0.75. Giá trị của 0.75 đã được chọn theo kinh nghiệm như là một sự thỏa hiệp tốt giữa hiệu năng tra cứu băm và sử dụng không gian cho mảng băm chính. Khi bạn đẩy hệ số tải lên, thời gian tra cứu trung bình sẽ tăng đáng kể.

Nếu bạn muốn đào sâu vào toán học của hành vi bảng băm: Donald Knuth (1998). Nghệ thuật lập trình máy tính '. 3: Sắp xếp và Tìm kiếm (chỉnh sửa lần 2). Addison-Wesley. trang 513–558. ISBN 0-201-89685-0.