当前位置: 代码迷 >> 综合 >> java TreeSet 源码分析
  详细解决方案

java TreeSet 源码分析

热度:31   发布时间:2023-12-23 09:03:20.0

底层数据结构:

TreeMap

哈哈,是不是很惊喜。

没错,treeSet在map(NavigableMap)的基础上,将存储内容作为键存储在map当中,实现了有序的set。

相关面试题

TreeMap和TreeSet在排序时如何比较元素?Collections工具类中的sort()方法如何比较元素?

源码:

public V put(K key, V value) {Entry<K,V> t = root;if (t == null) {compare(key, key); // type (and possibly null) checkroot = new Entry<>(key, value, null);size = 1;modCount++;return null;}int cmp;Entry<K,V> parent;// split comparator and comparable pathsComparator<? super K> cpr = comparator;if (cpr != null) {
    do {parent = t;cmp = cpr.compare(key, t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}else {if (key == null)throw new NullPointerException();@SuppressWarnings("unchecked")Comparable<? super K> k = (Comparable<? super K>) key;do {parent = t;cmp = k.compareTo(t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}Entry<K,V> e = new Entry<>(key, value, parent);if (cmp < 0)parent.left = e;elseparent.right = e;fixAfterInsertion(e);size++;modCount++;return null;
}

所以,需要实现比较器Comparator或者存放对象实现Comparable

Collections工具类中的sort()方法如何比较元素:(源码)

public static <T> void sort(List<T> list, Comparator<? super T> c) {list.sort(c);
}
list.sort():
default void sort(Comparator<? super E> c) {Object[] a = this.toArray();Arrays.sort(a, (Comparator) c);ListIterator<E> i = this.listIterator();for (Object e : a) {i.next();i.set((E) e);}
}
public static void sort(Object[] a, int fromIndex, int toIndex) {rangeCheck(a.length, fromIndex, toIndex);if (LegacyMergeSort.userRequested)legacyMergeSort(a, fromIndex, toIndex);elseComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
}//Arrays 对Object的排序操作是归并排序(优化后的)

HashSet和TreeSet有什么区别?

hashSet 的底层数据结构是HashMap,所以他俩的区别相当于TreeMap和HashMap的区别.

总结下:

数据结构

  hashmap:桶加链表

  treemap: 红黑树

是否有序

 treemap有序

hashmap无序

是否安全

  都不安全

时间、空间复杂度

  TreeMap基于红黑树(一种自平衡二叉查找树)实现的,时间复杂度平均能达到O(log n)。
  HashMap是基于散列表实现的,时间复杂度平均能达到O(1)。

适用场景

  相关解决方案