【Java】TreeMap与TreeSet

男娘i 2024-03-16 20:48 57阅读 0赞

### TreeMap的底层原理 ###

*  TreeMap**基于红黑树**（Red-Black tree）实现。
 *  映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。
 *  TreeMap的基本操作containsKey、get、put、remove方法。
 *  TreeMap包含几个重要的成员变量：root、size、comparator。
    
     *  其中root是红黑树的根节点。root是Entry类型，Entry就是红黑树的节点。
        
         *  Entry包含6部分：key、value、left、right、parent和color。
         *  Entry节点根据Key排序，包含的内容是value。
         *  Entry中key比较大小是根据比较器comparator来进行判断的。
 *  size是红黑树的节点个数。

### TreeSet 的原理 ###

*  底层是基于`TreeMap`来实现的，所以底层结构也是红黑树。
 *  因为是红黑树结构，所以不需要重写`hashCode()`和`equals()`方法来保证唯一性，它的去重是依靠比较器来去重，每次插入都会遍历比较来寻找节点的插入位置，如果发现某个节点的值是一样的那就会直接覆盖。
 *  TreeSet 用于 保存数据的是 NavigableMap<E,Object> 接口类型，实际上还是使用的 TreeMap 这个实现类
 *  TreeSet是有序集合，排序方式分为两种。
 *  TreeSet只能通过迭代器迭代元素

### TreeSet和HashSet的异同点 ###

*  **相同点：**
    
     *  HashSet、TreeSet中的元素都是不能重复的，并且它们都是线程不安全的
 *  **不同点：**
 *  HashSet是用HashMap来存储数据，而TreeSet是用红黑树来存储数据。
 *  HashSet中的元素可以是null，但TreeSet中的元素不能是null；
 *  HashSet不能保证元素的排列顺序，而TreeSet支持自然排序、定制排序两种排序的方式；
    
     *  如果需要排序，则使用TreeSet
     *  如果不需要排序的话，则使用HashSet