Java에서 주문 세트를 구현한 적이 있습니까?

Java에서 주문 세트를 구현한 적이 있습니까?

Objective-C에 대해 잘 아는 사람이 있다면 Set으로 동작하는 컬렉션이 있으며, 이 컬렉션은 Array의 아이템으로 액세스할 수 있습니다.

자바에도 이런 게 있나요?

라는 컬렉션이 있다고 들었습니다만, 세트로 된 것은 없었습니다.

Linked Hash Set 클래스 보기

Java 문서:

예측 가능한 반복 순서를 가진 Set 인터페이스의 해시 테이블 및 링크 목록 구현.이 실장은 HashSet과 달리 모든 엔트리에서 실행 중인 이중 링크목록을 유지합니다.이 링크 리스트는 반복 순서를 정의합니다.이것은 요소가 세트에 삽입된 순서(삽입 순서)입니다.요소를 세트에 다시 삽입해도 삽입 순서는 영향을 받지 않습니다(s.contains(e)가 호출되기 직전에 true를 반환할 때 s.add(e)가 호출되면 요소 e가 세트에 다시 삽입됩니다).

모든 세트에는 반복기()가 있습니다.일반 HashSet의 반복기는 매우 랜덤하고 TreeSet은 정렬 순서로 반복하며 LinkedHashSet 반복기는 삽입 순서로 반복됩니다.

그러나 LinkedHashSet에서는 요소를 교체할 수 없습니다.하나를 제거하고 다른 요소를 추가할 수 있지만 새 요소는 원래 요소 대신 없습니다.Linked Hash Map 에서는 기존 키의 값을 대체할 수 있으며 값은 원래 순서로 유지됩니다.

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

중복되지 않도록 하려면 Array List를 명시적인 체크와 함께 사용하는 것이 좋습니다.

Java 표준 API 문서를 참조하십시오.바로 옆에는 가 있습니다.단, 이들 순서는 삽입 순서이며 요소의 자연스러운 순서가 아닙니다.또한 이 순서로만 반복할 수 있으며 랜덤접근은 할 수 없습니다(반복 스텝을 카운트하는 경우는 제외).

와 에 의해 실장된 인터페이스도 있습니다.두 인터페이스 모두 요소 또는의 자연스러운 순서로 반복할 수 있지만 랜덤액세스나 삽입 순서는 사용할 수 없습니다.

인덱스별 효율적인 액세스와 설정 기준을 효율적으로 구현할 수 있는 데이터 구조에는 스킵 리스트가 필요하지만 Java Standard API에는 해당 기능이 구현되어 있지 않지만 인터넷에서 쉽게 찾을 수 있습니다.

TreeSet명령되어 있습니다.

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

그 도구를 사용해 보세요.

문서를 인용하려면:

"원소는 사용되는 컨스트럭터에 따라 자연스러운 순서를 사용하거나 설정 작성 시 제공된 비교기(Comparator)에 의해 정렬됩니다."

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

세트의 컨텐츠에 어레이로서 액세스 하려면 , 다음의 방법으로 변환할 수 있습니다.

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

이 어레이는 TreeSet과 같은 기준(자연 또는 비교기)으로 정렬됩니다.많은 경우 Arrays.sort()를 실행하는 대신 이점을 얻을 수 있습니다.

treeset은 순서가 매겨진 집합이지만 항목 인덱스를 통해 액세스할 수 없으며 반복하거나 시작/끝으로 이동할 수 없습니다.

저렴한 스킵 리스트의 실장이라고 하면, 빅 O의 관점에서 이 작업에 드는 비용은 얼마인지 궁금합니다.

YourType [ ]어레이 = someSet.toArray ( new YourType [ yourSet . size ( ) ） ;

즉, 항상 전체 어레이 생성에 고정되므로 O(n)가 됩니다.

java.util.Arrays#copyOf

Google Guava에서와 같은 양방향 지도에서 일부 유틸리티를 얻을 수도 있습니다.

를 사용하여BiMap(랜덤 인덱스액세스용) Integer를 다른 오브젝트유형에 매우 효율적으로 매핑할 수 있습니다. BiMap는 1 대 1이므로, 임의의 정수는 최대 1개의 요소를 관련지을 수 있으며, 임의의 요소는 1개의 정수를 관련지을 수 있습니다.그것은 두 가지에 의해 현명하게 뒷받침된다.HashTable즉, 거의 두 배의 메모리를 사용하지만 커스텀보다 훨씬 효율적입니다.List때문에 처리되는 데까지contains()(항목이 이미 존재하는지 확인하기 위해 추가되었을 때 호출됩니다)는 다음과 같은 상시적이고 병렬 친화적인 작업입니다.HashSet의,List의 실장은 매우 느립니다.

저도 비슷한 문제가 있었어요.주문 세트는 필요 없었지만 빠른 목록이 더 필요했습니다.indexOf/contains아무것도 찾지 못했기 때문에 직접 구현했습니다. 이 두 가지를 모두 합니다.Set ★★★★★★★★★★★★★★★★★」List, 모든 이 ''' 것은 ArrayList를 참조해당 버전.

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

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

인덱스 트리 맵프로젝트의 Indexed Tree Set은 이 기능을 제공합니다(인덱스별 목록과 같은 액세스로 정렬된 세트).

독자적인 MapTreeAVL(실장처:mtAvl interface package next that interface, package next that interface, next next next to to a 、 package a a a a a 、 a a a a a a a a a a 、 a a a a a a a a 、 a a a a a a a a aSortedSet액세스( 「」라고 불리는 것)를 가지는 .Optimizations를 들면, 「」와 같이MinMaxIndexIteration이 경우 선호될 수 있습니다.)

(주의: 제 레포는 열려 있기 때문에 원하는 파일을 직접 다운로드 할 수 있지만, 같은 슈퍼 패키지에 다른 클래스가 있는지 확인하는 것이 좋습니다.dataStructure★★★★★★★★★★★★★★★★★★★」

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