HashMap get/put complexity

Question

Chúng tôi được sử dụng để nói rằng các hoạt động HashMapget/put là O (1). Tuy nhiên nó phụ thuộc vào việc thực hiện băm. Băm đối tượng mặc định thực sự là địa chỉ nội bộ trong vùng JVM. Chúng tôi có chắc là đủ tốt để tuyên bố rằng get/put là O (1)?

Bộ nhớ có sẵn là một vấn đề khác. Theo tôi hiểu từ javadocs, HashMapload factor phải bằng 0,75. Điều gì sẽ xảy ra nếu chúng ta không có đủ bộ nhớ trong JVM và load factor vượt quá giới hạn?

Vì vậy, có vẻ như O (1) không được bảo đảm. Liệu nó có ý nghĩa hay tôi đang thiếu một cái gì đó?

Answer 1

Tùy thuộc vào nhiều thứ. Đó là thường là O (1), với một băm phong nha mà chính nó là không đổi ... nhưng bạn có thể có một băm mất nhiều thời gian để tính toán, và nếu có nhiều mục trong bản đồ băm trả về cùng một mã băm, get sẽ phải lặp qua chúng gọi equals trên mỗi người trong số họ để tìm một kết quả phù hợp.

Trong trường hợp xấu nhất, HashMap có tra cứu O (n) do đi qua tất cả các mục nhập trong cùng một nhóm băm (ví dụ: nếu tất cả đều có cùng mã băm). May mắn thay, trường hợp xấu nhất đó không xuất hiện rất thường xuyên trong đời thực, theo kinh nghiệm của tôi. Vì vậy, không, O (1) chắc chắn không được đảm bảo - nhưng nó thường là những gì bạn nên giả định khi xem xét các thuật toán và cấu trúc dữ liệu để sử dụng.

Trong JDK 8, HashMap đã được tinh chỉnh sao cho nếu các phím có thể được so sánh để đặt hàng, thì bất kỳ nhóm đông dân cư nào được triển khai dưới dạng cây, để ngay cả khi có nhiều mục nhập có cùng mã băm, độ phức tạp là O (log n). Điều đó có thể gây ra các vấn đề nếu bạn có một loại khóa nơi mà sự bình đẳng và thứ tự khác nhau, tất nhiên.

Và có, nếu bạn không có đủ bộ nhớ cho bản đồ băm, bạn sẽ gặp sự cố ... nhưng điều đó sẽ đúng với bất kỳ cấu trúc dữ liệu nào bạn sử dụng.

Answer 2

Tôi không chắc chắn mã băm mặc định là địa chỉ - tôi đã đọc nguồn OpenJDK để tạo mã băm cách đây một thời gian, và tôi nhớ nó là một thứ phức tạp hơn một chút. Vẫn không phải cái gì đó đảm bảo một phân phối tốt, có lẽ. Tuy nhiên, đó là để một số mức độ tranh luận, như vài lớp học bạn muốn sử dụng như là chìa khóa trong một hashmap sử dụng hashcode mặc định - họ cung cấp triển khai của riêng mình, mà nên được tốt. Ngoài ra, những gì bạn có thể không biết (một lần nữa, điều này được dựa trên nguồn đọc - nó không được đảm bảo) là HashMap khuấy băm trước khi sử dụng nó, để trộn entropy từ khắp các từ vào các bit dưới cùng, đó là nơi mà nó cần thiết cho tất cả, nhưng những hashmaps lớn nhất. Điều đó giúp đối phó với băm mà cụ thể không làm điều đó bản thân, mặc dù tôi không thể nghĩ ra bất kỳ trường hợp phổ biến mà bạn muốn thấy điều đó.

Cuối cùng, điều gì xảy ra khi bảng bị quá tải là nó biến thành một tập hợp các danh sách liên kết song song - hiệu suất trở thành O (n). Cụ thể, số lượng các liên kết đi ngang sẽ trung bình là một nửa hệ số tải.

Answer 3

Nó đã được đề cập rằng các hashmaps là trung bình O(n/m), nếu n là số lượng mục và m là kích thước. Nó cũng đã được đề cập rằng về nguyên tắc toàn bộ điều có thể sụp đổ vào một danh sách liên kết đơn lẻ với thời gian truy vấn O(n). (Điều này giả định rằng việc tính toán băm là thời gian cố định).

Tuy nhiên những gì không thường được đề cập là, với xác suất ít nhất 1-1/n (vì vậy đối với 1000 mục là 99,9% cơ hội), nhóm lớn nhất sẽ không được lấp đầy hơn O(logn)! Do đó phù hợp với độ phức tạp trung bình của cây tìm kiếm nhị phân. (Và hằng số là tốt, một ràng buộc chặt chẽ hơn là (log n)*(m/n) + O(1)).

Tất cả những gì cần thiết cho giới hạn lý thuyết này là bạn sử dụng hàm băm hợp lý tốt (xem Wikipedia: Universal Hashing. Nó có thể đơn giản như a*x>>m). Và tất nhiên là người đưa cho bạn các giá trị để băm không biết bạn đã chọn các hằng số ngẫu nhiên của mình như thế nào.

TL; DR: Với xác suất rất cao, trường hợp xấu nhất nhận/đặt độ phức tạp của băm là O(logn).

Answer 4

Hoạt động HashMap là yếu tố phụ thuộc của việc triển khai hashCode. Đối với kịch bản lý tưởng cho phép nói việc thực hiện băm tốt cung cấp mã băm duy nhất cho mọi đối tượng (Không có va chạm băm) thì trường hợp tốt nhất, xấu nhất và trung bình sẽ là O (1). Hãy xem xét một kịch bản trong đó việc triển khai mã băm nhỏ luôn luôn trả về 1 hoặc băm như vậy mà có xung đột băm. Trong trường hợp này độ phức tạp thời gian sẽ là O (n).

Bây giờ đến phần thứ hai của câu hỏi về bộ nhớ, sau đó có ràng buộc bộ nhớ sẽ được JVM quan tâm.