Java基础（3）｜Collection
目录1、Collection接口继承树
2、基本操作
- add(Object o)：增加元素
- addAll(Collection c)：...
- clear()：...
- contains(Object o)：是否包含指定元素
- containsAll(Collection c)：是否包含集合c中的所有元素
- iterator()：返回Iterator对象，用于遍历集合中的元素
- remove(Object o)：移除元素
- removeAll(Collection c)：相当于减集合c
- retainAll(Collection c)：相当于求与c的交集
- size()：返回元素个数
- toArray()：把集合转换为一个数组
3、Collection的遍历
Collection的遍历可以使用Iterator接口或者是foreach循环来实现
4、Set
Set集合不允许包含相同的元素，而判断两个对象是否相同则是根据对象的hashcode和equals方法。
4.1、HashSet
带着问题去学习
1.HashSet底层是什么数据结构？
2.HashSet允许有空值么？
3.HashSet允许有重复值么？
4.如果new两个值一样的字符串，往HashSet集合中添加，是否能添加进去？
5.HashSet是如何保证元素的唯一性的？
6.HashSetadd方法其实是调用的那个方法？
7.HashSet是否是线程安全的呢？
上面的几乎都没有什么难度，使用过集合的大多数人都了解。
那我们来看看哪些硬核的难点吧！
我们都知道HashSet底层其实上是new了一个HashMap集合，那我们就来看看，HashSet调用add方法的时候的一些问题。
1.HashMap的value部分值是否相同？
2.HashMap的初始化容量是多大？是在什么时候进行初化容量？
3.在计算HashMap的key的HashCode值的时候是单纯的时候hashCode方法计算出来的么？
4.HashMap什么时候进行扩容？
5.HashMap数组转红黑树需要满足那些条件？
7.HashSet在添加重复元素的时候，具体是怎么进行判断该元素已经存在的？
8.使用HashSet集合的时候，需要重写HashCode和equlas方法么？
那我们来看看哪些硬核的难点吧！
1.HashMap的value部分值是否相同？
2.HashMap的初始化容量是多大？是在什么时候进行初化容量？
3.在计算HashMap的key的HashCode值的时候是单纯的时候hashCode方法计算出来的么？
4.HashMap什么时候进行扩容？
5.HashMap数组转红黑树需要满足那些条件？
7.HashSet在添加重复元素的时候，具体是怎么进行判断该元素已经存在的？
8.使用HashSet集合的时候，需要重写HashCode和equlas方法么？
1、HashSet底层是什么数据结构？
HashSet底层采用的是数组+链表+红黑树，在new HashSet的时候实际底层是new了一个HashMap，把HashMap的key部分，作为HashSet的Value部分。
2、HashSet允许有空值么？
准确的来说是允许的（也就是代码不会出现异常），但是只能有一个空值，如果有第二个空值，那么第二个空值将加不进HashSet集合。
3.HashSet允许有重复值么？
肯定是不允许的，因为HashSet的value部分是HashMap的key部分，因为HashMap的key本身就是无序不可重复的，所以HashSet也就不可能重复。
4.如果new两个值一样的字符串，往HashSet集合中添加，是否能添加进去？
是不可以加入进去的，因为在进行添加元素的时候会进行判断，通过hashCode方法和equals方法进行比对，String这个类，重写了这两个方法，比较的是字符串的值，而不是使用继承自Object的equlash和hashCode方法去进行比较。
5.HashSet是如何保证元素的唯一性的？
依赖于hashCode()和equals()这两个方法，所有在我们比较两个我们自定义的对象的时候，需要我们重写这两个方法，自定义比较规则，否则就是使用继承自Object的进行比对，比对的是对象的内存地址。
6.HashSet的add方法其实是调用的哪个方法？
其实调用的是HashMap的map.put方法。
7.HashSet是否是线程安全的呢？
HashSet是线程不安全的，所以呢？他的执行效率比较高，因为HashSet和HashMap的源代码中的方法都有没有加synchronized关键字。
那我们来看看哪些硬核的难点吧！
1.HashMap的value部分值是否相同？
都是相同的，因为value部分是使用了一个静态的Object对象进行占位，这个对象只是用于占位操作，并没有多大的实际意义。
private static final Object PRESENT = new Object();
2.HashMap的初始化容量是多大？是在什么时候进行初化容量？
初始化容量是16，是在第一次调用resize()方法的时候进行扩容的，并不是new HashMap方法的时候就进行扩容。
3.在计算HashMap的key的HashCode值的时候是单纯的时候hashCode方法计算出来的么？
不是，而是通过一个表达式进行计算后的结果（
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)），并不是单纯的hashCode值。
4.HashMap什么时候进行扩容？
底层数组超过临界值12的时候就会进行扩容，那么为什么不是到16才进行扩容呢？试下一下，他是一个线程不安全的集合，万一此时突突来了很多对象，要加入到这个集合，那么这个集合不就炸了么？扩容的机制就是：
当前数组容量乘以2再乘以加载因子0.75每次添加元素的时候都会++Size，并不是说，这个数组中满了12个单向链表的时候进行扩容。
5.HashMap数组转红黑树需要满足那些条件？
首先判断该链表是否已经到达8个节点，如果满足该条件，再次进行判断这个数组链表的值是否大于64，如果小于64，还不会转化为红黑树，而是进行数组的扩容，大于64再转红黑树。
7.HashSet在添加重复元素的时候，具体是怎么进行判断该元素已经存在的？
进行equlas方法和HashCode方法进行比对，如果比对不出来再进行判断该链表是不是一颗红黑树，是的话进行红黑树的方式进行判断，如果不是，那么就遍历该链表，依次进行比对，如果比对到匹配的值，那么添加失败，如果没有比对到相等的值，那就把该元素添加到该链表的末尾。
8.使用HashSet集合的时候，为什么要重写HashCode和equlas方法？
因为底层添加元素的时候会调用这两个方法进行比对，而这个两个方法就是需要我们自定义比对规则，不然默认继承Object的。
源码分析，证明答案
new HashSet的源码：
//执行构造器
public HashSet() {
map = new HashMap<>();
}
1.第一次调用add方法的源码分析：
// 第一次add方法的执行过程：
// 2.add方法 ：调用map的put方法 PRESENT：静态的一个Object对象 用于占位，每一个map的value都是用一个对象
* public boolean add(E e) {
* return map.put(e, PRESENT)==null; //如果return null的时候就代表执行成功了
* }
* // 调用hash方法获取到key的hash值
* 3. public V put(K key, V value) {
* return putVal(hash(key), key, value, false, true);
* }
* // 通过hash算法获取的key的hash值 此hash值并不等于key原本的hash值
* static final int hash(Object key) {
* int h;
* return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
* }
*
* 4.得出hash值后 然后去putValue方法判断是否应该把这个值添加进去
* final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
* boolean evict) {
* Node<K,V>[] tab; Node<K,V> p; int n, i; //定义辅助变量，建议我们在开发的时候，需要用的时候再进行定义临时变量
* // 第一次进来 if成立，调用resize()
* if ((tab = table) == null || (n = tab.length) == 0) //table 其实就是HashMap里面的那个Node数组[] 存放链表的那个数组
* n = (tab = resize()).length; //resize())执行完后，返回一个初始化容量为16的table[]数组
*
* // 通过key的hash值计算出元素应该存放到table数组的那个索引位置
* //并把这个位置的对象赋值给临时变量p，判断p是否为null
* //如果p为空，代表这个位置还没有存放过元素，就创建一个node对象，key和value都放进去，next为null，留给第后来添加的元素存放Node对象
* if ((p = tab[i = (n - 1) & hash]) == null)
* tab[i] = newNode(hash, key, value, null);
* else {
* Node<K,V> e; K k;
* if (p.hash == hash &&
* ((k = p.key) == key || (key != null && key.equals(k))))
* e = p;
* else if (p instanceof TreeNode)
* e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
* else {
* for (int binCount = 0; ; ++binCount) {
* if ((e = p.next) == null) {
* p.next = newNode(hash, key, value, null);
* if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
* treeifyBin(tab, hash);
* break;
* }
* if (e.hash == hash &&
* ((k = e.key) == key || (key != null && key.equals(k))))
* break;
* p = e;
* }
* }
* if (e != null) { // existing mapping for key
* V oldValue = e.value;
* if (!onlyIfAbsent || oldValue == null)
* e.value = value;
* afterNodeAccess(e);
* return oldValue;
* }
* }
* // 记录修改的次数
* ++modCount;
* if (++size > threshold) //判断当前这个table数组是否超过了12这个最大容量值，如果超过进行扩容
* resize();
* // 这个方法其实是一个空方法，是留给子类去实现的
* afterNodeInsertion(evict);
* return null; //程序走到这儿，就代表我们第一次添加的元素已经成功了
* }
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//只有第一次add的时候才会执行这个 if
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 此时这个 方法为false 因为这次添加的元素是我们上次已经添加过的元素，所以算出来的下标1肯定是和上一次算出的下标一致
// 判断这个数组的下标位置中是否已经有链表元素存在
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//添加重复值的时候执行：
Node<K,V> e; K k;
// 此时的这个p就是指向的上面算出来的数组下标里的那个Node对象
//如果当前索引位置对应的链表的第一个元素和准备添加的这个key的hash值hash值相同
if (p.hash == hash &&
//如果hash值相同的情况下 当前准备要加入的key和刚刚计算出来的数组下标对应的那个Node对象的key是同一个对象 或者
// 当前的这个key不为null然后在和计算出来的那个数组下标对应的那个Node对象里的key进行equals比较，
//如果没有重写那么调用的就是继承自Object的equals方法，如果重写过，那么就调用重写后的，hashcode方法也是一样，所以建议两个方法都重写
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果上面一个条件为假 再判断 这个p是不是一颗红黑树，如果是红黑树的话再按照红黑树的方式进行比较
// 如果是红黑树 调用：putTreeVal（）； 方法进行添加
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 假如不是红黑树，那就是第三种情况：按照上面第一个情况的方式依次和整个链表进行比较，如果找到条件满足的那就直接break（此元素已经存在）；
// 结束遍历，return oldValue 那么就代表着添加失败，如果说，比较完后都没有满足条件的（该元素不存在），那就挂载到这个链表的末尾
// 在把元素添加到最后，立即判断 该链表是否已经到达8个节点，如果到达，调用treeifyBin(tab, hash);方法把当前这个链表转化为红黑树
判断条件如下： if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize();
// 上面条件不成立才进行树化 再进行转红黑树时还进行判断这个数组链表的值是否大于64，如果小于64，还不会转化为红黑树，而是进行数组的扩容，大于64再转红黑树
for (int binCount = 0; ; ++binCount) {
// 遍历整链表，都没有找到值一直的，直接添加到链表的末尾
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果 比的过程中找到一个值与准备添加的元素的值一致，那么就直接break，添加失败
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
4.2、LinkedHashSet
LinkedHashSet类也是根据元素的hashCode值来决定元素的存储位置，但它同时使用链表维护元素的次序。与HashSet相比，特点：
- 对集合迭代时，按增加顺序返回元素。
- 性能略低于HashSet，因为需要维护元素的插入顺序。但迭代访问元素时会有好性能，因为它采用链表维护内部顺序。