【面试八股|Java集合】Java集合常考面试题详解
这里根据个人说话口吻等编写java集合常见面试题用于记录复习，后续会持续更新补充。
JAVA集合
该部分内容有几大考察要点：1.底层源码 2.不同集合之间的对比特点
1.底层源码如果是宽泛的问（如ArrayList的底层原理是什么），需要分别从底层数据结构，核心方法讲解
2.不同集合对比，主要牢记不同集合的特点，主要考虑线程安全，底层数据结构等，再组织语言回答。
JAVA提供的常见集合（JAVA集合概述）
java提供了两大类集合框架-第一类是Collection 属于单列集合，第二类为Map 属于双列集合。Collection有三个子接口，分别为Set，List，Queue。像我们常用的HashSet，TreeSet，ArrayList，PriorityQueue等等都属于该框架。Map为双列集合，比较常见的实现类有HashMap，TreeMap，ConcurrentHashMap等。
ArrayList的底层原理
ArrayList的实现原理
ArrayList的底层数据结构是由一个动态数组实现的。这里具体说明一下add方法的底层原理。
第一，会先确保当前数组长度size+1后足够存下一个元素，如果不够将进行扩容。在扩容逻辑中，会调用grow方法将容量扩容到原来的1.5倍。
第二，在确保新增数据有地方存储之后，会将新元素添加到位于size的位置上。
最后，在添加成功会返回布尔值。
ArrayList的成员变量
DEFAULT_CAPACITY= 10; 默认初始的容量**(CAPACITY)
EMPTY_ELEMENTDATA= {}; 用于空实例的共享空数组实例
DEFAULTCAPACITY_EMPTY_ELEMENTDATA= {};用于默认大小的空实例的共享空数组实例
Object[] elementData; 存储元素的数组缓冲区
int size; ArrayList的大小（它包含的元素数量）
ArrayList的构造方法
第一种无参构造器：会将elementData赋值为空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，此时数组容量为0，只有在第一次调用add方法才会懒加载首次扩容为10
第二种有参构造器：如果传入参数initialCapactity=0，则赋值为空数组。如果传入参数initialCapactity>0则创建长度为initialCapactity的数组。如果传入参数initialCapactity<0，则抛出异常illegalArgumentException
第三种为传入集合构造器，会将集合转为数组，赋值给elementData，数组容量为集合的size。
HashMap的底层原理
HashMap的实现原理
第一，hashmap底层使用hash表数据结构，即数组和链表或红黑树。
第二，在增添元素时，计算key的哈希值确定元素下标。如果出现hash值相同则有两种情况：一是key相同，那就覆盖原始值。二是key不同，出现哈希冲突，那就将当前key-value存入链表或红黑树。
第三，在获取元素时，也计算key的hash值找到对应下标，再进一步判断key是否相同，从而找到对应值。
HashMap的成员变量
1.默认初始容量
2.默认加载因子
3.存储元素的hashmap.node<k,v> []table
4.包含元素数量size
HashMap的put方法原理
第一，先判断键值对table是否为null或空，如果是则通过resize（）扩容
第二，根据key计算hash值确定元素下标，如果对应下标为空，则直接添加元素。
第三，对应下标不为空，先判断首个元素是否key相同，如果相同则覆盖value
第四，如果key不相同，则判断当前table[i]是否为红黑树，如果是红黑树则插入键值对。
第五，如果不是红黑树，则遍历table[i]，在尾部插入元素。当然在遍历过程如果发现key相同，则直接覆盖value
第六，在插入元素后检测是否需要转换红黑树（链表长度大于8并且数组长度大于64）或扩容（扩容阈值=数组容量*扩容因子）。
HashMap的扩容机制
第一，在添加元素或初始化时可能会调用resize方法进行扩容。在添加元素时达到了扩容阈值=0.75*数组长度会发生扩容。
第二，第一次添加元素初始化数组长度为16，之后每次扩容都是扩容到原来元素的二倍。
第三，具体扩容逻辑，在扩容时会创建一个新数组，并把老数组元素挪动到新数组中。这里分出三种情况：
1.没有hash冲突的节点，直接使用 e.hash & (newCap - 1) 在新数组中的元素下标
2.有哈希冲突，如果是链表则判断e.hash&oldCap是否为0。如果是，新数组元素下标与旧数组元素下标相同；如果不是，新数组元素下标=旧数组元素下标+旧数组容量
3.如果是红黑树，则走红黑树逻辑的添加。
HashMap的寻址算法
第一，通过两次hash计算hash值。先计算key的hashcode，再右移16位与原本的hashcode异或运算，来使hash值更均匀减少hash冲突
第二，使用hash&（n-1）代替取模，得到数组得到索引。也因此数组长度必须是2的n次幂。
为什么HashMap的数组长度一定是2的次幂？
第一，计算索引，用位运算替代取模运算，更高效
第二，在扩容时，通过hash&oldcap计算元素是否留在原来位置，更高效。
HashMap在1.7情况下的多线程死循环
第一，在jdk1.7时的数据结构为数组+链表
第二，在jdk1.7时使用头插法，在进行扩容数据迁移时可能导致死循环。
第三，举例，现有两个线程，线程一读取到当前hashmap，并准备扩容时，线程二介入。线程二读取hashmap直接扩容，将原本链表的AB顺序扩容后变成了BA，线程二结束。线程一再执行就会发生死循环，导致BAB。
第四，jdk8对扩容算法做出调整，采用了尾插法避免死循环。
ArrayList与Vector的区别
1.ArrayList与Vector都是List的实现类，ArrayList被主要使用，而Vector更古老
2.两底层都使用object[],ArrayList线程不安全，Vector线程安全
ArrayList与LinkedList的区别
1.线程是否安全：两个都不线程安全
2.数据结构：ArrayList底层采用数组，LinkedList底层采用双向链表（jdk1.7取消循环）
3.操作数据：ArrayList支持按照下标查询，LinkedList不支持下标查询。查找未知索引两个都需要遍历，时间复杂度都是O（n）。增删在头尾节点为O（1）,其它情况ArrayLits需要挪动数组，LinkedLIst需要遍历，都是O（n）。
4.内存空间占用，ArrayList底层是数组，内存连续，节省空间。LinkedList，还需要存两个指针，更占用内存。
HashMap与HashSet的区别
1.底层数据结构，HashSet底层使用HashMap进行存储。知识HashSet的value默认Object对象
2.HashSet实现的是Set接口，存储对象；HashMap实现Map接口，存储键值对。
HashMap与HashTable的区别
1.底层数据结构：HashMap是数组+链表+红黑树。HashTable是数组+链表
2.线程是否安全：HashMap不安全，HashTable安全（synchronized），粒度粗效率低下。
3.扩容机制：HashMap是容量翻倍，HashTable是翻倍+1
4.是否可为null：HashMap能为null，HashTable不能为null
5.hash算法：HashMap是二次hash，HashTable是hashCode（）
简单介绍ConcurrentHashMap
数据结构：在1.8之前使用分段数组+链表（segment默认16+hashentry），1.8时采用数据+链表+红黑树
线程安全：1.8之前对segment数组加锁，继承reentrantlock，粒度粗。1.8时对Node加锁，采用CAS+synchronzied
并发度：1.8之前并发度为segment的个数，为16。1.8后为Node个数，并非度高。