해시셋과 트리셋

해시셋과 트리셋

난 항상 나무를 사랑했어, 그렇게 좋아.O(n*log(n))깔끔하게 정리되어 있습니다.하지만 제가 아는 모든 소프트웨어 엔지니어가 왜 이 소프트웨어를 사용하는지 지적하며 물어봅니다.TreeSetCS의 배경에서 보면, 어느 것을 사용하는지는 그다지 중요하지 않다고 생각합니다만, 해시함수나 버킷을 가지고 장난치는 것은 별로 신경 쓰지 않습니다.Java).

어떤 경우에 I'm을 사용해야 합니까?HashSet에 걸쳐서TreeSet?

HashSet은 TreeSet보다 훨씬 빠르지만(추가, 삭제, 포함 등 대부분의 작업에 대해 고정 시간과 로그 시간을 비교) TreeSet과 같은 순서 보증을 제공하지 않습니다.

해시 세트

• 클래스는 기본 작업(추가, 제거, 포함 및 크기)에 대해 일정한 시간 성능을 제공합니다.
• 시간이 지남에 따라 요소의 순서가 일정하게 유지된다는 보장은 없습니다.
• 반복 성능은 HashSet의 초기 용량과 부하율에 따라 달라집니다.
  • 기본 부하 계수를 사용하는 것이 안전하지만 초기 용량은 세트가 증가할 것으로 예상하는 크기의 약 2배로 지정할 수 있습니다.

트리 세트

• 기본 조작(추가, 삭제 및 포함)의 로그(n) 시간 비용을 보증합니다.
• 는 세트의 요소가 정렬되는 것을 보증합니다(표준, 자연 또는 컨스트럭터를 통해 사용자가 지정한 것). (실장)
• 반복 성능에 대한 조정 매개 변수를 제공하지 않음
• 에는 다음과 같은 주문 세트를 처리하는 편리한 방법이 몇 가지 있습니다.last(), , 등

주의사항:

• 둘 다 요소의 중복 없는 수집을 보장합니다.
• 일반적으로 HashSet에 요소를 추가한 후 중복 없이 정렬된 트래버설을 위해 컬렉션을 TreeSet으로 변환하는 것이 더 빠릅니다.
• 이러한 실장은 모두 동기화되지 않습니다.즉, 여러 스레드가 한 세트에 동시에 액세스하고 스레드 중 하나 이상이 세트를 수정하는 경우 외부에서 동기화해야 합니다.
• LinkedHashSet은 어떤 의미에서는HashSet그리고.TreeSet그러나 링크 리스트가 실행 중인 해시 테이블로 구현되어 TreeSet에 의해 보증된 정렬된 트래버설과는 다른 삽입 순서 반복을 제공합니다.

따라서 사용 방법은 전적으로 고객의 요구에 따라 다르지만, 주문한 컬렉션이 필요한 경우에도 HashSet을 생성하여 TreeSet으로 변환하는 것이 좋다고 생각합니다.

• 예.SortedSet<String> s = new TreeSet<String>(hashSet);

아직 언급되지 않은 장점 중 하나는TreeSet두 개의 엔트리가 순서대로 근처에 있는 경우 (1)을 나타내는 줄임말인 "더 큰"을 갖는다는 것입니다.TreeSet는 데이터 구조상 서로 근접하게 배치하므로 메모리 내에 배치됩니다.또, 이 배치에서는, 같은 빈도를 가지는 애플리케이션에 의해서, 같은 데이터에 액세스 하는 경우가 많은 것을 나타내는 로컬의 원리를 이용하고 있습니다.

이것은 A와 대조적이다.HashSet키가 무엇이든 간에 메모리 전체에 엔트리가 분산됩니다.

하드 드라이브에서 읽기 지연 시간이 캐시 또는 RAM에서 읽기 비용의 수천 배에 달하고 로컬에서 데이터에 액세스할 때TreeSet훨씬 더 나은 선택이 될 수 있어요

