Bảng băm Java

Lớp Java Hashtable là một trong những thành viên lâu đời nhất của Java Collection Framework. Nó là một triển khai của cấu trúc dữ liệu bảng băm toán học. Trong Java hashtable bên trong chứa các nhóm lưu trữ các cặp khóa/giá trị. Hashtable khá giống với HashMap . Sự khác biệt đáng kể nhất giữa chúng: Hashtable được đồng bộ hóa trong khi HashMap thì không.

Hashtable như một cấu trúc dữ liệu

Hashtable là một cấu trúc dữ liệu nơi dữ liệu được lưu trữ ở định dạng mảng. Mỗi giá trị dữ liệu có một giá trị khóa duy nhất. Nếu khóa được biết, việc truy cập vào dữ liệu cần thiết rất nhanh. Vì vậy, các thao tác chèn và tìm kiếm diễn ra nhanh chóng độc lập với kích thước dữ liệu. Bảng băm bao gồm một mảng để giữ dữ liệu và băm để tạo chỉ mục nơi đặt phần tử. Băm là gì? Đó là quy tắc ánh xạ Đối tượng thành một bộ ký tự (mã). Thông thường loại hàm đó sẽ chuyển đổi một phần dữ liệu lớn thành một giá trị số nguyên nhỏ. Các hàm băm có thể khác nhau, nhưng tất cả chúng đều gửi các thuộc tính nhất định:

• Một đối tượng cụ thể có mã băm cụ thể.
• Hai đối tượng bằng nhau có cùng mã băm. Điều ngược lại là không đúng sự thật.
• Nếu hai mã băm khác nhau, các đối tượng chắc chắn không bằng nhau.
• Các đối tượng khác nhau có thể có cùng mã băm. Sự kiện rất hiếm gặp này gọi là va chạm. Hàm băm tốt giảm thiểu xác suất va chạm.

Kết quả của việc áp dụng Hàm băm cho một Đối tượng gọi hashCode .

Bảng băm trong Java

Lớp Hashtable là việc triển khai cấu trúc dữ liệu bảng băm. Bộ sưu tập này được tạo sớm hơn Khung bộ sưu tập Java, nhưng sau đó đã được đưa vào trong đó. Giống như tất cả các bộ sưu tập “sơ khai” (từ Java 1.0), một hashtable được đồng bộ hóa (hầu hết tất cả các phương thức đều được đánh dấu là đã đồng bộ hóa). Vì yếu tố này, hashtable có vấn đề về hiệu suất đáng kể. Do đó, bắt đầu từ Java 1.2, trong hầu hết các trường hợp, nên sử dụng các triển khai khác của giao diện Bản đồ do thiếu đồng bộ hóa. Thông thường HashMap là sự thay thế thích hợp nhất. Vì vậy, Lớp Hashtable<K,V>bao gồm các khóa và giá trị. Nó lưu trữ các khóa theo nguyên tắc băm. Các cặp khóa-giá trị được lưu trữ trong "bộ chứa". Các thùng cùng nhau tạo nên một "bảng", một loại mảng bên trong. Hashtable sử dụng mã băm của khóa để xác định nhóm nơi cặp khóa/giá trị sẽ ánh xạ. Hàm băm cho phép lấy vị trí bộ chứa từ mã băm của Khóa. Hàm này trả về một số nguyên cho một đối tượng. Như chúng tôi đã nói ở trên, hai đối tượng bằng nhau có cùng mã băm, trong khi hai đối tượng không bằng nhau có thể không phải lúc nào cũng có mã băm khác nhau. Các đối tượng khác nhau, được đưa vào một bảng băm có thể có cùng một mã băm. Để giải quyết vấn đề này (xung đột) mảng danh sách được sử dụng trong hashtable. Các cặp được ánh xạ tới một nhóm duy nhất được lưu trữ trong danh sách và tham chiếu danh sách này được lưu trữ trong chỉ mục mảng.

Hashtable Java Constructor

• Hashtable() , hàm tạo mặc định. Nó tạo ra một hashtable trống. (Công suất ban đầu mặc định = 11, hệ số tải = 0,75).
• Hashtable(int size) xây dựng một hashtable có kích thước được chỉ định.
• Hashtable(int size, float fillRatio) tạo bảng băm có kích thước và tỷ lệ lấp đầy được chỉ định.
• Hashtable(Map m) tạo một hashtable có cùng ánh xạ với Map đã cho.

Tuyên bố Hashtable

Lớp Hashtable Java triển khai các giao diện Map , Cloneable và Serializable . Nó mở rộng lớp Dictionary .

Hashtable.java
public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable

K là loại khóa được duy trì bởi bản đồ. V là loại giá trị được ánh xạ. Ví dụ:

Hashtable<Student, Integer> myHTable = new Hashtable<>();

Cách nhập hashtable java

Java Hashtable nằm trong gói java.util . Vì vậy, hãy sử dụng nhập java.util.Hashtable; trong mã của bạn. Thông thường, bạn sẽ nhận được gợi ý từ IDE của mình về điều này.

Các hoạt động chính của Hashtable

Các hoạt động chính của Hashtable là nhận, chèn vào bộ sưu tập và xóa khỏi đó. Ở đây ba hoạt động này là:

