小鹏求职日记第一阶段——梳理自身能力——1-28

List集合和Map集合和Set集合

1.Java主要有三大类集合，分别为Set，List和Map三种，都位于java.util包中。

三个类的区别分别为Set不是按照顺序排序，并且没有重复对象，但是其一些类可以实现有序（TreeSet）或者也可以通过实现java.util.Comparator<Type>接口来自定义排序方式，只能有一个null。List的对象按照索引位置进行排序，可以有重复对象和null对象。List和Set都实现了collection接口（Map没有继承）。Map自身就是一个独立的接口，Map的每一个Entry都有两个对象，一个为Key其不能重复，一个是Value可以重复。

List的主要实现类：ArrayList、Vector、LinkedList、Stack（继承于Vector）。

ArrayList继承List接口，底层使用数组实现。该集合是可变长度数组。是线程不安全的，查询快，增删慢。面对并发的修改，迭代器很快会失效。其remove方法很有特色，是从删除元素到末尾的元素全部往前移动一个单位，制空最后一个的值，方便GC。ArrayList的add方法流程，先推断容量是否充足，如果充足，就在数组的最后一位添加对象。如果不充足，进行扩容，数组扩容时会将老数组中的元素重新拷贝一份到新数组，每次数组的增量为其容量的1.5倍。

LinkedList继承List接口，底层使用环形双向链表，数据结构我们称为节点，对象可以为null在内的所有对象，是线程不安全的，查询慢，增删快。双向链表节点对应的类Node的实例，Node中包含成员变量：prev，next，item。其中，prev是该节点的上一个节点，next是该节点的下一个节点，item是该节点所包含的值。其查找是使用二分查找，先判断index在链表的那一半，然后再在进行遍历，这样最多只要遍历链表的一半节点即可找到。LinkedList的add方法很有趣，如果是新增元素，不需要判断是否容量充足，直接找到最后一个节点，将其指向下一个节点指向新节点，将新节点下一个节点置空。

Vector继承List接口，底层使用的是数组，效率慢，但线程安全。由于使用越来越少，就不多描述了。但是有一点，Vector是线程安全的，所以在多线程使用时，可以考虑使用Vector而不是使用ArrayList(类似于StringBuffer和StringBuilder一样，前者线程安全，可以在多线程中发挥作用而不用担心会出现数据错误的情况)。

Stack继承Vector，实现了List接口。但是这是个特殊的，先进后出。在目前而言，已经被淘汰了，基本没有见到有人使用。

Set的主要实现类：TreeSet、HashSet

Set和List一样，都是继承于Collection,是集合的一种。和List不同的是，Set内部实现是基于Map的，所以Set取值时不保证数据和存入的时候顺序一致，并且不允许空值，不允许重复值。所以其实Set是Map的马甲，我们可以这么认为，Map的Key就是Set。

TreeSet继承于Set接口，但是和一般Set不一样的是，他居然是有序的！回忆一下，我的盆友，就在刚刚提到的Map的马甲Set是就是Map的Key一样的东西，最大的特点之一就是无序。那这个TreeSet怎么就有序了呢？我百度了一下，查出来的资料真的是惊了，和TreeMap有关(常威你还说你不会武功。。。)。TreeSet是线程不安全的。看了一下TreeSet的源代码，感觉不算特别困难，如果有兴趣的盆友可以去这一篇看看其底层代码。（https://www.cnblogs.com/skywang12345/p/3311268.html）

HashSet，说实话一看到这个名字我心里就想到HashMap，果然！Set就是Map披着Collection的皮，说自己是List的兄弟，其实就是隔壁老M的儿子！！！先看一下HashMap的底层代码

public HashSet(){map = new HashMap<>();}//对这个就是HashSet的底层创建。。。

markdown 这个加粗有点麻烦啊！！！
有点用不习惯。。。
贴一段HashSet的底层代码

新鲜截图出来的

所以其实Set的底层是依赖于Map实现的，所以Set的实现类基本都能找到对应的Map的实现类。

Map的主要实现类：HashMap，LinkedHashMap和TreeMap

其实对于Map的底层我知之甚少，唯独HashMap了解深入一些。比如hashMap的底层是数组+链表。HashMap的初始其实很简单，就是一个长度为十六的数组（如果你不指定的话，默认为16）。

transient Node<K,V>[] table;//这个就是列表，注意是节点！！！

但是Map要是超过16个怎么办？链表的作用就出来了。hashMap作为建立在hash表上的Map，肯定和hash表完全离不开。
当我们要创建一个新的Entry存入HashMap时，我们首先根据其Key得出hash值，确定这个Entry存到哪个数组位置中，然后就看这个数组位置上是否有key了，没有就占了这个位置，如果有检查这个位置上的Key是否有相同的，如果有，就将值修改为新的value。如果没有，就加一个进去。
但是问题来了，就算我前面16个Entry的Key得出的hash值都没有重复，那么我来17个怎么办。。。这时候就需要链表的协助了。我们依靠链表来补充拥有超多对象的Map。假如我新加入的Entry的相对应的数组上面已经用一个对象了，那么我就在这个对象的后面加上新的对象。所以hashMap是增删查改都很快的，因为其同时拥有数组和链表的好处。便于添加删除的同时，也便于查找。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}//如何得到hash值

看懂这个方法首先需要明白^和>>>这个两个运算符号
^这个符号叫做异或运算符，两个操作数的位中，相同则结果为0，不同则结果为1
比如2^5=7 因为0010^0101=0111

>>>这个符号叫做无符号右移，忽略符号位，空位都以0补齐
比如5>>>2 0101>>>2等于0001=1,5>>> 0101>>>1 0010=2

再来看下hash这个方法，先取key的hashcode，这个是个native的方法，然后再与右移16位的值取异或。
举个例子

int h = "hello".hashCode();
System.out.println("result1 : "+ h);
System.out.println("result2 : "+ (h>>>16));
System.out.println("result3 : "+ (h^(h>>>16)));
/*
结果为
result1 : 99162322
result2 : 1513
result3 : 99163451
*/

此处大家可以去看看这个文章（https://blog.csdn.net/wz249863091/article/details/77483948）讲解很详细，上面那个hash值讲解便是来自于他