Độ phân giải va chạm trong HashMap

Question

Khi chúng tôi đặt cặp khóa-giá trị trong HashMap điều này có thể xảy ra mã băm của hai khóa có thể giống nhau thì cách thức lưu trữ và truy xuất khóa-giá trị này sẽ được xử lý.

Cập nhật

Những gì tôi hiểu cho đến nay là nếu hai chìa khóa đối tượng có cùng một mã băm sau đó cả hai đối tượng chủ chốt sẽ được lưu trữ trong cùng một xô và khi tôi sẽ nói get(key) sau đó ra khỏi hai đối tượng với phù hợp với hashcode yếu tố nào để tìm nạp được quyết định bởi object.equals().

Answer 1

Khi bạn muốn truy xuất một số đối tượng từ hashmap và tồn tại một số đối tượng có cùng mã băm, java sẽ gọi equals() để xác định đúng đối tượng.

Đó là lý do tại sao điều quan trọng là ghi đè equals() khi ghi đè hashCode().

Answer 2

Mỗi nhóm được đại diện bởi một danh sách được liên kết, do đó không có giới hạn, ngoài không gian heap, về số lượng mục nhập trong một nhóm. Có ít nhóm hơn kết quả hashCode có thể, do đó, nhiều mã băm được ánh xạ tới cùng một nhóm, không chỉ các khóa có cùng hashCode.

A hashCode() với nhiều va chạm, hoặc HashMap với quá ít nhóm, có thể tạo một số danh sách được liên kết lâu. Hiệu suất tốt phụ thuộc vào các danh sách được liên kết ngắn, bởi vì giai đoạn cuối cùng trong việc tra cứu là quét tuyến tính của một trong các danh sách được liên kết.

Tôi đồng ý với câu trả lời trước rằng trận đấu tùy thuộc vào cả hai số equals() và hashCode().