Bài báo
Bắt đầu
Bắt đầu học
JavaRush /Blog Java /Random-VI /Bộ băm trong Java
渚古河
Mức độ
Москва

Bộ băm trong Java

Xuất bản trong nhóm
Lớp này HashSettriển khai giao diện Set, dựa trên bảng băm và cũng được hỗ trợ bởi một thể hiện HashMap. Vì HashSetcác phần tử không được sắp xếp theo thứ tự nên không có gì đảm bảo rằng các phần tử sẽ có cùng thứ tự sau một thời gian. Các hoạt động thêm, xóa và tìm kiếm sẽ được thực hiện trong thời gian không đổi, miễn là hàm băm phân phối chính xác các phần tử vào “nhóm”, điều này sẽ được thảo luận sau. Bộ băm trong Java - 1Một vài điểm quan trọng về HashSet:
  • Bởi vì lớp thực hiện giao diện Set, nó chỉ có thể lưu trữ các giá trị duy nhất;
  • Có thể lưu trữ giá trị NULL;
  • Thứ tự thêm các phần tử được tính bằng mã băm;
  • HashSetcũng thực hiện Serializablevà Cloneable.
Để duy trì thời gian thực hiện liên tục của các hoạt động, thời gian dành cho các hành động với HashSet, phải tỷ lệ thuận với số phần tử trong HashSet+ “công suất” của phiên bản tích hợp sẵn HashMap(số lượng “giỏ”). Vì vậy, để duy trì hiệu suất, điều quan trọng là không đặt công suất ban đầu quá cao (hoặc hệ số tải quá thấp). Dung lượng ban đầu – số lượng ô ban đầu (“thùng”) trong bảng băm. Nếu tất cả các ô được điền, số lượng của chúng sẽ tự động tăng lên. Hệ số tải là thước đo mức độ đầy của nó HashSettrước khi công suất của nó tự động tăng lên. Khi số phần tử trong HashSetlớn hơn tích của dung lượng ban đầu và hệ số tải, bảng băm được băm lại (mã băm của các phần tử được tính toán lại và bảng được xây dựng lại theo giá trị thu được) và số số lượng tế bào trong đó tăng gấp đôi. Hệ số tải = Số phần tử được lưu trữ trong bảng / kích thước bảng băm Ví dụ: nếu số ô ban đầu trong bảng là 16 và hệ số tải là 0,75, thì khi số lượng ô được điền đạt tới 12, thì hệ số tải sẽ số lượng tế bào sẽ tự động tăng lên. Hệ số tải và công suất ban đầu là hai yếu tố chính ảnh hưởng đến hiệu suất của HashSet. Hệ số tải trung bình là 0,75 mang lại hiệu suất tốt. Nếu tham số này tăng lên thì tải bộ nhớ sẽ giảm (vì nó sẽ giảm số lần băm lại và xây dựng lại), nhưng nó sẽ ảnh hưởng đến các hoạt động nối thêm và tra cứu. Để giảm thiểu thời gian băm lại, bạn cần chọn thông số dung lượng ban đầu phù hợp. Nếu dung lượng ban đầu lớn hơn số phần tử tối đa chia cho hệ số tải thì sẽ không có hoạt động băm lại nào xảy ra. Quan trọng: HashSetkhông phải là cấu trúc dữ liệu có tính năng đồng bộ hóa tích hợp, vì vậy nếu nhiều luồng đang hoạt động trên nó cùng một lúc và ít nhất một trong số chúng đang cố gắng thực hiện các thay đổi thì cần phải cung cấp quyền truy cập được đồng bộ hóa từ bên ngoài. Điều này thường được thực hiện với chi phí là một đối tượng được đồng bộ hóa khác đang đóng gói HashSet. Nếu không có đối tượng như vậy thì Collections.synchronizedSet(). Đây hiện là cách tốt nhất để ngăn chặn các hoạt động không đồng bộ với HashSet.
Java-университет 
Set s = Collections.synchronizedSet(new HashSet(...));
Các hàm tạo HashSet:
  1. HashSet h = new HashSet(); - nhà xây dựng mặc định. Công suất ban đầu mặc định là 16, hệ số tải là 0,75.
  2. HashSet h = new HashSet(int initialCapacity)– một hàm tạo với công suất ban đầu nhất định. Hệ số tải – 0,75.
  3. HashSet h = new HashSet(int initialCapacity, float loadFactor);- một nhà xây dựng có công suất ban đầu và hệ số tải nhất định.
  4. HashSet h = new HashSet(Collection C)– một hàm tạo thêm các phần tử từ một bộ sưu tập khác.