• Lấy đối tượng(Khóa đối tượng) trả về giá trị của Đối tượng đã chỉ định khóa. Trả về null nếu không tìm thấy khóa như vậy.
• Đặt đối tượng (Khóa đối tượng, Giá trị đối tượng) ánh xạ khóa đã chỉ định với giá trị đã chỉ định. Cả khóa và giá trị đều không thể rỗng.
Xóa đối tượng(Khóa đối tượng) xóa mục nhập (khóa và giá trị tương ứng) khỏi bảng băm.

Các thao tác quan trọng khác:

• int size() trả về số lượng mục nhập trong bảng băm.
• boolean contains(Object value) kiểm tra xem giá trị đã chỉ định có trong bảng băm hay không. Nếu vậy, phương thức trả về true, ngược lại trả về false.
• boolean containsValue(Object value) kiểm tra xem giá trị đã chỉ định có trong bảng băm hay không. Nếu vậy, phương thức trả về true, ngược lại trả về false.
• void clear() xóa tất cả các mục khỏi bảng băm.
• boolean containsKey(Khóa đối tượng) trả về true nếu khóa được chỉ định tồn tại trong bảng băm, nếu không thì trả về false.
• boolean isEmpty() trả về true nếu bảng băm trống hoặc trả về false nếu nó chứa ít nhất một khóa.
• void rehash() tăng kích thước của hashtable và rehash tất cả các khóa của nó.

Thực hiện bảng băm, mã Java:

Hãy tạo một lớp Sinh viên :

import java.util.Date;
public class Student {
   String surname;
   String name;
   String secondName;
   Long birthday; // Long instead of long is used by Gson/Jackson json parsers and various orm databases

   public Student(String surname, String name, String secondName, Date birthday ){
       this.surname = surname;
       this.name = name;
       this.secondName = secondName;
       this.birthday = birthday == null ? 0 : birthday.getTime();
   }

   @Override
   public int hashCode(){
       //TODO: check for nulls
       return (surname + name + secondName + birthday).hashCode();
   }
   @Override
   public boolean equals(Object other_) {
       Student other = (Student)other_;
       return (surname == null || surname.equals(other.surname) )
               && (name == null || name.equals(other.name))
               && (secondName == null || secondName.equals(other.secondName))
               && (birthday == null || birthday.equals(other.birthday));
   }
}

Đây là ví dụ Java Hashtable . Hãy đặt hai Đối tượng của lớp Sinh viên vào hashtable, sau đó loại bỏ một số và kiểm tra một số tham số.

public class HashTableExample {
   public static void main(String[] args) {
 
       Hashtable<Student, Integer> myHTable = new Hashtable<>();
       Student sarah1 = new Student("Sarah","Connor", "Jane", null);
       Student john = new Student("John","Connor", "Kyle", new Date(1985, 02-1, 28)); // date not exists
       myHTable.put(john,1);
       myHTable.put(sarah1,0);
       System.out.println(myHTable.get(john));
       System.out.println(myHTable.isEmpty());
       System.out.println(myHTable.size());
       System.out.println(myHTable.contains(1));
       myHTable.remove(john);
       System.out.println(myHTable.contains(0));
       System.out.println(myHTable.contains(1));
       System.out.println(myHTable.containsKey(sarah1));
   }
}

Kết quả chạy chương trình là:

1
false
2
true
true
false
true

HashMap so với Hashtable

• Hashtable tương tự như HashMap trong Java. Sự khác biệt đáng kể nhất là Hashtable được đồng bộ hóa trong khi HashMap thì không. Do đó, Hashtable chậm hơn HashMap do đồng bộ hóa.
• Ngoại trừ sự cố đồng bộ hóa, Hashtable không cho phép sử dụng null làm giá trị hoặc khóa. HashMap cho phép một khóa null và nhiều giá trị null.
• Hashtable kế thừa lớp Dictionary trong khi HashMap kế thừa lớp AbstractMap.
• HashMap được duyệt bởi Iterator. Hashtable có thể được duyệt qua không chỉ bởi Iterator mà còn bởi Enumerator.

Ví dụ về hashtable Java (Khóa null Hashtable vs HashMap)

Đây là đoạn mã để chứng minh null được sử dụng làm khóa và giá trị trong HashMap và Hashtable

// Null key Java hashtable example and hashmap example  

try{
      System.out.println("Hashtable");
      Hashtable hashTable = new Hashtable();
      hashTable.put(null, new Object());
    }catch(Exception ex){
      ex.printStackTrace();
    }
    System.out.println("HashMap");
    HashMap hashMap = new HashMap();
    hashMap.put(null, new Object());
    System.out.println("as you see no exceptions with null key in HashMap");
  }

Kết quả của việc chạy chương trình chứa đoạn này:

java.lang.NullPointerException
	at java.base/java.util.Hashtable.put(Hashtable.java:480)
	at Character.main(Character.java:58)
HashMap
as you see no exceptions with null key in HashMap

Phần kết luận

Bạn sẽ không thường xuyên sử dụng Hashtable trong các dự án thực tế, nhưng rất dễ gặp cấu trúc dữ liệu này trong các dự án cũ. Dù sao đi nữa, điều quan trọng là phải hiểu Java có Cấu trúc dữ liệu gì và cách chúng hoạt động, ít nhất là cho các cuộc phỏng vấn của bạn. Thông thường, các đối tượng HashMap được sử dụng thay vì Hashtable vì tính tương tự của chúng. HashMap hiệu quả hơn (nó không được đồng bộ hóa) và có thể có null làm khóa.