HashMap với ~ 100 triệu phím, vẫn không đổi?

Question

Có ai biết câu trả lời cho câu hỏi này không?

Answer 1

Có. Để tìm kiếm bản đồ băm có 100 triệu mục được thêm vào đó, bạn thực hiện việc này:

1) Tính băm của đối tượng bạn đang tìm kiếm.
2) Tìm nhóm đó
3) Tìm kiếm thông qua nhóm đó cho mục đó.

(1) độc lập với kích thước bản đồ băm hoặc số mục trong đó.
(2) là O (1), giả định một hashmap chuẩn được triển khai dưới dạng một danh sách liên kết.
(3) mất một khoảng thời gian liên quan đến số lượng mục trong nhóm, khoảng thời gian này sẽ xấp xỉ (số lượng mục được thêm vào băm)/(số lượng nhóm). Phần này sẽ bắt đầu tại O (1), nhưng sẽ tăng rất chậm vì số lượng các mục bắt đầu vượt quá số lượng xô.

Với hầu hết mọi mục đích, Hash Maps có thể được coi là O (1) cho cả chèn và truy xuất, ngay cả với các tập dữ liệu rất lớn, miễn là bạn bắt đầu với số lượng nhóm đủ lớn.

Answer 2

Có, vẫn không đổi thời gian (khấu hao).