[java] 해시 셋 vs 트리 셋

JAVA / 글쓴이

나는 항상 나무, 그 멋지고 O(n*log(n))단정함을 좋아 했습니다. 그러나 내가 아는 모든 소프트웨어 엔지니어는 내가 왜을 사용할지 물었다 TreeSet. CS 배경에서 나는 당신이 사용하는 모든 것이 중요하다고 생각하지 않으며 해시 함수와 버킷 ()의 경우 엉망이되지 않습니다 Java.

어떤 경우에 HashSet이상을 사용해야 TreeSet합니까?

답변

HashSet은 TreeSet보다 훨씬 빠르지 만 (추가, 제거 및 포함과 같은 대부분의 작업에서 상수 시간 대 로그 시간) TreeSet과 같은 순서 보장은 제공하지 않습니다.

해시 세트

  • 이 클래스는 기본 작업 (추가, 제거, 포함 및 크기)에 대해 일정한 시간 성능을 제공합니다.
  • 요소의 순서가 시간이 지남에 따라 일정하게 유지된다고 보장하지는 않습니다.
  • 반복 성능은 초기 용량 과 HashSet 의 로드 팩터 에 따라 다릅니다 .
    • 기본로드 팩터를 수락하는 것이 안전하지만 세트가 커질 것으로 예상되는 크기의 약 두 배인 초기 용량을 지정할 수 있습니다.

TreeSet

  • 기본 작업에 대한 log (n) 시간 비용 보장 (추가, 제거 및 포함)
  • 집합의 요소가 오름차순, 자연적 또는 생성자를 통해 지정한 요소로 정렬되도록 보장합니다 (구현 SortedSet)
  • 반복 성능에 대한 튜닝 매개 변수를 제공하지 않습니다
  • 이벤트 몇 가지 편리한 방법은 같은 명령 세트를 처리하는 first(), last(), headSet(), 및 tailSet()등

중요한 점 :

  • 두 요소 모두 중복없는 요소 수집을 보장합니다.
  • 일반적으로 HashSet에 요소를 추가 한 다음 복제되지 않은 정렬 된 순회를 위해 컬렉션을 TreeSet으로 변환하는 것이 더 빠릅니다.
  • 이러한 구현 중 어느 것도 동기화되지 않습니다. 즉, 여러 스레드가 동시에 세트에 액세스하고 스레드 중 하나 이상이 세트를 수정하는 경우 외부에서 동기화되어야합니다.
  • LinkedHashSet의는 어떤 의미에서의 중간입니다 HashSet및 TreeSet. 그러나 연결된 목록을 통해 실행되는 해시 테이블로 구현되지만 TreeSet에 의해 보장 된 정렬 된 순회와 동일하지 않은 삽입 순서 반복을 제공합니다 .

따라서 사용법의 선택은 전적으로 귀하의 요구에 달려 있지만 정렬 된 컬렉션이 필요하더라도 여전히 HashSet을 선호하여 Set을 만든 다음 TreeSet으로 변환해야한다고 생각합니다.

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

답변

아직 언급되지 않은 한 가지 장점 TreeSet은 “지역성 (locality)”이 더 크다는 것인데, 이는 (1) 두 항목이 순서대로 근처에 있으면 TreeSet데이터 구조에서 서로 가까이 배치되어 메모리에 배치된다. 그리고 (2)이 배치는 지역성의 원칙을 이용하는데, 이는 유사한 데이터가 종종 유사한 주파수를 가진 응용 프로그램에 의해 액세스된다고 말합니다.

이것은 대조적으로 HashSet 키와 상관없이 메모리 전체에 항목을 분산시키는와 입니다.

하드 드라이브에서 읽는 대기 시간 비용이 캐시 나 RAM에서 읽는 시간의 수천 배인 경우, 데이터가 실제로 로컬로 액세스되는 TreeSet경우 훨씬 더 나은 선택이 될 수 있습니다.

답변

HashSet요소에 액세스하려면 O (1)이므로 확실히 중요합니다. 그러나 세트에서 객체의 순서를 유지하는 것은 불가능합니다.

TreeSet순서를 유지하는 것이 중요합니다 (삽입 순서가 아닌 값으로). 그러나 앞에서 언급했듯이 기본 작업의 경우 요소에 액세스하는 데 시간이 오래 걸리는 주문을 거래하고 있습니다.

에 대한 javadocs에서TreeSet :

이 구현은 기본 작업 ( add, remove및 contains)에 대해 보장 된 log (n) 시간 비용을 제공합니다 .

답변

1. HashSet은 null 객체를 허용합니다.

2. TreeSet은 null 객체를 허용하지 않습니다. null 값을 추가하려고하면 NullPointerException이 발생합니다.

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

답변

@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               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝

답변

가장 많이 사용하는 이유 HashSet는 연산이 O (log n) 대신 (평균) O (1)이기 때문입니다. 세트에 표준 항목이 포함되어 있으면 “해시 함수가없는 것”이 ​​아닙니다. 세트에 사용자 정의 클래스가 포함 된 경우, 유효 Java가 방법을 표시 하도록 구현 hashCode해야 HashSet하지만,를 사용하는 경우 TreeSet이를 작성 Comparable하거나을 제공해야합니다 Comparator. 클래스에 특정 순서가 없으면 문제가 될 수 있습니다.

나는 아주 작은 세트 / 맵 (<10 항목)에 때때로 TreeSet(또는 실제로 TreeMap) 사용했습니다. 하지만 실제로 얻는 것이 있는지 확인하지는 않았습니다. 큰 세트의 경우 그 차이가 상당 할 수 있습니다.

정렬이 필요한 TreeSet경우 업데이트가 자주 발생하고 정렬 된 결과가 자주 나타나지 않더라도 때때로 내용을 목록이나 배열에 복사하여 정렬하는 것이 더 빠를 수 있습니다.

답변

빈번한 재해시 (또는 HashSet의 크기를 조정할 수없는 경우 충돌)를 초래할 수있는 충분한 요소를 삽입하지 않으면 HashSet은 일정한 시간 액세스의 이점을 제공합니다. 그러나 많은 성장 또는 축소가있는 세트에서는 구현에 따라 실제로 Treeset으로 더 나은 성능을 얻을 수 있습니다.

메모리가 저에게 도움이된다면, 상각 된 시간은 기능적인 레드-블랙 트리로 O (1)에 가까울 수 있습니다. 오카 사키의 책은 내가 뽑을 수있는 것보다 더 나은 설명이 될 것이다. (또는 그의 출판물 목록 참조 )