阿里面试实战题1----TreeSet,HashSet 区别

2024-08-31 17:40:28

TreeSet，HashSet 区别

TreeSet

 public class TreeSet<E> extends AbstractSet<E>

     implements NavigableSet<E>, Cloneable, java.io.Serializable

 {

     public TreeSet() {

         this(new TreeMap<E,Object>());

     }

 }

可以从代码中明显看出。TreeSet的底层其实是TreeMap。

而TreeMap是一个有序的key-value集合，它是通过红黑树实现的。

TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparable 进行排序（实现其compareTo进行排序），具体取决于使用的构造方法。

TreeMap可以详细看这篇 TreeMap 还能排序？分析下源码就明白了

HashSet

 public HashSet() {

     map = new HashMap<>();

 }

很明显，底层是HashMap实现。具体看这篇文章。基于JDK1.8的HashMap分析

TreeSet,HashSet 区别

TreeSet底层是TreeMap，HashSet底层是HashMap
TreeSet增加查找删除是O(lgn)。HashSet增加查找删除是O(1)，最坏情况是O(n)
TreeSet底层TreeMap可以有序，HashSet底层HashMap一定无序。

最新文章

热门文章