Java-Datenstruktur, die effizient hinzufügen, löschen und zufällig

Question

Ich brauche eine Java-Datenstruktur, die ich effizient hinzufügen, löschen und auf ein zufälliges Objekt zugreifen kann.

Dies ist, was nicht funktioniert:

Arraylist effiziente add (konstante Zeit) und Random Access (nur „get“ mit einer Zufallszahl), aber Löschungen lineare Zeit in Anspruch nehmen können, weil es möglicherweise muss Suche die ganze Liste danach.

TreeSet oder HashSet hat effiziente hinzufügen und löschen, aber ich kann nicht herausfinden, wie man ein zufälliges Objekt erhalten.

Irgendwelche Ideen?

In der Theorie würde ein B-Baum funktionieren, wenn ich den Baum selbst mit zufälligen Lefts oder Rechten durchqueren könnte, aber ich glaube nicht, dass eine Standard-Java-Klasse mir diese Fähigkeit gibt.

Ich bin bereit, eine Drittanbieter-Bibliothek zu verwenden, wenn nichts in den Standard-Java-Klassen funktionieren wird.

Ich brauche weder Duplikate oder Nullen, noch muss es threadsicher sein.

Danke.

Answer 1

Sie können dies mit einem ArrayList/HashMap-Paar erhalten (wobei die Karte den Index der Objekte in der Liste speichert), wenn Sie die Listenentfernung ungeordnet vornehmen. Beim Entfernen verschieben Sie nicht alle nachfolgenden Elemente in der Liste um eine Position nach unten, sondern verschieben einfach das letzte Element, um das Feld des entfernten Elements zu füllen. Dann gibt es höchstens zwei verschiedene Elemente, die beim Entfernen berührt werden müssen. Ein kurzes Beispiel (die ich nicht getestet haben, und hoffe, dass ich bungle nicht):

class SpecialSet<E> extends AbstractSet<E> implements Set<E> { 
    private final List<E> list = new ArrayList<>(); 
    private final Map<E,Integer> indexMap = new HashMap<>(); 

    @Override 
    public boolean add(E e) { 
     if (contains(e)) return false; 
     indexMap.put(e, list.size()); 
     list.add(e); 
     return true; 
    } 

    @Override 
    public boolean remove(Object o) { 
     Integer indexBoxed = indexMap.remove(o); 
     if (indexBoxed == null) return false; 
     int index = indexBoxed; 
     int last = list.size() - 1; 
     E element = list.remove(last); 
     if (index != last) { 
      indexMap.put(element, index); 
      list.set(index, element); 
     } 
     return true; 
    } 

    public E removeRandom() { 
     E element = list.get((int)(Math.random() * size())); 
     remove(element); 
     return element; 
    } 

    @Override 
    public boolean contains(Object o) { 
     return indexMap.containsKey(o); 
    } 

    @Override 
    public Iterator<E> iterator() { 
     return list.iterator(); 
    } 

    @Override 
    public int size() { 
     return list.size(); 
    } 
} 

Je nachdem, welche Objektgleichheit Testverhalten Sie möchten, könnten Sie vielleicht die HashMap für eine IdentityHashMap für ein wenig besser auslagern Geschwindigkeit.

Answer 2

Ich würde vorschlagen, dass Sie eine Karte mit einem Integer-Schlüssel verwenden. Auf diese Weise können Sie eine Zufallszahl für das Entfernen generieren.

Problem für den Leser übrig: bei nachfolgenden Entfernen (oder jeder Operation) wird es Lücken geben.

Answer 3

Beachten Sie, dass ein einfaches Array die Aufgabe erledigt, wenn Sie die maximale Größe vordefinieren, die Sie benötigen. Behalten Sie einen "oberen" Indexwert und fügen Sie ein, indem Sie "top" inkrementieren und in diesem Array-Element speichern. Wenn Sie löschen, kopieren Sie den Wert "top" in das gelöschte Element und dekrementieren Sie "top".

Wenn Sie Ihre maximale Größe nicht kennen, können Sie immer noch ein Array von Arrays zuweisen und denselben Basisalgorithmus verwenden. Sie müssen jedoch zuerst die Indexwerte des Haupt- und Nebenarrays berechnen, bevor Sie auf ein Element zugreifen.