集合
一、List
（一）ArrayList
1.定义
容量可以改变的非线程安全的集合
2.底层实现
数组，默认大小为10，如果数据超过10，就会先创建一个新的大数组，然后将原数组中的数据复制（Arrays.coyyOf()方法）到新数组中，可以自定义初始大小new ArrayList(n)
3.特点
便于遍历、修改；不擅长插入、删除（需要移动其他元素）
4.方法
菜鸟教程
5.注意
（1）将数组转换成集合时，该集合不能使用add/remove/clear等修改集合的方法，但可以使用set()方法对指定元素进行修改，是因为数组转换成集合后，底层依旧是原数组，不可以使数组的长度发生改变，但是可以对数组某一元素的值进行修改
（2）可以使用泛型对集合中存在的元素类型进行限制，提高性能和安全性
（二）LinkedList
1.定义
实现了List接口和Queue接口，其对象可以表示顺序表，可以把他当做栈和队列使用
2.底层实现
链表（本质是双向链表）
3.特点
便于增加、删除；不擅长遍历、修改
4.方法
菜鸟教程
5.优点
LinkedList可以将零散的内存单元通过附加引用的方式关联起来，形成按链路顺序查找的线性结构，内存利用率较高
（三）LinkendList和ArrayList的区别
1.底层实现不同，ArrayList是数组，LinkedList是链表
2.ArrayList便于查找和修改，LinkedList便于插入和删除
（四）fail-fast错误监测机制
该机制常出现在多线程模式下，当前线程会维护一个计数比较器，即expextModCount，记录已经修改的次数；在进入遍历前，会把实时修改次数modCount赋值给expectModCount，如果两个值不等，则抛出异常
java.util下的所有集合类都是fail-fast；而concurrent包下的集合类都是fail-safe
fail-safe是指，截取当前某一状态的数据进行遍历
（五）COW
1.特点：在该容器内部对Iterator加锁，一种高并发思路，实行读写分离，如果是写操作，则复制一个新的集合，在这个新集合上进行写操作，在写操作完成后，再将原集合的引用指向新集合
2.优点：可以高并发的对COW进行读和写操作，而不需要加锁，因为当前集合不会添加任何元素
3.注意
**（1）**尽量设置合理的容量初始值，他扩容的代价比较大
**（2）**使用批量添加或删除方法时，如addall()和removeall()操作，在高并发请求下，可以攒一下需要添加和删除的元素，避免增加一个元素就要复制整个集合，内存的大量占用会导致GC的频繁发生，从而降低服务器的性能
**（3）**COW是fail-safe机制的，在并发包中的集合中都是由这种机制实现的，fast-safe是在安全的副本（或者没有发生写操作的正本）上进行遍历的，集合的修改和副本的遍历没有任何关系，但是缺点也很明显，读取不到最新的数据，这也是CAP理论中C（一致性）和A（可用性）的矛盾
4.使用场景：高并发且读多写少的场景，比如白名单，黑名单，商品类目的访问和更新场景
二、Map
Map是以Key-Value键值对来进行存储元素的哈希结构，Key是以某种哈希函数计算之后产生的唯一的，Value则是可以重复的
（一）HashMap
1.底层实现：数组+链表+红黑树
在链表节点大于等于8且数组长度大于等于64时，自动转换成红黑树（解决拉链过长带来的性能降低的问题）
2.函数方法：
3.HashMap在JDK1.8与1.8之前的区别
（1）JDK1.8之前用的是数组+链表；JDK1.8之后用的是数组+链表红黑树；
（2）链表的插入法由头插法变为尾插法【头插法会产生反转链表，多线程会出现循环链表】
（3）扩容时jdk1.8之前是重hash，1.8之后的简单判断在扩2^n;
（4）插入时JDK1.8之前是先判断是否要扩容再插入，1,8之后是先插入在判断是否扩容；
4.hashmap为什么使用链表
数组的长度是有限的，hash值可能会相同，当hash值相同时就产生了链表（解决了哈希碰撞）
拉链法
拉链法又叫链地址法，Java中的HashMap在存储数据的时候就是用的拉链法来实现的，拉链发就是把具有相同散列地址的关键字(同义词)值放在同一个单链表中，称为同义词链表。有m个散列地址就有m个链表，同时用指针数组T[0…m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插入到以T[i]为指针的单链表中。T中各分量的初值应为空指针
5.HashMap是怎么插入数据的
首先判断数组是否为空，为空则初始化数组，不为空则计算存储位置【(n-1)&hash】；
判断其存储位置是否存在元素，如果不存在则放入数据，如果存在【哈希冲突产生（hashcode相同）】，判断其Key是否相等，相等则覆盖并返回旧值，不相等则判断当前节点是否为红黑树节点，不是就插入链表，判断链表长度是否大于8，大于则转换成红黑树，如果是红黑树节点，就存入红黑树，判断存入后的节点数是否大于阈值，大于就进行扩容【2N】，结束操作
6.HashMap怎么设置初始化容量大小
一般默认的初始化容量为16，负载因子是0.75，若自己传入初始大小为K，那么初始 化大小为大于K的2的整数次幂，K=10，大小为16.HashMap的默认长度为16,是为了降低hash碰撞的几率。
7.那为啥用16不用别的呢？
因为在使用不是2的幂的数字的时候，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。
只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。这是为了实现均匀分布。
当length为奇数时，length-1为偶数，而偶数二进制的最后一位永远为0，那么与其进行 & 运算，得到的二进制数最后一位永远为0，那么结果一定是偶数，那么就会导致下标为奇数的桶永远不会放置数据，这就不符合我们均匀放置，减少冲突的要求了。如果直接用偶数就不满足当length为2的N次方的时候，h & (length-1) = h % length
8.HashMap为什么扩容是2的倍数
（一个值的hash码）&(hash表长度-1)，如果长度是2的倍数，长度减一的二进制就是以1111结尾的，与其他数进行&运算，可以减少结果中二进制有数字0的出现几率，碰撞几率小。
总结：因为2的幂-1都是11111结尾的，所以碰撞几率小。
9.提到哈希函数，你知道HashMap的哈希函数是怎么设计的吗【hash怎么实现的】？为什么这么设计？
JDK1.8中,是通过hashCode()的高16位异或低16位实现的:(h=k.hashCode())^(h>>>16),主要是从速度,功效和质量来考虑的,减少系统的开销,也不会造成因为高位没有参与下标的计算,从而引起的碰撞。
为什么要这样操作呢
如果当n即数组长度很小，假设是16的话，那么n - 1即为1111 ，这样的值和hashCode直接做按位与操作，实际上只使用了哈希值的后4位。如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解决了这个问题。
10.为什么要重写equals和hashCode？
object下默认的equals在比较基本类型的就是比较值是否相等；
当涉及到引用对象的时候就是比较引用对象的地址；
所以引用对象就需要重写equals；
HashCode也是根据地址计算；
光重写equals，不重写hashCode就会导致数据相等但是hashCode不一致；
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
11.为什么采用HashCode的高16 位与低16位进行异或运算能减少Hash碰撞？Hash函数可以直接用KEY的HashCode？
保证了对象的hashCode的32位值只要有一位发生改变,整个hash()返回值就会改变。尽可能的减少碰撞。
（2）不可以，因为hashCode()方法返回的是int整数类型，其范围为-(2 ^ 31)~(2 ^ 31 - 1)，约有40亿个映射空间，而HashMap的容量范围远远比他小，HashMap通常情况下是取不到最大值的，并且设备上也难以提供这么多的存储空间，从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内，进而无法匹配存储位置；
12.为什么JDK1.8使用红黑树？
比如某些人通过找到你的hash碰撞值，来让你的HashMap不断地产生碰撞，那么相同key位置的链表就会不断增长，当你需要对这个HashMap的相应位置进行查询的时候，就会去循环遍历这个超级大的链表，性能及其地下。java8使用红黑树来替代超过8个节点数的链表后，查询方式性能得到了很好的提升，从原来的是O(n)到O(logn)
13.拉链法导致的链表过深问题为什么不用二叉查找树代替,而选择红黑树?为什么不一直使用红黑树?
之所以选择红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构【链表】遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋,右旋、变色这些操作来保持平衡,引入红黑树就是为了查找数据快,解决链表查询深度的问题,我们知道红黑树属于平衡二叉树,所损耗的资源要比遍历线性链表要少,所以当长度大于8的时候,会使用红黑树,如果链表长度很短的话,根本不需要引入红黑树,引入反而会慢。
14.说说你对红黑树的见解?
1、每个节点非红即黑
2、根节点总是黑色的
3、如果节点是红色的,则它的子节点必须是黑色的(反之不一定)
4、每个叶子节点都是黑色的空节点(NIL节点）
5、从根节点到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度)
15.HashMap和HashTable有什么区别?
①、HashMap是线程不安全的,HashTable是线程安全的;
②、由于线程安全,所以HashTable的效率比不上HashMap;
③、HashMap最多只允许一条记录的键为null,允许多条记录的值为null,而HashTable不允许;
④、HashMap默认初始化数组的大小为16,HashTable为11,前者扩容时,扩大两倍,后者扩大两倍+1;
⑤、HashMap需要重新计算hash值,而HashTable直接使用对象的hashCode;
16.HashMap线程安全方面会出现什么问题？
在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。
在jdk1.8中，在多线程环境下，会发生数据覆盖的情况
17.HashMap的不安全体现在哪里？什么是安全的？
hashMap是线程不安全的，其主要体现：
1、在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。【头插法会产生反转链表，多线程会出现循环链表】
2.在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。
比如当前两个线程A和B，A线程判断当前位置为空就挂起了，此时线程B获取了当前下标，执行操作。但此时A线程恢复了，但是他并不知道B已将对此下标改变了。问题出现：线程A会把线程B插入的数据给覆盖，发生线程不安全。
安全的hash：ConcurrentHashMap /hashtable/collection.SynchronizedHashMap【利用collection集合工具通过把Map封装成一个SynchronizedHashMap锁对象】
18.HashMap是怎么解决哈希冲突的？
什么是哈希？
所有散列函数都有如下一个基本特性：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。
什么是哈希冲突？
当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，我们就把它叫做碰撞（哈希碰撞）。
HashMap的数据结构
在Java中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址容易，插入和删除困难；链表的特点是：寻址困难，但插入和删除容易；所以我们将数组和链表结合在一起，发挥两者各自的优势，使用一种叫做链地址法的方式可以解决哈希冲突：
引入红黑树进一步降低遍历的时间复杂度，使得遍历更快；
（二）ConcurrentHashMap
1.原理：使用了锁分段技术，将数据分段，每段竞争一把锁，不同数据段之间不存在锁竞争，，从而有效提高了高并发访问效率
2.HashMap 和 ConcurrentHashMap 的区别？
1.ConcurrentHashMap对整个桶数组进行了分割分段(Segment)，然后在每一个分段上都用lock锁进行保护，相对于HashTable的synchronized锁的粒度更精细了一些，并发性能更好，而HashMap没有锁机制，不是线程安全的。（JDK1.8之后ConcurrentHashMap启用了一种全新的方式实现,利用CAS算法。）
HashMap的键值对允许有null，但是ConCurrentHashMap都不允许。
3.ConcurrentHashMap 和 Hashtable 的区别？
ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。
实现机制：ConcurrentHashMap 1.7采用的锁分段技术，1.8采用volatile修饰保证数据的可见性，通过cas算法加Synchronized实现赋值，只对当前线程可见，锁粒度减小了；Hashtable采用 整段加锁的方式，锁粒度比较大，时间慢。
ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步，HashTable 考虑了同步的问题。但是 HashTable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的
4.ConcurrentHashMap 底层具体实现知道吗？实现原理是什么？
JDK1.7
首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。ConcurrentHashMap采用Segment + HashEntry的方式进行实现，结构如下：
一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。
1.该类包含两个静态内部类 HashEntry 和 Segment ；前者用来封装映射表的键值对，后者用来充当锁的角色；2.Segment 是一种可重入的锁 ReentrantLock，每个 Segment 守护一个HashEntry 数组里得元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 锁。
JDK1.8
在JDK1.8中，放弃了Segment臃肿的设计，取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现，synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。
结构如下：
附加源码，有需要的可以看看
插入元素过程（建议去看看源码）：
如果相应位置的Node还没有初始化，则调用CAS插入相应的数据；
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
如果相应位置的Node不为空，且当前该节点不处于移动状态，则对该节点加synchronized锁，如果该节点的hash不小于0，则遍历链表更新节点或插入新节点；
1.如果该节点是TreeBin类型的节点，说明是红黑树结构，则通过putTreeVal方法往红黑树中插入节点；如果binCount不为0，说明put操作对数据产生了影响，如果当前链表的个数达到8个，则通过treeifyBin方法转化为红黑树，如果oldVal不为空，说明是一次更新操作，没有对元素个数产生影响，则直接返回旧值；
2.如果插入的是一个新节点，则执行addCount()方法尝试更新元素个数baseCount；
5.Java中的另一个线程安全的与HashMap极其类似的类是什么?同样是线程安全,它与HashTable在线程同步上有什么不同?
ConcurrentHashMap类(是Java并发包java.util.concurrent中提供的一个线程安全且高效的HashMap实现)。
HashTable是使用synchronize关键字加锁的原理(就是对对象加锁);
而针对ConcurrentHashMap,在JDK1.7中采用分段锁的方式;JDK1.8中直接采用了CAS(无锁算法)+synchronized。
6.ConcurrentHashMap在JDK1.8中,为什么要使用内置锁synchronized来代替重入锁ReentrantLock?
①、粒度降低了;②、JVM开发团队没有放弃synchronized,而且基于JVM synchronized优化空间更大,更加自然。③、在大量的数据操作下,对于JVM的内存压力,基API 的ReentrantLock会开销更多的内存。
7.ConcurrentHashMap的并发度是什么?
程序运行时能够同时更新ConccurentHashMap且不产生锁竞争的最大线程数。默认为16,且可以在构造函数中设置。当用户设置并发度时,ConcurrentHashMap会使用大于等于该值的最小2幂指数作为实际并发度(假如用户设置并发度为17,实际并发度则为32)
8.HashMap和HashSet的区别
1.HashSet实现了Set接口，它不允许集合中有重复的值，当我们将对象存储在HashSet之前，要先确保对象重写equals()和hashCode()方法；这样才能比较对象的值是否相等，以确保set中没有储存相等的对象。如果我们没有重写这两个方法，将会使用这个方法的默认实现
2.HashMap实现了Map接口；HashSet仅仅存储对象，HashMap储存键值对
3.HashSet使用add()方法将元素放入set中，HashMap使用put()方法将元素放入map中
4.HashMap中使用键对象来计算hashcode值；HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false
5.HashMap比较快，因为它使用唯一的键来获取对象；HashSet较HashMap来说比较慢
9.Set集合
Set是不允许出现重复元素的集合类型。
●Set体系最常用的是HashSet、 TreeSet和LinkedHashSet三个集合类。HashSet从源码分析是使用HashMap来实现的，只是Value固定为一个静态对象，使用Key保证集合元素的唯一性，但它不保证集合元素的顺序。HashSet不是线程同步的!
●TreeSet也是如此，从源码分析是使用TreeMap来实现的，底层为树结构，在添加新元素到集合中时，按照某种比较规则将其插入合适的位置，保证插入后的集合仍然是有序的。
●LinkedHashSet继承自HashSet,具有HashSet的优点， 内部使用链表维护了元素插入顺序。
HashMap加载因子为什么是0.75
加载因子是表示Hsah表中元素的填满的程度。
加载因子越大,填满的元素越多,空间利用率越高，但冲突的机会加大了。
反之,加载因子越小,填满的元素越少,冲突的机会减小,但空间浪费多了。
冲突的机会越大,则查找的成本越高。反之,查找的成本越小。
因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷。
答案来源
这东西，不全是我自己写的，不会不理解的是网上找到的，由于来自很多不同的博主，所以没法一一贴出，感谢！我只是想自己复习用，见到错误多多提醒，见到相同处还望海涵