Struttura dati Java con aggiunta, eliminazione e random efficienti

Question

Ho bisogno di una struttura dati Java che possa aggiungere, eliminare e accedere in modo efficiente a un oggetto casuale.

Questo è ciò che non funziona:

ArrayList ha efficiente add (costante di tempo), e ad accesso casuale (solo "ottenere" con un numero intero casuale), ma elimina può richiedere tempo lineare, perché deve potenzialmente cerca l'intero elenco per questo.

TreeSet o HashSet ha un'aggiunta ed eliminazione efficiente, ma non riesco a capire come ottenere un oggetto casuale.

Qualche idea?

In teoria, un Albero B funzionerebbe, se potessi attraversare l'albero io stesso con Sinistra o Diritti casuali, ma non penso che una classe Java standard mi dia questa abilità.

Sono disposto ad utilizzare una libreria di terze parti se nulla nelle classi Java standard funzionerà.

Non è necessario supportare duplicati o null, né è necessario essere thread-safe.

Grazie.

Answer 1

È possibile ottenere questo con una coppia ArrayList/HashMap (in cui la mappa memorizzerà l'indice degli oggetti nell'elenco) se si effettua la rimozione degli elenchi non ordinati. Alla rimozione, invece di spostare tutti gli elementi successivi nell'elenco in basso di una posizione, basta spostare l'ultimo elemento per riempire lo spazio dell'elemento rimosso. Poi ci sono al massimo due diversi elementi che devono essere toccati durante la rimozione. Un esempio veloce (che non ho ancora testato e la speranza non ho bungle):

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(); 
    } 
} 

A seconda di quale oggetto comportamento test di uguaglianza si desidera, è forse potrebbe scambiare la HashMap per un IdentityHashMap per un po 'meglio velocità.

Answer 2

Suggerirei di utilizzare una mappa, con un tasto intero. In questo modo puoi generare un numero casuale per la rimozione.

Problema lasciato al lettore: nelle operazioni di rimozione successive (o qualsiasi operazione) ci saranno degli spazi vuoti.

Answer 3

Si noti che un semplice array farà il lavoro, se si pre-allocare alla dimensione massima di cui avrete bisogno. Mantieni un valore di indice "top" e inserisci incrementando "top" e memorizzandolo in quell'elemento dell'array. Quando elimini, copia il valore "in alto" nell'elemento eliminato e decrementa "in alto".

Se non si conosce la dimensione massima è ancora possibile allocare una matrice di matrici e utilizzare lo stesso algoritmo di base, solo è necessario calcolare prima i valori dell'indice di array maggiore e minore prima di accedere a un elemento.