Tại sao một cửa hàng HashTable giá trị băm của khóa trong bảng trong java

Question

tôi đang trải qua việc thực hiện các phương pháp đặt cho một Hashtable Java và đã xem qua này:

// Makes sure the key is not already in the hashtable. 
    Entry tab[] = table; 
    int hash = key.hashCode(); 
    int index = (hash & 0x7FFFFFFF) % tab.length; 
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { 
     if ((e.hash == hash) && e.key.equals(key)) { 
      V old = e.value; 
      e.value = value; 
      return old; 
     } 
    } 

Trong khi tôi hiểu rằng một chìa khóa là cần thiết để kiểm tra va chạm, tại sao Java lưu trữ giá trị băm của khóa và cũng kiểm tra nó?

Answer 1

Vì cùng một nhóm (tab) có thể chứa các mục có băm khác nhau do hoạt động % tab.length. Kiểm tra băm đầu tiên có lẽ là một số tối ưu hóa hiệu suất để tránh gọi số equals() nếu băm khác nhau.

Để đặt điều này trong ví dụ: Giả sử bạn có hai đối tượng phức tạp với phương thức equals() tốn kém. Một đối tượng có hàm băm bằng 1 trong khi đối tượng kia có băm 32. Nếu bạn đặt cả hai đối tượng trong một bảng băm có 31 nhóm, chúng sẽ kết thúc trong cùng một nhóm (tab). Khi thêm một đối tượng thứ hai (đối tượng khác), bạn phải chắc chắn rằng nó chưa có trong bảng. Bạn có thể sử dụng ngay equals() nhưng điều này có thể chậm hơn. Thay vào đó bạn lần đầu tiên so sánh băm, tránh tốn kém equals() nếu không cần thiết. Trong ví dụ này băm là khác nhau (mặc dù đang ở trong cùng một nhóm) vì vậy equals() là không cần thiết.

Answer 2

Nó giúp truy cập nhanh hơn, vì giá trị băm không cần phải được tính toán lại cho mọi truy cập. Điều này không chỉ quan trọng đối với các tìm kiếm tường minh (trong đó hàm băm được kiểm tra trước khi thực hiện equals) mà còn để phục hồi.