HashSet in Java

Die Klasse HashSetimplementiert die Schnittstelle Set, basiert auf einer Hash-Tabelle und wird auch von einer Instanz unterstützt HashMap. Da HashSetdie Elemente nicht geordnet sind, gibt es keine Garantie dafür, dass die Elemente nach einiger Zeit in derselben Reihenfolge sind. Die Vorgänge des Hinzufügens, Löschens und Suchens werden in konstanter Zeit ausgeführt, vorausgesetzt, dass die Hash-Funktion die Elemente korrekt in „Buckets“ verteilt, worauf später noch eingegangen wird. Ein paar wichtige Punkte zu HashSet:

• Weil Die Klasse implementiert die Schnittstelle Setund kann nur eindeutige Werte speichern.
• Kann NULL-Werte speichern;
• Die Reihenfolge, in der Elemente hinzugefügt werden, wird mithilfe eines Hash-Codes berechnet.
• HashSetimplementiert auch die Serializableund Cloneable.

Um eine konstante Ausführungszeit von Operationen aufrechtzuerhalten, HashSetmuss die für Aktionen mit aufgewendete Zeit direkt proportional zur Anzahl der Elemente in HashSet+ der „Kapazität“ der integrierten Instanz HashMap(der Anzahl der „Körbe“) sein. Um die Leistung aufrechtzuerhalten, ist es daher wichtig, die Anfangskapazität nicht zu hoch (oder den Lastfaktor zu niedrig) einzustellen. Anfangskapazität – die anfängliche Anzahl von Zellen („Bins“) in der Hash-Tabelle. Wenn alle Zellen gefüllt sind, erhöht sich deren Anzahl automatisch. Der Ladefaktor ist ein Maß dafür, wie voll es sein kann, HashSetbevor sich seine Kapazität automatisch erhöht. Wenn die Anzahl der Elemente HashSetgrößer wird als das Produkt aus Anfangskapazität und Auslastungsfaktor, wird die Hash-Tabelle erneut gehasht (die Hash-Codes der Elemente werden neu berechnet und die Tabelle wird entsprechend den erhaltenen Werten neu erstellt) und die Anzahl ermittelt der darin enthaltenen Zellen wird verdoppelt. Ladefaktor = Anzahl der in der Tabelle gespeicherten Elemente / Hash-Tabellengröße . Wenn die anfängliche Anzahl der Zellen in der Tabelle beispielsweise 16 beträgt und der Ladefaktor 0,75 beträgt, folgt daraus, dass, wenn die Anzahl der gefüllten Zellen 12 erreicht, die Die Anzahl der Zellen erhöht sich automatisch. Ladefaktor und Anfangskapazität sind die beiden Hauptfaktoren, die die Leistung von beeinflussen HashSet. Ein Lastfaktor von 0,75 sorgt im Durchschnitt für eine gute Leistung. Wenn dieser Parameter erhöht wird, wird die Speicherlast reduziert (da dadurch die Anzahl der erneuten Hashes und Neuerstellungen verringert wird), es wirkt sich jedoch auf Anhänge- und Suchvorgänge aus. Um den Zeitaufwand für das erneute Hashing zu minimieren, müssen Sie den richtigen anfänglichen Kapazitätsparameter auswählen. Wenn die Anfangskapazität größer ist als die maximale Anzahl von Elementen dividiert durch den Lastfaktor, findet überhaupt kein Re-Hashing-Vorgang statt. Wichtig: HashSetist keine Datenstruktur mit integrierter Synchronisierung. Wenn also mehrere Threads gleichzeitig daran arbeiten und mindestens einer von ihnen versucht, Änderungen vorzunehmen, muss ein synchronisierter Zugriff von außen bereitgestellt werden. Dies erfolgt häufig auf Kosten eines anderen synchronisierten Objekts, das die kapselt HashSet. Wenn es kein solches Objekt gibt, dann wird die Collections.synchronizedSet(). Dies ist derzeit die beste Möglichkeit, nicht synchronisierte Vorgänge mit zu verhindern HashSet.

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

HashSet-Konstruktoren:

