Toute implémentation de Seted Set en Java?

Si quelqu’un est familier avec Objective-C, il existe une collection appelée NSOrderedSet qui agit en tant que Set et ses éléments sont accessibles en tant que ceux d’un tableau .

Y a-t-il quelque chose comme ça en Java?

J’ai entendu dire qu’il existe une collection appelée LinkedHashMap , mais je n’ai rien trouvé de tel pour un ensemble.

Jetez un oeil à la classe LinkedHashSet

Chaque ensemble a un iterator (). Un iterator normal de HashSet est assez aléatoire, un TreeSet le fait par ordre de sorting, un iterator LinkedHashSet itère par ordre d’insertion.

Vous ne pouvez toutefois pas remplacer un élément dans un LinkedHashSet. Vous pouvez en supprimer un et en append un autre, mais le nouvel élément ne sera pas à la place de l’original. Dans un LinkedHashMap, vous pouvez remplacer une valeur pour une clé existante, puis les valeurs seront toujours dans l’ordre d’origine.

En outre, vous ne pouvez pas insérer à une certaine position.

Vous devriez peut-être utiliser une ArrayList avec une vérification explicite pour éviter d’insérer des doublons.

Jetez un coup d’oeil à la doc API Java standard . Juste à côté de LinkedHashMap , il y a un LinkedHashSet . Mais notez que l’ordre dans ces derniers est l’ordre d’insertion, pas l’ordre naturel des éléments. Et vous ne pouvez qu’itérer dans cet ordre, ne pas faire d’access aléatoire (sauf en comptant les étapes d’itération).

Il existe également une interface SortedSet implémentée par TreeSet et ConcurrentSkipListSet . Les deux permettent une itération dans l’ ordre naturel de leurs éléments ou un Comparator , mais pas un access aléatoire ou un ordre d’insertion.

Pour une structure de données qui dispose à la fois d’un access efficace par index et peut implémenter efficacement le critère défini, vous avez besoin d’une liste de sauts , mais aucune implémentation n’est disponible avec l’API Java Standard. sur Internet.

Essayez d’utiliser java.util.TreeSet qui implémente SortedSet .

Pour citer le doc:

“Les éléments sont classés selon leur ordre naturel ou par un comparateur fourni au moment de la création de l’ensemble, en fonction du constructeur utilisé”

Notez que append, supprimer et contient a un journal des coûts en temps (n).

Si vous souhaitez accéder au contenu de l’ensemble en tant que tableau, vous pouvez le convertir en procédant comme suit:

 YourType[] array = someSet.toArray(new YourType[yourSet.size()]); 

Ce tableau sera sortingé avec les mêmes critères que le TreeSet (naturel ou par un comparateur), et dans de nombreux cas, cela aura un avantage au lieu de faire un Arrays.sort ()

treeset est un ensemble ordonné, mais vous ne pouvez pas accéder via un index d’éléments, simplement parcourir ou aller au début / à la fin.

Si nous parlons de la mise en œuvre peu coûteuse de la liste de sauts, je me demande en termes de grand O, quel est le coût de cette opération:

YourType [] array = someSet.toArray (new YourType [yourSet.size ()]);

Je veux dire qu’il est toujours bloqué dans une création entière de tableau, donc c’est O (n):

 java.util.Arrays#copyOf 

IndexedTreeSet du projet indexed -tree-map fournit cette fonctionnalité (jeu ordonné / sortingé avec access de type liste par index).

Vous pouvez également obtenir une utilité à partir d’une carte bidirectionnelle comme le BiMap de Google Guava

Avec un BiMap , vous pouvez très bien faire correspondre un Integer (pour un access à un index aléatoire) à tout autre type d’object. BiMap s sont un-à-un, donc tout entier donné a au plus un élément qui lui est associé et tout élément a un entier associé. Il est intelligemment soutenu par deux instances de HashTable , il utilise donc presque le double de la mémoire, mais il est beaucoup plus efficace qu’une List personnalisée en ce qui concerne le traitement car contains() est appelé lorsqu’un élément est ajouté pour vérifier s’il existe déjà. est une opération à temps constant et parallèle comme HashSet , tandis que l’implémentation de List est LOT plus lente.

