Cualquier implementación de conjunto ordenado en Java?

Question

Si alguien está familiarizado con Objective-C hay una colección llamada NSOrderedSet que actúa como Establecer y sus artículos se puede acceder como una matriz 's queridos.

¿Hay algo como esto en Java?

He oído que hay una colección llamada LinkedHashMap, pero no he encontrado nada igual para un conjunto.

Answer 1

Tome un vistazo a LinkedHashSet clase

Answer 2

treeset es un conjunto ordenado, pero no se puede acceder a través de un índice de elementos, simplemente iterar o ir al principio/final.

Answer 3

Cada conjunto tiene un iterador(). Un iterador de HashSet normal es bastante aleatorio, un TreeSet lo hace por orden de clasificación, un iterador LinkedHashSet itera por orden de inserción.

No se puede reemplazar un elemento en un LinkedHashSet, sin embargo. Puede eliminar uno y agregar otro, pero el nuevo elemento no estará en el lugar del original. En LinkedHashMap, puede reemplazar un valor para una clave existente y, a continuación, los valores seguirán en el orden original.

Además, no puede insertar en una posición determinada.

Quizás sea mejor que use una ArrayList con una comprobación explícita para evitar la inserción de duplicados.

Answer 4

TreeSet se ordena.

http://docs.oracle.com/javase/6/docs/api/java/util/TreeSet.html

Answer 5

Trate de usar java.util.TreeSet que implementa SortedSet.

citar el documento:

"Los elementos están clasificadas utilizando su orden natural, o por un comparador proporcionada en el momento de crear el tipo, dependiendo de lo que se utiliza el constructor"

Tenga en cuenta que add, remove y contains tiene un registro de costo de tiempo (n).

Si desea acceder al contenido de la forma de matriz, se puede convertir haciendo:

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

Esta matriz se clasificará con los mismos criterios que el TreeSet (naturales o por un comparador) , y en muchos casos esto tendrá una ventaja en lugar de hacer un Arrays.sort()

Answer 6

Eche un vistazo a Java standard API doc. Justo al lado de LinkedHashMap, hay un LinkedHashSet. Pero tenga en cuenta que el orden en esos es el orden de inserción, no el orden natural de los elementos. Y solo puede iterar en ese orden, no hacer acceso aleatorio (excepto contando los pasos de iteración).

También hay una interfaz SortedSet implementada por TreeSet y ConcurrentSkipListSet. Ambos permiten la iteración en el natural order de sus elementos o un Comparator, pero no el acceso aleatorio o el orden de inserción.

Para una estructura de datos que tiene tanto un acceso eficiente por el índice y se puede aplicar eficazmente el criterio establecido, se necesitaría una skip list, pero no hay ninguna aplicación con la que la funcionalidad de la API estándar de Java, aunque estoy seguro de que es fácil de encontrar uno en internet.

Answer 7

Si estamos hablando de la aplicación económica de la lista de salto, me pregunto en términos de gran O, lo que el coste de esta operación es:

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

quiero decir que siempre se quede atascado en toda una creación de la matriz, por lo que es O (n):

java.util.Arrays#copyOf 

Answer 8

IndexedTreeSet del proyecto indexed-tree-map proporciona esta funcionalidad (ordenados/ordenan en conjunto con la lista- como acceso por índice).

Answer 9

También puede obtener alguna utilidad de un mapa bidireccional como el BiMap de Google Guava

Con un BiMap, puede asignar bastante eficiente un entero (índice para acceder al azar) a cualquier otro tipo de objeto. BiMap s son uno a uno, por lo que cualquier número entero dado tiene, a lo sumo, un elemento asociado con él, y cualquier elemento tiene un número entero asociado. Está inteligentemente respaldado por dos instancias HashTable, por lo que utiliza casi el doble de memoria, pero es mucho más eficiente que un List personalizado en cuanto al procesamiento porque (que se llama cuando se agrega un elemento para verificar si ya existe) es funcionamiento de tiempo constante y paralelo amigable como HashSet, mientras que la implementación de List es MUCHO más lenta.

Answer 10

Tuve un problema similar. No necesitaba un conjunto ordenado, pero más una lista con un rápido indexOf/contains. Como no encontré nada, implementé uno yo mismo. Aquí está el código, implementa Set y List, aunque no todas las operaciones de lista masiva son tan rápidas como las versiones ArrayList.

exención de responsabilidad: no probado

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 entries are 
* ignored as most other java Set's do. 
*/ 
public class IndexedArraySet<E> extends ArrayList<E> implements Set<E> { 

    public IndexedArraySet() { super(); } 

    public IndexedArraySet(Iterable<E> c) { 
     super(); 
     addAll(c); 
    } 

    private HashMap<E, Integer> 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<? extends E> c) { 
     return addAll((Iterable<? extends E>) c); 
    } 
    public boolean addAll(Iterable<? extends E> 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<? extends E> 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<? super E> filter) { 
     boolean rv; 
     try { rv = super.removeIf(filter); } 
     finally { reindex(); } 
     return rv; 
    } 

    @Override 
    public void replaceAll(final UnaryOperator<E> 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<? super E> c) { 
     try { super.sort(c); } 
     finally { reindex(); } 
    } 
}