`HashMap` hoạt động bên trong ra sao, và va chạm được xử lý thế nào?

Phép trộn bit tồn tại vì chỉ số bucket chỉ dùng các bit THẤP của hash. Nếu hashCode() của bạn chỉ khác nhau ở bit cao — chuyện rất hay xảy ra với hash dựa trên địa chỉ hoặc ID tăng dần nhân với số lớn — thì mọi khoá rơi vào cùng một bucket. Dịch phải 16 bit rồi XOR là cách rẻ nhất để bit cao có ảnh hưởng tới chỉ số.

Việc chuyển sang cây có lý do bảo mật chứ không chỉ hiệu năng: trước Java 8, kẻ tấn công có thể gửi hàng nghìn khoá cố tình cùng bucket để biến mọi lần tra cứu thành O(n) — một dạng tấn công từ chối dịch vụ bằng va chạm hash, từng ảnh hưởng nhiều framework web. Cây đỏ-đen chặn kịch bản đó, với điều kiện khoá Comparable.

Về việc resize: nó không rẻ, vì mọi phần tử phải được đặt lại chỗ. Nếu bạn biết trước số phần tử, khởi tạo với capacity phù hợp (new HashMap<>(expected / 0.75f + 1)) tránh được vài lần resize. Đây là một trong ít chỗ tinh chỉnh nhỏ mà đo được lợi ích thật khi map lớn.