J’avais un problème similaire. Je n’ai pas vraiment eu besoin d’un ensemble ordonné, mais plutôt d’une liste avec un indexOf rapide / contains . Comme je n’ai rien trouvé là-bas, j’en ai installé un moi-même. Voici le code, il implémente à la fois Set et List , bien que toutes les opérations de liste de masse ne soient pas aussi rapides que les versions ArrayList .

avertissement: non testé

 import java.util.ArrayList; import java.util.HashMap; import java.util.Set; import java.util.Collection; import java.util.Comparator; import java.util.function.Predicate; import java.util.function.UnaryOperator; import static java.util.Objects.requireNonNull; /** * An ArrayList that keeps an index of its content so that contains()/indexOf() are fast. Duplicate ensortinges are * ignored as most other java Set's do. */ public class IndexedArraySet extends ArrayList implements Set { public IndexedArraySet() { super(); } public IndexedArraySet(Iterable c) { super(); addAll(c); } private HashMap indexMap = new HashMap<>(); private void reindex() { indexMap.clear(); int idx = 0; for (E item: this) { addToIndex(item, idx++); } } private E addToIndex(E e, int idx) { indexMap.putIfAbsent(requireNonNull(e), idx); return e; } @Override public boolean add(E e) { if(indexMap.putIfAbsent(requireNonNull(e), size()) != null) return false; super.add(e); return true; } @Override public boolean addAll(Collection c) { return addAll((Iterable) c); } public boolean addAll(Iterable c) { boolean rv = false; for (E item: c) { rv |= add(item); } return rv; } @Override public boolean contains(Object e) { return indexMap.containsKey(e); } @Override public int indexOf(Object e) { if (e == null) return -1; Integer i = indexMap.get(e); return (i == null) ? -1 : i; } @Override public int lastIndexOf(Object e) { return indexOf(e); } @Override @SuppressWarnings("unchecked") public Object clone() { IndexedArraySet clone = (IndexedArraySet) super.clone(); clone.indexMap = (HashMap) indexMap.clone(); return clone; } @Override public void add(int idx, E e) { if(indexMap.putIfAbsent(requireNonNull(e), -1) != null) return; super.add(idx, e); reindex(); } @Override public boolean remove(Object e) { boolean rv; try { rv = super.remove(e); } finally { reindex(); } return rv; } @Override public void clear() { super.clear(); indexMap.clear(); } @Override public boolean addAll(int idx, Collection c) { boolean rv; try { for(E item : c) { // check uniqueness addToIndex(item, -1); } rv = super.addAll(idx, c); } finally { reindex(); } return rv; } @Override public boolean removeAll(Collection c) { boolean rv; try { rv = super.removeAll(c); } finally { reindex(); } return rv; } @Override public boolean retainAll(Collection c) { boolean rv; try { rv = super.retainAll(c); } finally { reindex(); } return rv; } @Override public boolean removeIf(Predicate filter) { boolean rv; try { rv = super.removeIf(filter); } finally { reindex(); } return rv; } @Override public void replaceAll(final UnaryOperator operator) { indexMap.clear(); try { int duplicates = 0; for (int i = 0; i < size(); i++) { E newval = requireNonNull(operator.apply(this.get(i))); if(indexMap.putIfAbsent(newval, i-duplicates) == null) { super.set(i-duplicates, newval); } else { duplicates++; } } removeRange(size()-duplicates, size()); } catch (Exception ex) { // If there's an exception the indexMap will be inconsistent reindex(); throw ex; } } @Override public void sort(Comparator c) { try { super.sort(c); } finally { reindex(); } } }