Esistono classi di raccolta non ordinate e ripetibili in Java?

Question

Desidero che una raccolta contenga elementi non ordinati e ripetibili. In Java, Set è irripetibile, List è ordinato, che non è quello che voglio.

Sembra che Pool sia una raccolta appropriata, ma non esiste in Java. L'interfaccia dovrebbe essere il seguente:

public interface Pool<T> { 
    void set(T item); 
    T get(); 
} 

Esiste da qualche parte?

---

A complemento:

realizzo che ho espresso il mio pensiero in modo errato. Infatti, voglio avere un'interfaccia come questa:

public interface Pool<T> { 
    void put(T item); 
    T randomRemove(); 
} 

Cioè, voglio ottenere un elemento ramdomly ogni volta. Come posso ottenerlo?

Answer 1

è possibile implementare la funzionalità Pool<T> avvolgendo un List<T>.

public class ListPool<T> implements Pool<T> { 
    private List<T> list = ArrayList<>(); 

    public void put(T t) { 
     list.append(t); 
    } 

    public T randomRemove() { 
     return list.remove(rand.nextInt(list.size())); 
    } 
} 

che non sarà particolarmente efficiente perché remove è O(N) sullo standard List implementazioni. Tuttavia, esiste un'implementazione alternativa che utilizza ArrayList un po 'più complicato, ma fornisce uno randomRemove ovvero O(1). L'idea è di trattare l'elenco come un array dinamico e gestire da solo la "dimensione".

Qualcosa di simile a questo:

public class FasterPool<T> implements Pool<T> { 
    private List<T> list = new ArrayList<>(); 
    private int size = 0; 
    Random rand = new Random(); 

    public void put(T t) { 
     if (size == list.size()) { 
      list.append(t); 
     } else { 
      list.set(size, t); 
     size++; 
    } 

    public T randomRemove() { 
     int pos = rand.nextInt(size); 
     T result = list.get(pos); 
     if (pos < size - 1) { 
      list.set(pos, list.get(size - 1)); 
     } 
     list.set(size - 1, null); // avoid memory leak ... 
     size--; 
     return result; 
    } 
} 

NB: nessuna delle due versioni gestisce il caso in cui la piscina è vuota quando si tenta di rimuovere un elemento. Nessuno dei due è stato compilato o testato. Si prega di trattare il codice di conseguenza.

Infine, se si tenta di implementare utilizzando un tipo di raccolta non ordinato, è improbabile che sia possibile rimuovere un elemento casuale in modo efficiente. Suggerimento: rimuovere il primo restituito dall'iteratore di una raccolta non sarà veramente casuale per qualsiasi pratica struttura di raccolta dati. Ciò si applicherebbe anche a un'implementazione (ipotetica) Bag.

Answer 2

Sembra che tu stia descrivendo Guava Multiset e in particolare HashMultiset.

Nessuna raccolta esiste in Java SE, sebbene sia possibile creare la propria abbastanza facilmente, a seconda della quantità di funzionalità desiderata. In pratica avresti un HashMap<T, Integer> o qualcosa del genere.

solo per esempio:

class MultiSet<T> { 
    Map<T, Integer> map = new HashMap<>(); 

    void add(T obj) { 
     Integer count = map.get(obj); 
     if (count == null) { 
      map.put(obj, 1); 
     } else { 
      map.put(obj, count + 1); 
     } 
    } 

    void remove(T obj) { 
     Integer count = map.get(obj); 
     if (count != null) { 
      if (count > 1) { 
       map.put(obj, count - 1); 
      } else { 
       map.remove(obj); 
      } 
     } 
    } 

    boolean contains(Object obj) { 
     return map.containsKey(obj); 
    } 
} 

Answer 3

Un approccio dovrebbe essere casuale raccogliere se avete bisogno di ordinamento casuale.

List<String> list = new ArrayList<String>(); 
list.add("A"); 
list.add("B"); 
list.add("C"); 
Collections.shuffle(list); 

System.out.println(list); 

uscita:

[B, A, C]