# Set

元素无序（存储时不是按照类似数组索引顺序添加）、唯一。底层都是对应的*Map。由于没有索引，只可以通过Iterator或foreach。与Collection接口的方法一致，Set 的实现类都重写了toString()方法。
使用Set集合保存自定义对象（可为 null）。带有Hash*的必须重写hashCode()和equal()方法，且重写的俩方法尽可能保持一致性（即相等的对象必须有相同的 hashCode ，不相等亦如此）

# HashSet

底层数据结构是哈希表（元素为链表或红黑树的数组），实际上是一个HashMap实例（value 存储静态的 Object），查询快。根据hashCode决定元素的存放位置，但迭代出的元素顺序和存入顺序不一定一致，即不稳定（hash重排）。
初始容量为16，当如果使用率超过0.75，(16*0.75=12) 就会扩大容量为原来的2倍（16扩容为32，依次为64,128....等）
添加元素过程（以 HashSet 为例）
- 向HashSet中添加元素a，首先调用元素a所在类的hashCode()方法，计算元素a的hashCode。
- 此hashCode值接着通过某种散列函数（如：取模。这个散列函数会与底层数组的长度相计算得到在数组中的下标，并且这种散列函数计算还尽可能保证能均匀存储元素，越是散列分布，该散列函数设计的越好）计算出在HashSet底层数组中的存放位置（即为：索引位置），判断数组此位置上是否已经有元素：
  - 如果此位置上没有其他元素，则元素a添加成功。 ——>情况1
  - 如果此位置上有其他元素b（或以链表或红黑树形式存在的多个元素），则比较元素a与元素b的hashCode值：
    - 如果hashCode值不相同，则元素a添加成功。——>情况2
    - 如果hashCode值相同，进而需要调用元素a所在类的equals()方法：
      - equals()返回true,元素a添加失败
      - equals()返回false,则元素a添加成功。——>情况3
- 对于添加成功的情况2和情况3而言：元素a与已经存在指定索引位置上数据以链表或红黑树的方式存储。
  - JDK7：元素a放到数组中，指向原来的元素。
  - JDK8：原来的元素在数组中，指向元素a
    
    总结：七上八下

# LinkedHashSet

继承HashSet，底层数据结构是双向链表和哈希表（元素为链表或红黑树的数组），元素迭代顺序和存入顺序一致
LinkedHashSet插入性能略低于 HashSet，但在迭代访问 Set 里的全部元素时有很好的性能。

# TreeSet

底层数据结构是红黑树（自平衡二叉树），有序，查询速度比List快 ，实际上是一个 TreeMap实例。使用TreeSet保存自定义元素，这个元素必须实现Comparable接口或构造时必须提供Comparator实现类
- 元素唯一性通过红黑树存储时确定，相同元素丢弃， 根据compareTo返回值是否是0来决定
- 元素的顺序通过红黑树存储，并通过中（根）序遍历展示
新增的方法如下：
- Comparator comparator()
- Object first()
- Object last()
- Object lower(Object e)
- Object higher(Object e)
- SortedSet subSet(fromElement, toElement)
- SortedSet headSet(toElement)
- SortedSet tailSet(fromElement)
保证元素的排列方式：
1. 自然排序（元素具备比较性）：让元素所属的类实现Comparable接口，重写compareTo
  
  向 TreeSet 中添加元素时，只有第一个元素无须比较compareTo()方法，后面添加的所有元素都会调用compareTo()方法进行比较。且重写该对象对应的 equals() 方法时，应保证该方法与 compareTo(Object obj) 方法有一致的结果
2. 比较器排序（集合具备比较性）：让集合构造方法接收Comparator接口的实现类对象，重写compare
  
  向 TreeSet 中添加元素时，只有第一个元素无须比较compare()方法，后面添加的所有元素都会调用compare()方法进行比较。且重写该对象对应的 equals() 方法时，应保证该方法与 compare() 方法有一致的结果
  
  s1-s2升序，s2-s1降序
```
// Lambda
TreeSet<Person> people = new TreeSet(
    Comparator.comparingInt(Person::getAge).thenComparing(Person::getName).reversed()
); 
```

# List 与 Set 之间转换

都可以在构造时传递对方
都继承了 Collection 的 addAll（以整体添加，但每个都是独立的）、add（当成单独元素）

← List Queue →