HashSet、TreeSet、LinkedHashSet 学习_hashset treeset linkhashset

一、HashSet 概念

public class HashSet extends AbstractSet
implements Set, Cloneable, java.io.Serializable

存储结构

	// 底层数据结构其实是一个 HashMap
	private transient HashMap<E,Object> map;

    // HashSet 存储的值其实是作为 HashMap 的 key存储，所有key对应的值其实就是这个 PRESENT 
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

	// 基本操作方法也都是通过 hashmap 的方法完成的
	public HashSet() { map = new HashMap<>(); }
	public Iterator<E> iterator() { return map.keySet().iterator();}

	// 也从 add 方法上可以看出来，set 的值是存储在 map 的key中，map 的value 是默认值
	public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二、HashSet 特点

**
不能重复
无序
可以存储 null （HashMap 的 key 可以为null）
线程不安全
**

三、TreeSet 概念

public class TreeSet extends AbstractSet
implements NavigableSet, Cloneable, java.io.Serializable

底层原理：使用NavigableMap，但NavigableMap只是一个接口，最终是使用TreeMap

同理，很多方法都是使用的 TreeMap 。

四、TreeSet 特点

不能重复
无序
元素必须实现自然排序和定制排序中的一种（TreeMap 默认会对key进行排序）
不可以存储 null （TreeMap 的 key 不可以为null，需要参与比较）
线程不安全

五、LinkedHashSet 概念

public class LinkedHashSet extends HashSet
implements Set, Cloneable, java.io.Serializable

我们都知道 LinkedHashSet 底层结构是 LinkedHashMap，但是单从 LinkedHashSet 的定义中看不出两者关系，最核心的主要时父类 HashSet 的私有构造方法.

// LinkedHashSet 子类的构造方法最后一个参数默认 true 
public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }

// HashSet 父类提供的构造方法
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
1
2
3
4
5
6
7
8
9

六、LinkedHashSet 特点

不能重复
有序（LinkedHashMap 有序）
可以存储 null （LinkedHashMap 的 key 可以为null）
线程不安全