이 글의 내용은 Java에서 TreeSet을 구현하는 방법에 관한 것입니다. (자세한 설명) 도움이 필요한 친구들이 참고하면 좋을 것 같습니다.
HashSet은 HashMap을 기반으로 구현되는데 TreeSet은 어떻게 구현되나요? 좋아요! 다들 생각하시는대로 TreeMap을 기반으로 구현되어 있습니다. 따라서 TreeSet의 소스 코드도 매우 간단합니다. 가장 중요한 것은 TreeMap을 이해하는 것입니다.
TreeSet의 상속 관계
평소처럼 TreeSet 클래스의 상속 관계를 먼저 살펴보겠습니다.
#🎜🎜 ##🎜 🎜#public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable
public interface NavigableSet<E> extends SortedSet<E>익숙한 취향, SortedSet 인터페이스를 상속합니다. SortedSet은 비교기를 반환하는 메서드를 제공합니다.
Comparator<? super E> comparator();은 SortedMap과 마찬가지로
자연 정렬
및사용자 정의를 지원합니다. 🎜🎜#. 자연 정렬을 위해서는 Set에 추가된 요소가 Comparable 인터페이스를 구현해야 하고, 사용자 정의 정렬을 위해서는 Comparator를 구현해야 합니다.
소스 코드 분석Key point
핵심은 자연스럽게 TreeSet이 요소가 그렇지 않음을 보장하는 방법입니다. 반복되고 요소의 순서가 맞습니다. 네, 앞서 말씀드린 것처럼 TreeMap 기반으로 구현되었으니 살펴보겠습니다.
private transient NavigableMap<E,Object> m; // 保证有序 // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); // 固定Value
TreeSet 소스 코드를 보면 이 두 가지 속성만 있는 것을 발견했습니다. 여기에는 포함되지 않습니다). 분명히 m은 요소를 저장하는 데 사용되지만 m은 TreeMap 대신 NavigableMap을 선언합니다. 여기서 NavigableMap을 사용하면 TreeSet을 더 유연하게 만들 수 있습니다. PRESENT는 HashSet의 PRESENT와 동일한 기능을 가지며 고정 값 값에 대한 자리 표시자 역할을 합니다.
추가 및 제거 방법을 살펴보세요.public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
HashSet 구현과 동일하며 Key도 사용합니다. Map에 의해 저장됨 - Value 키-값 쌍의 키는 반복되지 않습니다.
물론, TreeSet의 TreeMap은 생성자에서 초기화됩니다.
public TreeSet() {
this(new TreeMap<>()); // 默认自然排序的TreeMap
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator)); // 自定义比较器的TreeMap
}
public TreeSet(Collection<? extends E> c) {
this(); // 还是用的默认
addAll(c); // 将元素一个一个添加到TreeMap中
}
public TreeSet(SortedSet<E> s) {
this(s.comparator()); // 使用传入的SortedSet的比较器
addAll(s); // 一个一个添加元素
}
자연스럽게 정렬된 TreeMap은 기본적으로 인스턴스화됩니다. 물론 비교기를 사용자 정의할 수 있습니다.
여기에서 addAll 메소드를 추적하세요.
public boolean addAll(Collection<? extends E> c) {
// Use linear-time version if applicable
if (m.size()==0 && c.size() > 0 &&
c instanceof SortedSet &&
m instanceof TreeMap) {
SortedSet<? extends E> set = (SortedSet<? extends E>) c;
TreeMap<E,Object> map = (TreeMap<E, Object>) m; // 强转成TreeMap
Comparator<?> cc = set.comparator();
Comparator<? super E> mc = map.comparator();
if (cc==mc || (cc != null && cc.equals(mc))) { // 要保证set和map的比较器一样
map.addAllForTreeSet(set, PRESENT); // TreeMap专门为TreeSet准备的方法
return true;
}
}
return super.addAll(c);
}
은 TreeMap의 addAllForTreeSet메소드를 호출합니다. :
void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
try {
buildFromSorted(set.size(), set.iterator(), null, defaultVal);
} catch (java.io.IOException | ClassNotFoundException cannotHappen) {
}
}TreeMap 기사에서 분석된 buildFromSorted에 익숙해야 합니다. 이 방법은 전달된 집합 요소를 맨 아래 노드가 빨간색이고 다른 노드가 검은색인 빨간색-검정 트리로 구성합니다.
addAllForTreeSet方法：
public E first() {
return m.firstKey(); // 返回第一个元素
}
public E lower(E e) {
return m.lowerKey(e); // 返回小于e的第一个元素
}
public NavigableSet<E> headSet(E toElement, boolean inclusive) {
return new TreeSet<>(m.headMap(toElement, inclusive)); // 取前几个元素构成子集
}
public E pollFirst() { // 弹出第一个元素
Map.Entry<E,?> e = m.pollFirstEntry();
return (e == null) ? null : e.getKey();
}
public NavigableSet<E> descendingSet() { // 倒排Set
return new TreeSet<>(m.descendingMap());
}
......看到buildFromSorted，应该很熟悉，在TreeMap的文章中分析过。该方法将传入的集合元素构造成了一棵最底层的结点为红色，而其他结点都是黑色的红黑树。
导航方法
既然实现了NavigableSet，那各种导航方法自然少不了。它们的实现也很简单，直接调用m对应的导航方法即可。例如：
// 前面构造了一个存储Int的Set
// 3、5、7、9
SortedSet<Integer> subSet = intSet.headSet(8); // 最大值7，超过7越界
for (Integer sub : subSet) {
System.out.println(sub);
}
subSet.add(2);
// subSet.add(8); // 越界了
subSet.remove(3);
for (Integer sub : subSet) {
System.out.println(sub);
}
这里需要注意的是返回子集合的方法，例如：headSet。返回的子集合是可以添加和删除元素的，但是有边界限制，举个栗子。
public Iterator<E> descendingIterator() {
return m.descendingKeySet().iterator();
}
TreeSet也是支持逆序输出的，因为有descendingIteratorNavigation method
rrreee
여기서 주목해야 할 것은 headSet과 같은 하위 집합을 반환하는 메서드입니다. 반환된 하위 컬렉션은 요소를 추가하고 삭제할 수 있지만 예를 들어 경계 제한이 있습니다.rrreee
descendingIterator 구현이 있으므로 역순 출력도 지원합니다. #🎜🎜 ## 🎜🎜#rrreee
요약
TreeSet은 기반 TreeM AP 구현 예, 자연 정렬 및 사용자 지정 정렬을 지원하며 역순으로 출력할 수 있습니다.
#🎜🎜##🎜🎜##🎜🎜#TreeSet은 null 값을 허용하지 않습니다. #🎜🎜##🎜 🎜##🎜🎜## 🎜🎜#TreeSet은 스레드로부터 안전하지 않습니다. SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...))는 다중 스레드 환경에서 사용할 수 있습니다. 🎜🎜##🎜🎜##🎜🎜 #위 내용은 Java에서 TreeSet을 구현하는 방법은 무엇입니까? (상해)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!