Sự khác biệt trong Bản đồ băm của Java 7 và Java 8 khi cả hai hoạt động trên thuật toán phức tạp liên tục là gì? Theo sự hiểu biết của tôi tìm kiếm bản đồ băm trong thời gian liên tục bằng cách tạo ra một khóa băm cho một đối tượng thông qua hàm băm.Sự khác biệt trong bản đồ băm trong java 7 và 8
Trong Java 7 sau khi tính toán hàm băm từ hàm băm nếu có nhiều thì một phần tử có cùng giá trị băm so với tìm kiếm tuyến tính do đó độ phức tạp là (n). Trong Java 8 tìm kiếm đó được thực hiện bằng tìm kiếm nhị phân để độ phức tạp sẽ trở thành nhật ký (n). Vì vậy, khái niệm này là sai, bản đồ băm tìm kiếm một đối tượng phức tạp liên tục bởi vì nó không phải là trường hợp ở tất cả các lần.
Thực ra có một ngưỡng, Nó được mô tả trong JEP180, khi một thùng/bin có nhiều hơn TREEIFY_THRESHOLD = 8 mục, nó sẽ được chuyển thành cây. Trong Java 7, nơi va chạm đã được tìm kiếm tuyến tính có một bảo vệ DOS: một Xord hạt giống ngẫu nhiên với các băm để làm cho chúng ít có thể dự đoán được. Hàm này được loại bỏ trong Java 8. – eckes
Nếu chúng ta đi sâu vào việc thực hiện, nó chính xác là những gì bạn đã giải thích @eckes – MDaniyal
Bạn có thể thấy các vấn đề mới nhất của Chuyên gia Java newsletter rất hữu ích. Nó đi vào chiều sâu thảo luận về băm trong Java trong suốt nhiều năm; ví dụ chỉ ra rằng bạn nên đảm bảo rằng các khóa bản đồ của bạn thực hiện Comparable (khi sử dụng Java8).
@MDaniyal trả lời chính xác mà không sử dụng cụm từ mô tả tình huống của hai hoặc nhiều phần tử có cùng một băm: "băm va chạm". Nếu bạn muốn nhìn sâu hơn vào các va chạm băm nói chung, tôi khuyên bạn nên bắt đầu ở đây: https://en.wikipedia.org/wiki/Hash_table#Collision_resolution – Jeutnarg