HashSet 和 TreeSet 的底层原理
HashSet的底层源码：
研究思路：
1.研究继承关系
2.研究属性
3.理解创建集合的过程 – 构造方法的底层原理
4.研究添加元素的过程
场景：
public static void main(String[] args) {
HashSet<String> set = new HashSet<>();
set.add("aaa");//将元素添加到HashMap中：map.put("aaa",PRESENT);
set.add("bbb");//将元素添加到HashMap中：map.put("bbb",PRESENT);
set.add("ccc");//将元素添加到HashMap中：map.put("ccc",PRESENT);
set.add("ddd");//将元素添加到HashMap中：map.put("ddd",PRESENT);
}
}
1.研究属性
private transient HashMap<E,Object> map;//new HashMap<>();
//占位value
private static final Object PRESENT = new Object();
2.理解创建集合的过程 – 构造方法的底层原理
public HashSet() {
map = new HashMap<>();
}
3.研究添加元素的过程
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
4. HashSet分析的总代码
public class HashSet<E> extends AbstractSet<E> implements Set<E>{
private transient HashMap<E,Object> map;//new HashMap<>();
//占位value
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
//e - "ccc"
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
}
注意：HashSet底层由HashMap实现，HashSet的元素添加到HashMap中Key的位置。
5.深究
1.研究删除集合的过程
2.研究遍历集合的过程
TreeSet的底层源码：
研究思路：
1.研究继承关系
2.研究属性
3.理解创建集合的过程 – 构造方法的底层原理
4.研究添加元素的过程
场景1：
public static void main(String[] args) {
TreeSet<Student> set = new TreeSet<>();
set.add(new Student("小白", '女', 23, "2401", "002"));
set.add(new Student("小红", '女', 27, "2401", "001"));
set.add(new Student("小丽", '女', 21, "2401", "003"));
}
}
场景2：
public static void main(String[] args) {
TreeSet<Student> set = new TreeSet<>(new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
...外置比较器规则...
}
});
set.add(new Student("小白", '女', 23, "2401", "002"));
set.add(new Student("小红", '女', 27, "2401", "001"));
set.add(new Student("小丽", '女', 21, "2401", "003"));
}
}
1.研究继承关系
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>{
//外置比较器
private final Comparator<? super K> comparator;
//使用无参构造创建TreeMap，外置比较器对象就是null
public TreeMap() {
comparator = null;
}
//使用有参构造创建TreeMap，外置比较器对象由外界传入
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public V put(K key, V value) {
//获取外置比较器
Comparator<? super K> cpr = comparator;
//注意：以下判断说明了外置比较器优先于内置比较器，因为先找的是外置比较器，如果外置比较器为null，才执行内置比较器的比较规则
//外置比较器是否为null
if (cpr != null) {//外置比较器不为空
//执行外置比较器的比较规则
} else {//外置比较器为空
//执行内置比较器的比较规则
}
}
}
2.研究属性
private transient NavigableMap<E,Object> m;
//占位value
private static final Object PRESENT = new Object();
3.理解创建集合的过程 – 构造方法的底层原理
public TreeSet() {
//调用有参构造
this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
//有参构造，无参构造调用有参构造为接口的多态
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
4.研究添加元素的过程
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
5. TreeSet分析的总代码
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>{
//使用无参构造创建TreeSet -- new TreeMap<E,Object>()
//使用有参构造创建TreeSet -- new TreeMap<>(comparator);
private transient NavigableMap<E,Object> m;
//占位value
private static final Object PRESENT = new Object();
public TreeSet() {
this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
// e - new Student("椎名空", '女', 23, "2401", "002")
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
}
tips:
1. TreeSet底层由TreeMap实现。
2. TreeSet的元素添加到TreeMap中Key的位置。
6.深究
1.研究删除集合的过程
2.研究遍历集合的过程