HashSet요소에 액세스하기 위한 O(1)이기 때문에 확실히 문제가 됩니다.그러나 세트 내 객체의 순서를 유지하는 것은 불가능합니다.

TreeSet순서 유지(삽입 순서가 아닌 값)가 중요한 경우 도움이 됩니다.그러나 이미 설명한 바와 같이 기본 조작의 경우 O(log n) 요소에 액세스하는 데 걸리는 시간이 느리기 때문에 주문을 교환하고 있습니다.

의 javadocs:

이 실장에서는, 기본적인 조작에 대해서, 로그(n)의 시간 코스트가 보증됩니다.add,remove그리고.contains).

여기에서는 @shevchyk의 지도상의 아름다운 시각적 답변을 바탕으로 제 의견을 제시하겠습니다.

╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
║   Property   ║       HashSet       ║      TreeSet      ║     LinkedHashSet   ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║  no guarantee order ║ sorted according  ║                     ║
║   Order      ║ will remain constant║ to the natural    ║    insertion-order  ║
║              ║      over time      ║    ordering       ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║ Add/remove   ║        O(1)         ║     O(log(n))     ║        O(1)         ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║   NavigableSet    ║                     ║
║  Interfaces  ║         Set         ║       Set         ║         Set         ║
║              ║                     ║    SortedSet      ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║    not allowed    ║                     ║
║  Null values ║       allowed       ║ 1st element only  ║      allowed        ║
║              ║                     ║     in Java 7     ║                     ║
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
║              ║   Fail-fast behavior of an iterator cannot be guaranteed      ║
║   Fail-fast  ║ impossible to make any hard guarantees in the presence of     ║
║   behavior   ║           unsynchronized concurrent modification              ║
╠══════════════╬═══════════════════════════════════════════════════════════════╣
║      Is      ║                                                               ║
║ synchronized ║              implementation is not synchronized               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝

1. HashSet에서는 늘오브젝트를 허용합니다.

2. TreeSet에서 null 객체를 허용하지 않습니다.null 값을 추가하려고 하면 Null Pointer가 느려집니다.예외.

3. HashSet은 TreeSet보다 훨씬 빠릅니다.

예.

 TreeSet<String> ts = new TreeSet<String>();
 ts.add(null); // throws NullPointerException

 HashSet<String> hs = new HashSet<String>();
 hs.add(null); // runs fine

가장 많이 사용하는 이유HashSet동작은 O(log n)가 아닌 O(1)입니다.세트에 표준 아이템이 포함되어 있는 경우, 지금까지와 같이 「해시 함수와의 조작」은 행해지지 않습니다.세트에 커스텀 클래스가 포함되어 있는 경우,hashCode사용하다HashSet(유효한 Java는 방법을 나타내지만)TreeSet꼭 해내야 해Comparable또는 a를 공급합니다.Comparator클래스에 특정 순서가 없는 경우 문제가 될 수 있습니다.

