HashSet dalam Java

Kelas HashSetmelaksanakan antara muka Set, adalah berdasarkan jadual cincang, dan juga disokong oleh contoh HashMap. Oleh kerana HashSetunsur-unsur tidak disusun, tiada jaminan bahawa unsur-unsur akan berada dalam susunan yang sama selepas beberapa ketika. Operasi menambah, memadam dan mencari akan dilakukan dalam masa yang tetap, dengan syarat fungsi cincang mengagihkan elemen dengan betul ke dalam "baldi", yang akan dibincangkan kemudian. Beberapa perkara penting tentang HashSet:

• Kerana kelas melaksanakan antara muka Set, ia hanya boleh menyimpan nilai unik;
• Boleh menyimpan nilai NULL;
• Susunan elemen ditambah dikira menggunakan kod cincang;
• HashSetjuga melaksanakan Serializabledan Cloneable.

Untuk mengekalkan masa pelaksanaan operasi yang berterusan, masa yang dibelanjakan untuk tindakan dengan HashSet, mestilah berkadar terus dengan bilangan elemen dalam HashSet+ "kapasiti" contoh terbina dalam HashMap(bilangan "bakul"). Oleh itu, untuk mengekalkan prestasi, adalah penting untuk tidak menetapkan kapasiti awal terlalu tinggi (atau faktor beban terlalu rendah). Kapasiti awal – bilangan awal sel (“tong sampah”) dalam jadual cincang. Jika semua sel diisi, bilangannya akan meningkat secara automatik. Faktor beban ialah ukuran seberapa penuh ia boleh HashSetsebelum kapasitinya meningkat secara automatik. Apabila bilangan elemen dalam HashSetmenjadi lebih besar daripada produk kapasiti awal dan faktor beban, jadual cincang dicincang semula (kod cincang elemen dikira semula dan jadual dibina semula mengikut nilai yang diperoleh) dan nombor sel di dalamnya berganda. Faktor beban = Bilangan elemen yang disimpan dalam jadual / saiz jadual cincang Contohnya, jika bilangan awal sel dalam jadual ialah 16, dan faktor beban ialah 0.75, maka apabila bilangan sel yang diisi mencapai 12, bilangan sel secara automatik akan meningkat. Faktor beban dan kapasiti awal adalah dua faktor utama yang mempengaruhi prestasi HashSet. Faktor beban 0.75 memberikan prestasi yang baik secara purata. Jika parameter ini dinaikkan, maka beban memori akan berkurangan (kerana ia akan mengurangkan bilangan operasi pencincangan semula dan pembinaan semula), tetapi ia akan menjejaskan operasi tambah dan carian. Untuk meminimumkan masa yang dihabiskan untuk pencincangan semula, anda perlu memilih parameter kapasiti awal yang betul. Jika kapasiti awal lebih besar daripada bilangan maksimum elemen dibahagikan dengan faktor beban, maka tiada operasi pencincangan semula akan berlaku sama sekali. Penting: HashSetbukan struktur data dengan penyegerakan terbina dalam, jadi jika berbilang benang berfungsi pada masa yang sama, dan sekurang-kurangnya salah satu daripada mereka cuba membuat perubahan, adalah perlu untuk menyediakan akses yang disegerakkan dari luar. Ini sering dilakukan dengan mengorbankan objek disegerakkan lain yang merangkum HashSet. Jika tidak ada objek sedemikian, maka Collections.synchronizedSet(). Pada masa ini, ini ialah cara terbaik untuk mengelakkan operasi tidak segerak dengan HashSet.

Set s = Collections.synchronizedSet(new HashSet(...));

Pembina HashSet:

1. HashSet h = new HashSet(); - pembina lalai. Kapasiti awal lalai ialah 16, faktor beban ialah 0.75.
2. HashSet h = new HashSet(int initialCapacity)– pembina dengan kapasiti awal yang diberikan. Faktor beban – 0.75.
3. HashSet h = new HashSet(int initialCapacity, float loadFactor);— pembina dengan kapasiti awal dan faktor beban yang diberikan.
4. HashSet h = new HashSet(Collection C)– pembina yang menambah elemen daripada koleksi lain.

Kod di bawah menunjukkan beberapa kaedah 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());
    }
}

Kesimpulan:

[South Africa, Australia, India]
List contains India or not:true
List after removing Australia:[South Africa, India]
Iterating over list:
South Africa
India

Semua kelas yang melaksanakan antara muka Setdisokong secara dalaman oleh pelaksanaan Map. HashSetmenyimpan elemen menggunakan HashMap. Walaupun HashMapelemen mesti diwakili sebagai pasangan nilai kunci untuk menambah elemen, HashSethanya nilai yang ditambahkan. Malah, nilai yang kita berikan HashSetialah kunci kepada objek HashMap, dan pemalar digunakan sebagai nilai HashMap. Dengan cara ini, dalam setiap pasangan nilai kunci, semua kunci akan mempunyai nilai yang sama. Pelaksanaan HashSetdalam 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();

Jika anda melihat kaedah add()y HashSet:

public boolean add(E e)
{
   return map.put(e, PRESENT) == null;
}

Anda boleh perhatikan bahawa kaedah add()y HashSetmemanggil kaedah put()pada objek dalaman HashMap, memberikannya elemen untuk ditambahkan sebagai kunci, dan pemalar PRESENT sebagai nilai. Kaedah ini berfungsi dengan cara yang sama remove(). Ia memanggil kaedah remove()objek dalaman HashMap:

public boolean remove(Object o)
{
  return map.remove(o) == PRESENT;
}

HashSetadalah berdasarkan jadual cincang, dan operasi tambah, padam atau cari akan, secara purata, lengkap dalam masa malar (O(1)) . Kaedah HashSet:

1. boolean add(E e): menambah elemen kepada HashSet, jika tidak ada, tetapi jika elemen sedemikian sudah ada, kaedah mengembalikan false .
2. void clear():mengalih keluar semua elemen daripada set.
3. boolean contains(Object o): Mengembalikan benar jika elemen yang diberikan hadir dalam set.
4. boolean remove(Object o): Mengeluarkan elemen yang diberikan daripada set, jika ada.
5. Iterator iterator(): Mengembalikan lelaran untuk elemen set.
6. boolean isEmpty(): Mengembalikan benar jika tiada unsur dalam set.
7. Object clone(): Melakukan pengklonan permukaan HashSet.

Javadoc: https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html