1. HashSet h = new HashSet(); - Standardkonstruktor. Die standardmäßige Anfangskapazität beträgt 16, der Lastfaktor beträgt 0,75.
2. HashSet h = new HashSet(int initialCapacity)– ein Konstruktor mit einer gegebenen Anfangskapazität. Belastungsfaktor – 0,75.
3. HashSet h = new HashSet(int initialCapacity, float loadFactor);– ein Konstrukteur mit einer gegebenen Anfangskapazität und einem gegebenen Auslastungsfaktor.
4. HashSet h = new HashSet(Collection C)– ein Konstruktor, der Elemente aus einer anderen Sammlung hinzufügt.

Der folgende Code demonstriert einige Methoden HashSet:

import java.util.*;

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

        // Mit der Methode add() Elemente zum HashSet hinzufügen
        h.add("India");
        h.add("Australia");
        h.add("South Africa");
        h.add("India");// Versuchen Sie, ein weiteres gleiches Element hinzuzufügen

        // Die Elemente des HashSets auf der Konsole ausgeben
        System.out.println(h);
        System.out.println("List contains India or not:" +
                           h.contains("India"));

        // Elemente mit der Methode „remove()“ aus der Menge entfernen
        h.remove("Australia");
        System.out.println("List after removing Australia:"+h);

        // Durchlaufen Sie die Elemente des HashSet mithilfe eines Iterators:
        System.out.println("Iterating over list:");
        Iterator<String> i = h.iterator();
        while (i.hasNext())
            System.out.println(i.next());
    }
}

Abschluss:

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

Alle Klassen, die eine Schnittstelle implementieren, Setwerden intern durch Implementierungen unterstützt Map. HashSetspeichert Elemente mit HashMap. Obwohl HashMapein Element als Schlüssel-Wert-Paar dargestellt werden muss, um ein Element hinzuzufügen, HashSetwird nur der Wert hinzugefügt. Tatsächlich ist der Wert, an den wir übergeben, HashSetder Schlüssel zum Objekt HashMap, und als Wert wird eine Konstante verwendet HashMap. Auf diese Weise haben in jedem Schlüssel-Wert-Paar alle Schlüssel den gleichen Wert. Umsetzung HashSetin java doc:

private transient HashMap map;

// Konstruktor - 1
// Alle Konstruktoren erstellen implizit ein HashMap-Objekt.
public HashSet()
{
    // Erstelle ein implizites HashMap-Objekt
    map = new HashMap();
}

// Konstruktor- 2
public HashSet(int initialCapacity)
{
    // Erstelle ein implizites HashMap-Objekt
    map = new HashMap(initialCapacity);
}

// Ein Objekt der Object-Klasse, das jedes Mal als Wert in der HashMap fungiert
private static final Object PRESENT = new Object();

add()Wenn Sie sich die Methode y ansehen HashSet:

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

Sie können feststellen, dass die Methode add()y die Methode für das interne Objekt HashSetaufruft und ihm das hinzuzufügende Element als Schlüssel und die PRESENT-Konstante als Wert übergibt. Die Methode funktioniert auf ähnliche Weise . Es ruft die interne Objektmethode auf : put()HashMapremove()remove()HashMap

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

HashSetbasiert auf einer Hash-Tabelle und Add-, Lösch- oder Suchvorgänge werden im Durchschnitt in konstanter (O(1))-Zeit abgeschlossen . Methoden HashSet:

1. boolean add(E e): Fügt ein Element hinzu HashSet, wenn keins vorhanden ist, aber wenn ein solches Element bereits vorhanden ist, gibt die Methode false zurück .
2. void clear():Entfernt alle Elemente aus einer Menge.
3. boolean contains(Object o): Gibt true zurück , wenn das angegebene Element in der Menge vorhanden ist.
4. boolean remove(Object o): Entfernt das angegebene Element aus der Menge, falls vorhanden.
5. Iterator iterator(): Gibt einen Iterator für die Elemente der Menge zurück.
6. boolean isEmpty(): Gibt true zurück , wenn die Menge keine Elemente enthält.
7. Object clone(): Führt das Klonen der Oberfläche durch HashSet.

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