나는 가끔 사용해 왔다.TreeSet(또는 실제로TreeMap매우 작은 세트/맵(< 10 아이템)의 경우, 실제로 얻을 수 있는 것이 있는지 어떤지는 확인하지 않았습니다.큰 세트의 경우 큰 차이가 날 수 있습니다.

정리된 게 필요하면TreeSet업데이트가 빈번하고 정렬된 결과의 필요성이 적은 경우에도 콘텐츠를 목록이나 배열에 복사하여 정렬하는 것이 더 빠를 수 있습니다.

빈번한 재해시(또는 HashSet이 크기를 조정할 수 없는 경우 충돌)를 일으킬 만큼 충분한 요소를 삽입하지 않는 경우 HashSet은 일정한 시간 액세스의 이점을 제공합니다.다만, 증감량이 많은 세트에서는, 실장에 따라서는, 실제로 Treeset 를 사용해 퍼포먼스가 향상하는 경우가 있습니다.

상각된 시간은 O(1)에 가까울 수 있으며, 기능하는 레드-블랙 트리가 있습니다(메모리에 문제가 없는 경우입니다.오카사키의 책은 내가 할 수 있는 것보다 더 좋은 설명이 될 것이다.(혹은 그의 출판물 목록을 참조해 주세요.)

물론 HashSet 구현이 훨씬 빠릅니다. 순서가 없기 때문에 오버헤드가 줄어듭니다.Java의 다양한 Set 구현에 대한 적절한 분석은 http://java.sun.com/docs/books/tutorial/collections/implementations/set.html에서 제공됩니다.

또한 Tree vs Hash 질문에 대한 흥미로운 '중도' 접근법에 대해서도 설명합니다.Java는 LinkedHashSet을 제공합니다.HashSet은 "삽입 지향" 링크 리스트가 실행되는 해시 세트입니다.즉, 링크 리스트의 마지막 요소도 해시에 가장 최근에 삽입된 것입니다.이를 통해 TreeSet의 비용이 증가하지 않고 순서가 매겨지지 않은 해시의 불안정성을 방지할 수 있습니다.

TreeSet은 2개의 정렬된 컬렉션(다른 하나는 TreeMap) 중 하나입니다.레드-블랙 트리 구조(단, 알고 계셨지만)를 사용하여 요소가 자연 순서에 따라 오름차순으로 정렬됩니다.선택적으로 Comparible 또는 Comparator를 사용하여 순서 지정에 대한 고유한 규칙을 컬렉션에 지정할 수 있는 생성자를 사용하여 TreeSet을 구성할 수 있습니다.

LinkedHashSet은 모든 요소에 걸쳐 이중 링크된 목록을 유지하는 HashSet의 순서 버전입니다.반복 순서를 신경 쓸 때는 HashSet 대신 이 클래스를 사용합니다.HashSet에서 반복할 경우 순서를 예측할 수 없지만 LinkedHashSet에서는 요소가 삽입된 순서대로 반복할 수 있습니다.

오렌지를 먹을 수 있는데 왜 사과를 먹을까요?

진지하게 고민하고 있는 여러분 - 방대한 양의 컬렉션을 읽고 쓰고 CPU 사이클에 대한 비용을 지불해야 한다면 컬렉션을 선택하는 것은 퍼포먼스를 향상시키기 위해 필요한 경우에만 의미가 있습니다.하지만, 대부분의 경우, 이것은 별로 중요하지 않습니다. 몇 밀리초 동안 인간의 관점에서 눈에 띄지 않습니다.그게 그렇게 중요했다면 왜 어셈블리러나 C에 코드를 쓰지 않는 거죠?[또 다른 토론에 끼어들기]요점은 어떤 컬렉션을 사용하든 만족할 수 있고, (작업에 가장 적합한 컬렉션이 아니더라도) 문제가 해결된다는 것입니다.소프트웨어는 유연성이 있습니다.필요한 경우 코드를 최적화합니다.밥 삼촌은 조기 최적화가 모든 악의 근원이라고 말한다.밥 아저씨가 그러셔

심지어 11년이 지났는데도, 아무도 매우 중요한 차이를 언급할 생각을 하지 못했다.

만약에HashSet동등.TreeSet그럼 그 반대도 사실인가요?이 코드를 봐 주세요.

TreeSet<String> treeSet = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
HashSet<String> hashSet = new HashSet<>();
treeSet.add("a");
hashSet.add("A");
System.out.println(hashSet.equals(treeSet));
System.out.println(treeSet.equals(hashSet));

출력을 추측하고 스니펫 아래로 이동하여 실제 출력을 확인합니다.준비됐어요? 여기 있어요.

거짓의
진실의

그렇습니다. 동등하지 않은 대조군에 대한 동등성 관계는 없습니다.그 이유는...TreeSet비교기를 사용하여 동등성을 판별합니다.HashSet사용하다equals내부적으로는HashMap그리고.TreeMap그래서 당신은 언급한 것과 함께 이러한 행동을 예상해야 합니다.Map에서도 마찬가지입니다.

당초의 회답

Message Edit (완전 리라이트)순서가 중요하지 않은 경우는 그 시점입니다.둘 다 Log(n)를 부여해야 합니다.둘 중 하나가 다른 쪽보다 5% 이상 빠른지 확인하는 것이 유용합니다.HashSet은 루프에서 O(1) 테스트를 제공할 수 있습니다.이 테스트에 의해 O(1)가 유효한지 여부가 밝혀집니다.

기술적인 고려 사항, 특히 성능에 대한 많은 답변이 제시되었습니다.제 말에 따르면,TreeSet그리고.HashSet문제가 있습니다.

그러나 나는 차라리 선택은 개념적인 고려에 의해 결정되어야 한다고 말하고 싶다.

조작해야 할 객체에 대해 자연스러운 순서가 적절하지 않은 경우 를 사용하지 마십시오.TreeSet.
이것은 분류된 세트이다. 왜냐하면 그것은 실장되어 있기 때문입니다.SortedSet즉, 기능을 무효로 할 필요가 있습니다.compareTo반환 함수와 일치해야 합니다.equals예를 들어, Student라고 하는 클래스의 오브젝트 세트가 있다면, 나는 그것이 가능하다고 생각하지 않는다.TreeSet학생들 사이에 자연스러운 질서가 없기 때문에 말이 됩니다.평균 등급으로 주문할 수 있지만, 이것은 "자연적인 순서"가 아닙니다.기능.compareTo는, 2개의 오브젝트가 같은 학생을 나타내고 있을 뿐만 아니라, 2개의 다른 학생이 같은 성적을 받고 있는 경우에도 0을 반환합니다.두 번째 케이스는equalsfalse를 반환한다(다른 두 학생이 같은 성적을 받았을 때 후자를 true로 반환하기로 결정하지 않는 한).equals함수는 잘못된 의미를 가지며, 잘못된 의미를 말하지 않습니다.)
이 일관성에 주의해 주십시오.equals그리고.compareTo는 옵션이지만 강력히 권장합니다.그렇지 않으면 인터페이스 계약Set코드가 깨져서 다른 사람에게 오해를 불러일으키고 예기치 않은 동작으로 이어질 수 있습니다.

이 링크는 이 질문에 대한 유용한 정보원이 될 수 있습니다.

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class HashTreeSetCompare {

    //It is generally faster to add elements to the HashSet and then
    //convert the collection to a TreeSet for a duplicate-free sorted
    //Traversal.

    //really? 
    O(Hash + tree set) > O(tree set) ??
    Really???? Why?



    public static void main(String args[]) {

        int size = 80000;
        useHashThenTreeSet(size);
        useTreeSetOnly(size);

    }

    private static void useTreeSetOnly(int size) {

        System.out.println("useTreeSetOnly: ");
        long start = System.currentTimeMillis();
        Set<String> sortedSet = new TreeSet<String>();

        for (int i = 0; i < size; i++) {
            sortedSet.add(i + "");
        }

        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useTreeSetOnly: " + (end - start));
    }

    private static void useHashThenTreeSet(int size) {

        System.out.println("useHashThenTreeSet: ");
        long start = System.currentTimeMillis();
        Set<String> set = new HashSet<String>();

        for (int i = 0; i < size; i++) {
            set.add(i + "");
        }

        Set<String> sortedSet = new TreeSet<String>(set);
        //System.out.println(sortedSet);
        long end = System.currentTimeMillis();

        System.out.println("useHashThenTreeSet: " + (end - start));
    }
}

언급URL : https://stackoverflow.com/questions/1463284/hashset-vs-treeset