HashSet di Jawa

Kelas HashSetmengimplementasikan antarmuka Set, didasarkan pada tabel hash, dan juga didukung oleh sebuah instance HashMap. Karena HashSetunsur-unsurnya tidak terurut, tidak ada jaminan bahwa unsur-unsur tersebut akan berada dalam urutan yang sama setelah beberapa waktu. Operasi penambahan, penghapusan, dan pencarian akan dilakukan dalam waktu yang konstan, asalkan fungsi hash mendistribusikan elemen dengan benar ke dalam “keranjang”, yang akan dibahas nanti. Beberapa poin penting tentang HashSet:

• Karena kelas mengimplementasikan antarmuka Set, ia hanya dapat menyimpan nilai unik;
• Dapat menyimpan nilai NULL;
• Urutan penambahan elemen dihitung menggunakan kode hash;
• HashSetjuga mengimplementasikan Serializabledan Cloneable.

Untuk mempertahankan waktu eksekusi operasi yang konstan, waktu yang dihabiskan untuk tindakan dengan HashSet, harus berbanding lurus dengan jumlah elemen dalam HashSet+ “kapasitas” instance bawaan HashMap(jumlah “keranjang”). Oleh karena itu, untuk menjaga kinerja, penting untuk tidak menetapkan kapasitas awal terlalu tinggi (atau faktor beban terlalu rendah). Kapasitas awal – jumlah awal sel (“bins”) dalam tabel hash. Jika semua sel terisi, jumlahnya akan bertambah secara otomatis. Faktor beban adalah ukuran seberapa penuhnya HashSetsebelum kapasitasnya meningkat secara otomatis. Ketika jumlah elemen HashSetmenjadi lebih besar dari produk kapasitas awal dan faktor beban, tabel hash di-hash ulang (kode hash elemen dihitung ulang dan tabel dibuat ulang sesuai dengan nilai yang diperoleh) dan jumlahnya jumlah sel di dalamnya menjadi dua kali lipat. Faktor beban = Jumlah elemen yang disimpan dalam tabel / ukuran tabel hash Misalnya, jika jumlah sel awal dalam tabel adalah 16, dan faktor bebannya adalah 0,75, maka ketika jumlah sel yang terisi mencapai 12, maka jumlah sel secara otomatis akan bertambah. Faktor beban dan kapasitas awal merupakan dua faktor utama yang mempengaruhi kinerja HashSet. Faktor beban 0,75 rata-rata memberikan kinerja yang baik. Jika parameter ini ditingkatkan, maka beban memori akan berkurang (karena akan mengurangi jumlah hash ulang dan pembangunan kembali), namun hal ini akan memengaruhi operasi penambahan dan pencarian. Untuk meminimalkan waktu yang dihabiskan untuk hashing ulang, Anda perlu memilih parameter kapasitas awal yang tepat. Jika kapasitas awal lebih besar dari jumlah maksimum elemen dibagi faktor beban, maka operasi hashing ulang tidak akan terjadi sama sekali. Penting: HashSetbukan struktur data dengan sinkronisasi bawaan, jadi jika beberapa thread sedang mengerjakannya secara bersamaan, dan setidaknya salah satu dari thread tersebut mencoba melakukan perubahan, maka perlu menyediakan akses tersinkronisasi dari luar. Hal ini sering dilakukan dengan mengorbankan objek tersinkronisasi lain yang merangkum file HashSet. Jika tidak ada objek seperti itu, maka Collections.synchronizedSet(). Saat ini cara terbaik untuk mencegah operasi yang tidak sinkron dengan HashSet.

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

Konstruktor HashSet:

1. HashSet h = new HashSet(); - konstruktor default. Kapasitas awal default adalah 16, faktor beban adalah 0,75.
2. HashSet h = new HashSet(int initialCapacity)– konstruktor dengan kapasitas awal tertentu. Faktor beban – 0,75.
3. HashSet h = new HashSet(int initialCapacity, float loadFactor);— konstruktor dengan kapasitas awal dan faktor beban tertentu.
4. HashSet h = new HashSet(Collection C)– konstruktor yang menambahkan elemen dari koleksi lain.

Kode di bawah ini menunjukkan beberapa metode 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 mengimplementasikan antarmuka Setdidukung secara internal oleh implementasi Map. HashSetmenyimpan elemen menggunakan HashMap. Meskipun HashMapsuatu elemen harus direpresentasikan sebagai pasangan kunci-nilai untuk menambahkan elemen, HashSethanya nilai yang ditambahkan. Faktanya, nilai yang kita teruskan HashSetadalah kunci dari objek tersebut HashMap, dan sebuah konstanta digunakan sebagai nilainya HashMap. Dengan cara ini, di setiap pasangan kunci-nilai, semua kunci akan memiliki nilai yang sama. Implementasi HashSetdi 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 metode add()y HashSet:

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

Anda dapat melihat bahwa metode add()y HashSetmemanggil metode put()pada objek internal HashMap, meneruskannya elemen yang akan ditambahkan sebagai kunci, dan konstanta PRESENT sebagai nilainya. Metode ini bekerja dengan cara yang serupa remove(). Itu memanggil metode remove()objek internal HashMap:

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

HashSetdidasarkan pada tabel hash, dan operasi penambahan, penghapusan, atau pencarian, rata-rata, akan selesai dalam waktu konstan (O(1)) . Metode HashSet:

1. boolean add(E e): menambahkan elemen ke HashSet, jika tidak ada, tetapi jika elemen tersebut sudah ada, metode akan mengembalikan false .
2. void clear():menghapus semua elemen dari satu set.
3. boolean contains(Object o): Mengembalikan nilai benar jika elemen tertentu ada di set.
4. boolean remove(Object o): Menghapus elemen tertentu dari himpunan, jika ada.
5. Iterator iterator(): Mengembalikan iterator untuk elemen himpunan.
6. boolean isEmpty(): Mengembalikan nilai benar jika tidak ada elemen dalam kumpulan.
7. Object clone(): Melakukan kloning permukaan HashSet.

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