java集合是一个常考的知识点，这一块呢，我们可以通过上面的图片进行分类，着重可以考虑ArrayList,LinkedList,Vector,HashSet，HashMap,TreeMap,LinkedHashMap等。
1.集合常见操作
0.集合的自实现hashcode和Equals方法
1.底层实现数据结构
2.如何实现hash函数，以及如何处理hash冲突
3.添加，获取，等常见操作函数
4.迭代器
5.各自优点和线程安全
2.List
2.1 ArrayList
0.hashcode 和 equals
-hashcode：遍历整个数组，h+=31*h+(e==null?0:e.hashcode);//h默认为1；
-equals 如果数据结构相同，则遍历整个集合，用e.equals比较
1.底层实现数据结构
底层使用一个 transient修饰的Object[] 数组。
2.没有hash冲突，所以没有使用hash函数
3.常见操作实现
- add()方法
首先，使用ensureCapacityInternal（）方法确保每次的数组容量是不是足够
part1:判断数组是不是为空，为空则默认初始化容量大小为10
part2:当数组里的元素容量大于数组长度时，扩容操作，新数组长度为旧数组长度+旧数组长度的/2；（扩容为原来的3/2）；
part3:数组长度大于（Integer.MAX_VALUE -8;）新数组长度，根据minCapacity获得最大值，为Integer.MAX_VALUE或者Integer.MAX_VALUE -8
part4:使用Arrays.copyOf（）将旧数组的值复制到新数组里面
- get方法
get方法比较简单，通过索引获取下标元素，如果索引大于数组长度，则报数组越界异常
-remove() 方法 --remove(int i),remove(Object)
如果删除的为对象，则将该对象的索引找到，然后把后面的元素依次后移，将最后一个位置变为null.
removeAll(Collection<?> c)
第一步：先判断要移除的集合是否为null，如果为null则抛出null异常。
第二步：如果不为null，则接着调用batchRemove方法即可移除成功。
1.代码的原理可以简单概述为如下过程：
2.通过contains方法，将所有不需要移除的元素放入elementData中，然后标记最后一个放入元素的位置w。
3.将所有需要移除的元素设置为null。
4.将size的大小设置为w。
5.修改modCount字段（该字段主要是为了防止多线程模式下安全问题）。
6.最后返回移除成功的标识。
4.迭代器
Arraylist 用了一个内部类实现了一Iterator接口，重写了，hasnext()和next()方法。
-hasnext()用一个cursor计数，从0开始，如果cursor等于size则hasnext()返回false
-next 首先判断是不是在遍历的过程中发生修改，如果发生修改，则抛出 concurrentModifycationException(),通过currsor每次递增，去去元素，如果这个时候currsor的长度大于数组长度同样抛出异常
5.优点以及线程安全
ArrayList的优点是能够动态扩容，相当于一个动态数组，但是是非线程安全的，建议在单线程中使用，且ArrayLists有三种遍历方式其中，通过索引随机访问是最快的。
2.2.Vector
Vector 中继承的父类和实现的接口和ArraysList完全相同
2.2.1Vector 的hashcode 和equals
Vecotr中的hashcode方法和equals方法完全是使用父类的hashcode方法和equals方法，但是用了Synchronized关键字进行了修饰
2.2.2 底层数据结构
Vector底层数据结构和ArrayList是相同得，都是采用的数组。
2.2.3 常用函数
- add()
Vector 的实现和ArrayList几乎相同，只是采用了Synchronzied修饰罢了,有一点不同的之处是在于，对于数组的初始化，Arraylist这里会做一个如果是第一次添加元素，会进行一个初始化，而Vectord的初始化过程在于构造函数。
- add(int index,E element)
在指定位置插入元素
首先判断，指定位置是不是合符要求，如果满足要求，则使用System.arrayCopy方法将所有元素后移一位，在指定位置插入元素。如果是使用addAll(Collection c)则原理是遍历整个Collection c然后依次插入元素。这个方法和ArrayList中的原理都是一样的。
但是两者的扩容机制不同，Arraylist扩容时所占的比例是为1.5倍，Vector扩容时所占的比例为2倍
- get()
get函数和ArrayList的get函数也是一样的
2.3 LinkedList
首先这个集合底层是由双向链表所实现的，每次新增或则删除都是对链表一个比较基础的操作。代码如下
-底层结构
通过代码可以知道，他的底层是无数个由Node数据结构所组成的一个链表的形式，每当创建一个新链表的时候，需要传入，prev(此节点的前一个节点)，element(当前节点的值)，next(下一个节点的值)。在LinkedList中会维护三个比较重要的成员变量，first(记录头节点)，last(记录尾节点)，size(记录链表长度)
-增
即创建一个新节点，每次添加到链表的尾部，如果为第一个节点，则first指向它，last也指向它
- 查
首先检查，参数index值是否合法，即是否大于0 且小于size,不合法报错，然后调用node(index)方法
判断index 是否大于 size的一半，大于采用从尾部向前遍历，小于从头往后遍历，直到找到第 index给位置为止
- 删除
remove();//不带参数默认删除第一个元素
remove(int index)；//带参数，检查索引是否合法，然后调node(index)查找，再删除，调正prev，next关系
remove(Object e);删除所有值等于 e的节点。
3.Set
HashSet底层就比较有意思了，它底层维护了的是一个hashMap集合，所有对集合的操作，都是基于hashMap的，我们来看一下代码
- add
我们可以看到，这个地方其实调用的是一个put方法，将add的值作为Key,new 一个对象作为value,但是我们思考一个问题，为什么不能存重复的值呢，HashMap不是可以存重复的值吗，我们看下hashmap的put方法我们就知道了
代码很长，我们就直接跳过前面的，大致意思就是，如果我们存的key已经存在了，则替换返回旧的值，如果不存在，就返回null，所以HashSet这里只需要判断一下该返回值是否为空，就可以知道其是否存入重复值了。
至于remove方法也是类似，如果删除成功了，则返回value值，否则返回空。
由于hashmap遍历时时无序的，所以Hashset遍历时也是无序的。
4.Linkedhashmap（有序的hashmap）
LinkedHashMap 和 hashmap 唯一的区别就是，解决了hashmap遍历的时候的无序性，解决的主要方法，就是将每个节点（注意这里指的是每个节点，不是数组下表后的节点）用双链表的形式链接。当然同时Linkedhashmap是继承了hashmap的底层数据结构的。
我们来看下他的数据结构：
双指针
这里可以注意到的是，每次创建一个新节点的时候，都会用尾插法维护链表的关系。从而使得每一个节点都用双链表维护着关系。
-boolean accessOrder 这个关键字，默认为false,则遍历的时候会按照put进来的顺序，遍历，如果accessOrder 为true时，put,get，操作时都会调用 afterNodeAcess,将被操作的节点移致双链表的尾巴处。
这样时的遍历的时候是按照操作的顺序遍历的。
如下：
我们可以看到 当对多操作了一次get("星期天")时，则输出时被放到了最后
最后看下如何遍历的：
通过 双链表的 head节点开始遍历，其他的地方和hashmap保持一致。
5.TreeMap（TreeSet）
treeSet不存放重复的元素，就是判读比较器是否返回0如果返回0证明相同，则不添加
TreeMap 底层就是一棵红黑树，对其的操作都是O（log2n）
这里需要值得一提得是，进行查找的时候，是可以实现一个比较器的Comparable，根据不同的Comparable以达到不同的比较效果。通过构造函数可以传入Comparable,达到不同的compare效果，
至于 TreeMap能不能存入null值，答案是如果采用默认的Comparable是不行的，但是如果你做了一个Comparable对其null进行了处理，则是可以的。
树的结构：
讲一下，put过程的实现
part0:判断 root是否为空，如果为空，则创建一个新节点，将root指向它
part1:root 不为空则判断comparable 比较器是不是传入的
part2:建立一个Entry<K,V>parent 节点，指向遍历节点，然后通过比较，是不是其孩子节点，直到找到对应的位置
part3:创建一个新节点，然后将其父节点指向这个新节点，通过比较器的结果判断是 左子树还是右子树
6.HashMap
1.hashMap的equals 和 hashcode方法
hashcode：将迭代遍历整个map,将所有next()的hashCode做一个累加。
equals:如果判断两个map集合是否相等，首先判断集合类型是否相等，集合大小是否相等，最后逐个遍历每个map集合中的Entry<>是否相等
2.hashmap的底层数据结构
hashmap的底层数据结构是，数组加链表的形式（哈希表）+红黑树（链表长度超过8时会变成红黑树）
-链表节点：
3.干扰函数
首先我们要理解到的是，key.hash & (tab.length-1)寻找位置是存在一定的hash冲突的，所以需要想办法进行减少这种冲突，这里所用的hash函数,可以理解为干扰函数，关于hash函数的实现，是将hash值得高16位和hash值得低16位做了一个异或操作，我们可以去假设就是如果当数组长度小于2的16次幂时， (tab.length-1)去与hash值进行&（与）运算，hash值得高16位是没有被用到的，则就容易造成hash值低16位相同得，容易产生冲突，例如3654061296和3652881648，所以可以让高16位和低16位进行异或操作，可以有效避免产生冲突。
具体可以参考https://blog.csdn.net/weixin_43689776/article/details/99999126
- hashmap如何解决空节点的
我们可以看到的是,如果key为null，则返回的hash值为0，然后会存入tab[0]这个位置，如果寻找的时候也是，在0这个位置寻找.
4.resize扩容机制
part0:如果表长大于2的30次方，则直接返回
part1:如果表长为空，则初始化一个新表，表长默认为16
part2:如果表长不为空，则将表长变为原来的2倍
part3:将原来的oldTab替换到newTab中，如果e.hash & oldCap ==0 则表示表元素的位置保持不动，否则则移动到oldCap+j的位置上
举个例子
oldcap=16,newcap=32,hash=101111，hash1=111111
hash&oldcap => 10000&101111 =0//表示保持不变
hash&(oldcap-1)=>1111&101111=15//原位置
hash&(newcap-1)=11111&101111=15//新位置
hash1=111111&oldcap=> 10000&111111=16//不等于0
hash1=111111&oldcap-1=>1111&111111=15//原位置
hash1=111111&newcap-1=>11111&111111=15+16=31//新位置（oldloca+oldlength）
5.jdk1.8hashmap为什么要引用红黑树
我们知道链表的时间复杂度为O（n）,而红黑树的时间复杂度为O（logN）,红黑树的效率明显高于原链表结构，那为什么不直接用红黑树代替呢，那是因为红黑树虽然查询效率高，但是在初始化的时候占用的空间比是普通节点的两倍，如果直接用红黑树代替必然会造成一定的资源浪费，所以当链的长度超过8时，此时的hashmap中元素分布已经非常密集了，已经非常多了，性能已经会相对较差了，这个时候再用红黑树代替，为了挽回性能，权衡之下，才使用红黑树，提高性能。
6.为什么 String、Integer 这样的 wrapper 类适合作为键？
因为hashmap结构存储的key,不可变是必要的，如果用的是可变对象，则hashmap存储的key的hash值也可能会发生变化，容易造成数据的丢失，而String 和Integer类是final修饰的，其重写了hashcode函数，和equals方法，如果想要用可变的对象作为健，则必须要重写hashcode函数和equals函数来达到key的hash值不变这个目的。
我们可以看看String的实现
hash//defalt to 0
7.常见操作 get,put
- 谈一下hashMap中get是如何实现的？
part1：判断不是空表以及表长是否大于0，如果满足则通过hash & table.length-1 找到具体位置否则返回null
part2:找到位置后，从头部开始比较，如果是头节点则直接返回（通过节点的hash值比对，以及通过equals方法判断，如果hash值不同，则不需要比较equals方法了，可以提高比较效率）
part3:如果不是头节点，则循环寻找，直到找到为止
-.谈一下hashMap中put是如何实现的？
part1:如果tab表为空，则初始化一个表结构，如果put的位置为空，则初始化一个新节点
part2:如果能通过key值能找到节点，则将节点中的value替换，如果不能，则在链表尾部插入一个新节点
part3:当当前key值所在的链表长度达到8则进行红黑树转换
part4:当当前表的长度大于threshold(factor*tab.length 一般是0.75即如果表里面的元素达到%75则)进行扩容操作，resize()函数
8.jdk1.8hashmap为什么是非线程安全的？
因为我看的是1.8得源码，所以对于网上很多关于1.7的源码自己并没有涉及，所以我这里只单独将一下，自己对1.8所导致的非线程安全的解释。
我们知道当两个线程同时进行处理的时候，可能会产生一些特殊的情况，我们假设线程1和线程2都在进行put操作，且两个进行put操作的key.hashcode相同，则当线程1进行hash碰撞之后，时间片耗尽暂时挂起，，这个时候线程2来进行put插入数据，即对于线程1重新占用cpu时发现已经进行了hash碰撞，则直接插入，这时将覆盖原线程2的数据，从而线程不安全
7.HashTable
1.底层数据结构 和hashmap保持一致，都是数组+链表的形式
HashTable的主要方法的源码实现逻辑，与HashMap中非常相似，有一点重大区别就是所有的操作都是通过synchronized锁保护的。只有获得了对应的锁，才能进行后续的读写等操作。
2. put方法
put方法的主要逻辑如下：
1.先获取synchronized锁。
2.put方法不允许null值，如果发现是null，则直接抛出异常。
3.计算key的哈希值和index
4.遍历对应位置的链表，如果发现已经存在相同的hash和key，则更新value，并返回旧值。
5.如果不存在相同的key的Entry节点，则调用addEntry方法增加节点。
6.addEntry方法中，如果需要则进行扩容，之后添加新节点到链表头部。
3. get方法
get方法的主要逻辑如下
1.先获取synchronized锁。
2.计算key的哈希值和index。
3.在对应位置的链表中寻找具有相同hash和key的节点，返回节点的value。
4.如果遍历结束都没有找到节点，则返回null。
4.rehash扩容方法
rehash扩容方法主要逻辑如下：
1.数组长度增加一倍（如果超过上限，则设置成上限值）+1（一直为素数）。
2.更新哈希表的扩容门限值。
3.遍历旧表中的节点，计算在新表中的index，插入到对应位置链表的头部。
5.remove方法
remove方法主要逻辑如下：
1.先获取synchronized锁。
2.计算key的哈希值和index。
3.遍历对应位置的链表，寻找待删除节点，如果存在，用e表示待删除节点，pre表示前驱节点。如果不存在，返回null。
4.更新前驱节点的next，指向e的next。返回待删除节点的value值。
6.hash冲突函数
7.hashtable 的size 为素数
hashtable 初始值为11
每次扩容之后size大小变成 2*size+1即一直为素数，为素数的原因是因为能够让，值能跟均匀的分配在hash桶里面。
6.hashmap 和 hashtable 的区别
1.HashMap是非同步的，没有对读写等操作进行锁保护，所以是线程不安全的，在多线程场景下会出现数据不一致的问题。而HashTable是同步的，所有的读写等操作都进行了锁（synchronized）保护，在多线程环境下没有安全问题。但是锁保护也是有代价的，会对读写的效率产生较大影响。
2.HashMap结构中，是允许保存null的，Entry.key和Entry.value均可以为null。但是HashTable中是不允许保存null的。
3.HashMap的迭代器（Iterator）是fail-fast迭代器，但是Hashtable的迭代器（enumerator）不是fail-fast的。如果有其它线程对HashMap进行的添加/删除元素，将会抛出ConcurrentModificationException，但迭代器本身的remove方法移除元素则不会抛出异常。这条同样也是Enumeration和Iterator的区别。
8.concurentHashMap
java1.7ConcurrentHashMap
数据结构：数组(Segment)+数组（HashEntry）+链表（HashEntry节点）
底层是一个Segment数组，存储一个HashEntry数组，每个HashEntry数组的头部存储的是链表的头节点
其实每一个Segment都会被一把锁所锁住，jdk1.7的思想就是，将一个大的表格，用分段锁，分成不同的小的表格。
put操作:
对于ConcurrentHashMap的数据插入，这里要进行两次Hash去定位数据的存储位置从
上Segment的继承体系可以看出，Segment实现了ReentrantLock,也就带有锁的功能，当执行put操作时，会进行第一次key的hash来定位Segment的位置，如果该Segment还没有初始化，即通过CAS操作进行赋值，然后进行第二次hash操作，找到相应的HashEntry的位置，这里会利用继承过来的锁的特性，在将数据插入指定的HashEntry位置时（链表的尾端），会通过继承ReentrantLock的tryLock（）方法尝试去获取锁，如果获取成功就直接插入相应的位置，如果已经有线程获取该Segment的锁，那当前线程会以自旋的方式去继续的调用tryLock（）方法去获取锁，超过指定次数就挂起，等待唤醒（美团面试官问道的，多个线程一起put时候，currentHashMap如何操作）
java1.8 concurrentHashMap
java 1.8和1.7最大的区别就是，不再采用分段锁的机制机制进行线程安全的同步，而是采用自旋锁加CAS（乐观锁）的机制进行线程安全的同步。concurrentHashMap的底层结构和hashmap是相同得
-put
-干扰函数
干扰函数
这里可以看到，同样也是拿hashcode值得高16位和低16位做了一个异或得操作，但是和hashmap不同的地方在于，这里得最后做了一个 与&操作，目的是为了和InterMax进行一个取模得操作
-自旋锁+CAS实现初始化
自旋锁+cas
这里可以看到这个逻辑，如果表为空，则调用initTable（）方法进行初始化，否则，判断如果在该hash值对应的下标元素是否为空，如果为空则创建一个新的节点
这里是怎么做到的呢，我们可以看到，casTabAT()这个函数，这个函数的意思就是，在数组的这个位置上，我有一个预期值 expect==null ,你给一个同样的的值，和我们这个预期值对应，如果两者先等，则将数组上的值替换成new Node 并返回 ture.并退出当前循环
这里我们假设如果有两个线程都执行到这一步了，同时调用这个casTabAt了，则至少有一个线程，将值改掉之后，另一个线程会执行false,执行false之后，执行成功的那个，break;退出循环，另一个则继续自旋，执行其他的 if--esle 分支条件了。
- 如果当前的数组正在扩容，则帮助他扩容
这里通过这个 f.hash == -1 (MOVED==-1) 判断它是否正在扩容，如果在扩容，则帮助它扩容
-synchronized(数组中某一下表的链表头节点，加锁)实现新增链表节点
这里注意到，由于整个代码块都是用synchronized进行加锁的，所以可以线程安全同步，但是值得注意的就是，这里有个binCount 用于统计链表的长度，以便待会判断是否大于阈值转换为红黑树，同时这里还判断节点的类型是否为红黑树，如果为红黑树的话，则用红黑树进行操作。
如果链表的长度大于等于8 则转换为红黑树，同时需要判断，数组的长度是不是为空，或则是否小于64，如果满足这个条件，则不会进行装换，会先进行扩容操作。
这里需要注意的地方就是，hashmap的红黑树的节点是TreeNode 而concurrentHasmap得红黑树节点是TreeBin，两者得区别在于TreeBin是一个对象，里面有一个属性记录了树的头节点，则当要对树进行操作的时候，则将整个TreeBin加锁，以达到线程同步，如果只有一个TreeNode加锁的话，可能由于左旋右旋操作，加锁的节点，不再是头节点了，则线程又会不安全。
ps：单链表装成红黑树的时候，这里会有一个先将链表装成双链表的操作，便于，红黑树中，将节点的一个指针指向父节点。
- 扩容操作
当当前数组长度大于阈值则进行扩容
-初始化操作
我们可以看到，简单来说。初始化操作就是，初始化一个大小为16的一个Node数组，这里为了使线程能够进行安全同步的，采用cas 对一个关键字sizeCtl进行操作，即当我整个线程进行操作的时候，我将sizeCtl改成-1，则其他线程进来的时候，如果也想初始化的话，则判断sizeCtl关键字是不是小于0,如果小于0则调用，Thread.yeild()//放弃cpu资源，然后退出。
-乐观锁/悲观锁
悲观锁认为，这个线程，发生并发的可能性极大，线程冲突几率大，比较悲观。一般用synchronized实现，保证每次操作数据不会冲突。乐观锁认为，线程冲突可能性小，比较乐观，直接去操作数据，如果发现数据已经被更改（通过版本号控制），则不更新数据，再次去重复 所需操作，直到没有冲突（使用递归算法）。
-hashmap1.7 扩容会致死循环的主要原因是因为，扩容的链表转移到新的位置上时采用的是头插法，这时候其他线程来捣乱很容易造成，闭环链表的实现，当get()操作的时候，就造成了死循环。
举个例子，e=tab[i]; e=e.next; p =e; tab[i+j]=p;... p.next=tab[i+j]; tab[i+j]=p; 如果 如果在将p的前面一个链表的节点插入之前，别其他线程执行了e=e.next,则两则的关系没有断开，则造成闭环
-hasmap1.8不会的原因是因为，链表扩容时是没有倒置的，前当长度大于8时会转成红黑树，所以不会出现死循环。
