Độ phức tạp thời gian của thao tác get() và put() trong HashMap
Độ phức tạp thời gian của thao tác get() và put() trong HashMap
get() và put() của HashMap có độ phức tạp O(1) trung bình (amortized với put) khi hàm băm phân bố đều và load factor hợp lý. Trường hợp xấu nhất là O(n) nếu mọi khoá rơi vào cùng một bucket (Java 7 trở về trước), và O(log n) từ Java 8 nhờ bucket được chuyển thành cây đỏ-đen.
Vì sao trung bình là O(1):
hashCode() của khoá, Java trộn thêm bit cao: h ^ (h >>> 16).(n - 1) & hash, với n là dung lượng mảng (luôn là luỹ thừa của 2).hash và equals() trong bucket.Nhờ load factor mặc định 0.75, mỗi bucket chỉ có vài phần tử nên mọi bước là hằng số.
Vì sao put() là O(1) amortized: khi số phần tử vượt capacity * loadFactor (mặc định 16 * 0.75 = 12), HashMap resize gấp đôi mảng và phân bố lại toàn bộ phần tử, tốn O(n). Nhưng resize hiếm nên chi phí chia đều cho mỗi lần put vẫn là O(1).
Đăng nhập để tham gia thảo luận cùng mọi người.
Chưa có bình luận nào
Hãy là người đầu tiên chia sẻ suy nghĩ của bạn.