Đoạn mã dưới đây thể hiện một số phương pháp HashSet: 
import java.util.*;

class Test
{
    public static void main(String[]args)
    {
        HashSet<String> h = new HashSet<String>();

        // Add elements to the HashSet using the add() method
        h.add("India");
        h.add("Australia");
        h.add("South Africa");
        h.add("India");// try to add another same element

        // Print the elements of the HashSet to the console
        System.out.println(h);
        System.out.println("List contains India or not:" +
                           h.contains("India"));

        // Remove elements from the set using the remove() method
        h.remove("Australia");
        System.out.println("List after removing Australia:"+h);

        // Loop through the elements of the HashSet using an iterator:
        System.out.println("Iterating over list:");
        Iterator<String> i = h.iterator();
        while (i.hasNext())
            System.out.println(i.next());
    }
}
Phần kết luận: 
[South Africa, Australia, India]
List contains India or not:true
List after removing Australia:[South Africa, India]
Iterating over list:
South Africa
India
Tất cả các lớp triển khai một giao diện Setđều được hỗ trợ nội bộ bởi các triển khai Map. HashSetlưu trữ các phần tử bằng cách sử dụng HashMap. Mặc dù HashMapmột phần tử phải được biểu diễn dưới dạng cặp khóa-giá trị để thêm phần tử vào nhưng HashSetchỉ có giá trị được thêm vào. Trong thực tế, giá trị chúng ta chuyển đến HashSetlà khóa của đối tượng HashMapvà một hằng số được sử dụng làm giá trị HashMap. Bằng cách này, trong mỗi cặp khóa-giá trị, tất cả các khóa sẽ có cùng giá trị. Triển khai HashSettại java doc: 
private transient HashMap map;

// Constructor - 1
// All constructors implicitly create a HashMap object.
public HashSet()
{
    // Create an implicit HashMap object
    map = new HashMap();
}

// Constructor- 2
public HashSet(int initialCapacity)
{
    // Create an implicit HashMap object
    map = new HashMap(initialCapacity);
}

// An object of the Object class, each time acting as a value in the HashMap
private static final Object PRESENT = new Object();
Nếu bạn nhìn vào phương pháp add()y HashSet: 
public boolean add(E e)
{
   return map.put(e, PRESENT) == null;
}
Bạn có thể nhận thấy rằng phương thức add()y HashSetgọi phương thức put()trên đối tượng bên trong HashMap, truyền cho nó phần tử cần thêm làm khóa và hằng số HIỆN TẠI làm giá trị. Phương pháp này hoạt động theo cách tương tự remove(). Nó gọi phương thức remove()đối tượng bên trong HashMap: 
public boolean remove(Object o)
{
  return map.remove(o) == PRESENT;
}
HashSetdựa trên bảng băm và các hoạt động thêm, xóa hoặc tra cứu trung bình sẽ hoàn thành trong thời gian không đổi (O(1)) . Phương pháp HashSet:
  1. boolean add(E e): thêm một phần tử vào HashSet, nếu không có phần tử nào, nhưng nếu phần tử đó đã có sẵn thì phương thức trả về false .
  2. void clear():loại bỏ tất cả các phần tử khỏi một tập hợp.
  3. boolean contains(Object o): Trả về true nếu phần tử đã cho có mặt trong tập hợp.
  4. boolean remove(Object o): Loại bỏ phần tử đã cho khỏi tập hợp, nếu có.
  5. Iterator iterator(): Trả về một iterator cho các phần tử của tập hợp.
  6. boolean isEmpty(): Trả về true nếu không có phần tử nào trong tập hợp.
  7. Object clone(): Thực hiện nhân bản bề mặt HashSet.
Javadoc: https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html
Bình luận
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION