Czy są jakieś nieuporządkowane, powtarzalne klasy kolekcji w Javie?

Question

Chcę, aby kolekcja zawierała nieuporządkowane, powtarzalne przedmioty. W języku Java zestaw jest niepowtarzalny, lista jest uporządkowana, a nie jest tym, czego chcę.

Wygląda na to, że Pool jest odpowiednią kolekcją, ale nie istnieje w Javie. Interfejs powinien być następujący:

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

Czy istnieje gdzieś?

---

Uzupełniając:

Zdaję sobie sprawę, że wyraziłem myśl nieprawidłowo. Rzeczywiście, chcę mieć interfejs podobny do tego:

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

To znaczy, chcę za każdym razem zdobyć coś niepoprawnie. Jak mogę to osiągnąć?

Answer 1

można zaimplementować funkcjonalność Pool<T> przez owinięcie 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())); 
    } 
} 

To nie będzie szczególnie efektywne, ponieważ remove jest O(N) na standardowych List wdrożeń. Istnieje jednak alternatywna implementacja z użyciem ArrayList, która jest nieco bardziej skomplikowana, ale zapewnia randomRemove, czyli O(1). Chodzi o to, aby traktować tę listę jako dynamiczną tablicę i zarządzać samym "rozmiarem".

coś takiego:

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: ani wersja obsługuje przypadek, gdy basen jest pusty podczas próby usunięcia elementu. Żadna z nich nie została skompilowana ani przetestowana. Proszę traktować kod odpowiednio.

Wreszcie, jeśli spróbujesz zaimplementować przy użyciu typu kolekcji, który nie jest uporządkowany, prawdopodobnie nie będziesz w stanie skutecznie usunąć elementu losowego. Podpowiedź: usunięcie pierwszego zwróconego przez iterator kolekcji nie będzie prawdziwie losowe dla żadnej praktycznej struktury danych kolekcji. Miałoby to również zastosowanie do (hipotetycznej) implementacji Bag.

Answer 2

Wygląda na to, że opisujesz Guava Multiset, a dokładniej: HashMultiset.

Brak takiej kolekcji w Java SE, chociaż można łatwo zbudować własną, w zależności od potrzebnej funkcjonalności. Zasadniczo masz HashMap<T, Integer> lub coś w tym stylu.

Wystarczy na przykład:

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

Jedno podejście powinno być collect shuffle, jeśli potrzebujesz losową kolejność.

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

System.out.println(list); 

wyjściowa:

[B, A, C]