Java에서 Ordered Set 구현이 있습니까?

Java에서 Ordered Set 구현이 있습니까?

---

Objective-C에 익숙한 사람이 있으면 SetNSOrderedSet 역할을 하는 컬렉션이 있으며 해당 항목은 Array 의 항목으로 액세스 할 수 있습니다 .

Java에 이와 같은 것이 있습니까?

라는 컬렉션이 있다고 들었지만 LinkedHashMap세트에 대해 이와 비슷한 것을 찾지 못했습니다.

---

LinkedHashSet 클래스 살펴보기

---

모든 Set에는 iterator ()가 있습니다. 일반적인 HashSet의 반복자는 매우 무작위 적이며 TreeSet은 정렬 순서로 수행하고 LinkedHashSet 반복자는 삽입 순서로 반복합니다.

그러나 LinkedHashSet의 요소를 바꿀 수는 없습니다. 하나를 제거하고 다른 요소를 추가 할 수 있지만 새 요소는 원본 위치에 있지 않습니다. LinkedHashMap에서 기존 키의 값을 바꿀 수 있으며 값은 원래 순서대로 유지됩니다.

또한 특정 위치에 삽입 할 수 없습니다.

중복 삽입을 피하기 위해 명시 적 검사와 함께 ArrayList를 사용하는 것이 좋습니다.

---

Java 표준 API 문서를 살펴보십시오 . 바로 옆에 LinkedHashMap하는있다 LinkedHashSet. 그러나 그 순서는 요소의 자연스러운 순서가 아니라 삽입 순서입니다. 그리고 무작위 액세스를 수행하지 않고 해당 순서로만 반복 할 수 있습니다 (반복 단계 계산 제외).

및에 SortedSet의해 구현 된 인터페이스도 있습니다 . 둘 다 요소 또는 a 의 자연스러운 순서 로 반복을 허용 하지만 임의 액세스 또는 삽입 순서는 허용하지 않습니다.TreeSetConcurrentSkipListSetComparator

인덱스로 효율적으로 액세스 할 수 있고 설정된 기준을 효율적으로 구현할 수있는 데이터 구조의 경우 건너 뛰기 목록이 필요 하지만 Java Standard API에는 해당 기능을 구현할 수 없지만 쉽게 찾을 수 있습니다. 인터넷에서.

---

TreeSet 주문됩니다.

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

---

java.util.TreeSet그 구현을 사용해보십시오 SortedSet.

문서를 인용하려면 :

"요소는 자연 순서를 사용하거나 사용되는 생성자에 따라 설정된 생성 시간에 제공된 비교기를 사용하여 정렬됩니다."

추가, 제거 및 포함에는 시간 비용 log (n)가 있습니다.

집합의 내용에 배열로 액세스하려면 다음을 수행하여 변환 할 수 있습니다.

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

이 배열은 TreeSet과 동일한 기준 (자연 또는 비교기)으로 정렬되며, 많은 경우 Arrays.sort ()를 수행하는 대신 이점이 있습니다.

---

treeset 은 정렬 된 집합이지만 항목 인덱스를 통해 액세스 할 수 없으며 반복하거나 시작 / 끝으로 이동합니다.

---

생략 목록의 저렴한 구현에 대해 이야기하고 있다면 빅 O의 관점에서이 작업의 비용이 얼마인지 궁금합니다.

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

내 말은 항상 전체 배열 생성에 갇혀 있으므로 O (n)입니다.

java.util.Arrays#copyOf

---

indexed-tree-map 프로젝트 의 IndexedTreeSet 은이 기능을 제공합니다 (색인 별 목록과 유사한 액세스로 정렬 / 정렬 된 집합).

---

또한 같은 양방향지도의 일부 유틸리티 아웃 얻을 수 있습니다 BiMap에서 구글 구아바

를 사용하면 BiMapInteger (임의 인덱스 액세스 용)를 다른 객체 유형에 매우 효율적으로 매핑 할 수 있습니다. BiMaps는 일대일이므로 주어진 정수에는 최대 하나의 요소가 연결되고 모든 요소에는 하나의 연결된 정수가 있습니다. 두 개의 HashTable인스턴스에 의해 영리하게 뒷받침 되므로 거의 두 배의 메모리를 사용하지만 List처리 하는 한 커스텀보다 훨씬 효율적입니다. contains()(이미 존재하는지 확인하기 위해 항목이 추가 될 때 호출 됨)이 일정 시간이기 때문입니다. 평행 쉬운 작업처럼 HashSet의 반면 List의 구현이 훨씬 느리다.

---

비슷한 문제가있었습니다. 나는 주문한 세트가 필요하지 않았지만 빠른 indexOf/ contains. 거기에서 아무것도 찾지 못했기 때문에 직접 구현했습니다. 다음은 코드입니다. 모든 대량 목록 작업이 버전 만큼 빠르지는 않지만 Set및을 모두 구현합니다 .ListArrayList

면책 조항 : 테스트되지 않음

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

참고 URL : https://stackoverflow.com/questions/8712469/any-implementation-of-ordered-set-in-java