[TOC]
ArrayList：
（1）JDK1.7和JDK1.8下ArrayList()底层数组的默认长度？
jdk1.7时使用ArrayList的无参构造，初始化后的长度是10，jdk1.8时使用无参构造，构造一个空数组，初始长度是0。
（2） 如何复制某个ArrayList到另一个ArrayList中去？
使用clone()方法
使用ArrayList构造方法
使用addAll方法
（3）arraylist怎么保证线程安全？
<1>、使用Vector
<2>、使用Collections.synchronizedList()
<3>、使用CopyOnWriteArrayList，涉及线程安全的部分，是通过写时复制的方式来实现。它内部有个volatile数组来保持数据。在“添加/修改/删除”数据时，会先获取互斥锁，再新建一个数组，并将更新后的数据拷贝到新建的数组中，最后再将该数组赋值给volatile数组，然后再释放互斥锁。
1.在做修改操作的时候加锁
2.每次修改都是将元素copy到一个新的数组中，并且将数组赋值到成员变量array中。
3.利用volatile关键字修饰成员变量array，这样就可以保证array的引用的可见性，每次修改之前都能够拿到最新的array引用。
迭代器的弱一致性:弱一致性是指返回迭代器后，其他线程对list的增删改对迭代器是不可见的。
（4）ArrayList频繁扩容导致添加性能急剧下降，如何处理？
使用ArrayList时，可以使用有参构造方法根据业务实际指定集合大小，以减少扩容的次数，提高写入效率。
（5）Java集合的快速失败机制 “fail-fast”和安全失败机制“fail-safe”？
“fail-fast”是java集合的一种错误检测机制，当多个线程对集合进行结构上的改变的操作时，有可能会产生fail-fast机制。fail-fast机制并不保证在不同步的修改下一定会抛出异常，它只是尽最大努力去抛出，所以这种机制一般仅用于检测bug。
原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变 modCount 的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测 modCount 变量是否为 expectedmodCount 值，是的话就返回遍历；否则抛出异常，终止遍历。
“fail-safe”采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有的集合内容，在拷贝的集合上进行遍历。
原理：基于拷贝内容的优点是避免了ConcurrentModificationException，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。
场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。
（6）扩容机制？
首先判断当前数组是不是空数组，如果是空数组，那么将数据由0扩容到需求长度minCapacity，此时有参构造生成的空数组扩容到1，无参构造扩容到10，因为在计算minCapacity时，如果是无参构造，取默认长度和需求长度 minCapacity 中比较大的值，返回10。如果是有参构造的空数组，minCapacity返回1。
如果不是空数组，创建一个长度为原来数组长度1.5倍的新数组，当新数组长度大于ArrayList数组定义的最大值后会调用hugeCapacity来进行判断。如果minCapacity已经大于Integer的最大值，也就是溢出为负数，那么抛出内存溢出异常。否则的话根据与MAX_ARRAY_SIZE的比较情况确定返回Integer的最大值还是MAX_ARRAY_SIZE。最后将旧数组的值用Arrays.copyOf（）方法拷贝到新数组。
（6）Iterator 和 ListIterator 有什么区别？
（1）Iterator可以在所有集合中使用，而ListIterator只能在List类型和其子类型中使用
（2）ListIterator和Iterator都有hasnext（）和next（）方法可以实现顺序向后遍历，但是ListIterator有hasPrevious（）方法和previous（）方法，可以实现逆向遍历，Iterator不可以。
（3）ListIterator有add（）方法，可以向List中添加对象，而Iterator不能。
（4）ListIterator可以定位当前索引的位置，next Index（）和previous Index（）可以实现，Iterator没用此功能。
（5）两个都可以实现删除操作，但是ListIterator可以实现对象的修改，set（）方法可以实现，Iterator不能修改。
（7）迭代器Iterator是什么？
Iterator是可以遍历集合的对象，为各种容器提供了公共的操作接口，隔离对容器的遍历操作和底层实现（解耦）。
迭代器是java23种设计模式之一，用于顺序访问集合对象的元素，无需知道集合对象的底层实现。
（8）Array和ArrayList的区别？
Array可以包含基本类型和对象类型，ArrayList只能包含对象类型。
Array大小是固定的，所以需要事前确定合适的空间大小。ArrayList的大小是动态变化的，在每次添加新的元素的时候都会检查内部数组空间是否足够。
ArrayList提供了更多的方法和特性，比如：all All（），removeAll（），iterator（）等。
对于基本数据类型，ArrayList使用自动装箱来减少编码工作量；而当处理固定大小的基本数据类型的时候，这种方式相对比较慢，这时候应该使用Array。
LinkedList:
（1）LinkedList 可以存储 null 值吗？元素可以重复吗？
LinkedList 底层是由双向链表实现的，并且在添加元素的时候，没有对元素进行值校验，所以可以存储 null 值，并且存储的元素是可以重复的。
（2）LinkedList和ArrayList的相同点与不同点?
相同点：
都是List集合的实现类，允许出现重复的元素，元素有序。
都是不同步的，线程都不安全。
不同点：
ArratList集合的底层采用的是Object数组结构，LinkedList底层采用的是双向链表结构。
查询时，ArrayList实现了RandomAccess接口，支持随机访问，时间复杂度是O（1），LinkedList需要进行遍历，时间复杂度是O（n）。
在插入元素时，ArrayList插入和删除元素时，原数组该插入或者删除位置已经它之后的元素都要进行移位操作，时间复杂度都是O（n），而且增加的时候可能还会引起扩容。LinkedList只要遍历找到该索引在的位置然后改变指针指向即可，如果是添加到头节点前或者链表末尾的位置，时间复杂度就是O（1），如果是指定了索引位置，时间复杂度就是O（n），总体来讲LinkedList增加和删除时性能比ArrayList好。
空间占用方面，ArrayList存在一定的空间浪费，因为每次扩容都是以前的1.5倍。但是LinkedList每个元素都要存放它的前驱节点的位置和后继节点的位置，所以对每个元素的存储要比ArrayList消耗更大的空间。
ArrayList适合多读，增删少的情况，Linked适合少读，增删多的情况。
（3）LinkedList版本前后变化？
LinkedList在1.6时底层是带头节点的双向循环列表，在1.7之后是不带头节点的双向链表。
Vector:
（1）ArrayList和Vector的区别？
相同点：
都实现了List接口。
底层数据结构都是数组。
不同点：
Verctor使用了Synchronized关键字来实现线程同步，所以线程是安全的，而ArrayList是线程不安全的。
在性能方面，因为Verctor很多方法使用了Synchronized关键字进行了加锁操作，所以性能不如ArrayList。
在扩容的时候，ArrayList扩容到原来的1.5倍，而Verctor扩容到原来的2倍。
Vector可以设置增长因子，而ArrayList不可以。
（2）为什么不推荐使用Verctor？
Verctor每个操作方法都加的有synchronized关键字，针对性能来说会比较大的影响，导致它性能很差。
HashMap:
（1）HashMap jdk1.7和1.8的区别？
底层数据结构不一样，jdk1.7是链表加数组，数组用来存储数据，链表用来防止hash冲突。1.8是链表加数组加红黑树，数组用来存储数据，链表和红黑树用来防止hash冲突。在链表长度大于等于8并且数组长度大于64时链表会变成红黑树（数组长度小于64会进行扩容）。避免单条链表过长而影响查询效率，提高查询效率。
1.7新增链表节点会采用头插法，1.8新增链表节点采用尾插法，所以1.8不容易形成环形链表。
1.7在扩容后会按原来的方法重新计算扩容后元素的位置，1.8在扩容后元素计算在新数组中的位置时按规律计算，扩容后的位置=原来的位置或者原数组的长度+原位置。节省了重新计算hash值的时间。
1.7是先扩容后插入的，1.8是先插入后扩容。
在计算hash值的时候，1.7经过了四次位运算和五次异或运算一共九次扰动，1.8经过了一次异或运算和一次位运算一共两次扰动。（两次扰动分别是key.hashCode()与key.hashCode右移16位进行异或，这样子做的目的是高16位不变，低16位与高16位进行异或操作，进而减少碰撞的发生，高低位都参与到Hash的运算。如果不进行hash扰动，因为hash有32位，直接对数组长度取余，起作用的只是hash值的几个低位）。
（2）为什么要增加红黑树？为什么不一直用红黑树？为什么到8转化为红黑树？到6转化为链表？
因为链表结构的查询效率是非常低的，他不像数组，能够通过索引开始找到想要的值，只能挨个遍历。当hash冲突很严重的时候，会严重影响查询的性能。当链化后链化特别严重，查询效率会退化到O（n），为了解决这个问题，jdk8中添加了红黑树来解决这个问题（时间复杂度O（logn））。
之所以不一直用红黑树，是为了权衡时间和空间，因为红黑树的节点占用空间是普通链表节点的两倍。
理想情况下随机hashCode算法下所有节点的分布频率会遵循泊松分布，链表长度达到8个元素的概率为0.00000006，几乎是不可能事件。
因为转化成树和生成树的时间不会太短，为了避免频繁的转化。
（3）为什么不用AVL树？为什么不用b树？为什么要用红黑树？
1、二叉排序树（二叉查找树）
1）若左子树不为空，则左子树上所有节点均小于根节点
2）若右子树不为空，则右子树上所有节点均大于根节点
3）左右子树也为二叉排序树
2、平衡二叉树（AVL树）：是一种二叉查找树，当且仅当两个子树的高度差不超过1时，这个树是二叉平衡树。
3、红黑树：是许多二叉查找树中的一种，它能保证在最坏的情况下，基本动态集合操作的时间为O（logn）。
每个节点非红即黑
根节点总是黑色的
如果节点是红色的，则它的子节点必须是黑色的（反之不一定）
每个叶子节点都是黑色的空节点（NIL节点）
从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）
【1】为什么不用二叉排序树？
二叉排序树在添加元素的时候极端情况下会出现线性结构。（因为二叉排序树左子树所有的节点的值均小于根节点的特点，如果添加的元素都比根节点小，会导致左子树线性增长，这样就失去了用树型结构替换链表的初衷，导致查询时间增长），遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于8的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。
【2】为什么不用二叉平衡树（AVL树）？
红黑树不追求完全平衡，他只要求部分达到平衡。红黑树是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数要比红黑树多。
在CurrentHashMap中是加锁了的，实际上是读写锁，如果写冲突就会等待，如果插入时间过程等待时间就更长，而红黑树相对于AVL树插入速度更快。
红黑树更加通用，它在添加，删除方面表现相对较好，但是AVL树的查找速度更快，代价是添加/删除速度较慢。
【3】为什么不用B/B+树？
B和B+树主要用于数据存储在磁盘上的场景，比如数据库索引就是用B+树实现的。这两种数据结构的特点就是树比较矮胖，每个结点存放一个磁盘大小的数据，这样一次可以把一个磁盘的数据读入内存，减少磁盘转动的耗时，提高效率。而红黑树多用于内存中排序，也就是内部排序。
（4）HashMap 的方法？
【1】put方法？
调用hash函数获取key对应的hash值，再计算其数组下标。
如果没有出现hash冲突，则直接放入数组，如果出现hash冲突，则以链表的方式放在链表后面。如果链表的长度已经大于等于8，数组长度小于64进行扩容，数组长度大于64就把链表转化为红黑树。
如果节点的key已经存在，则替换value就行。
如果集合中的键值对大于数组长度*负载因子，调用resize（）方法进行扩容。
【2】get方法？
通过hash&（数组.length-1）获取该key对应的数据节点的hash值。
判断首节点是否为空，为空则直接返回空。
再判断首节点的key和目标值是否相同，相同则直接返回（首节点不用区分链表还是红黑树）。
首节点的next为空，则直接返回空。
首节点是树形节点，则进入红黑树的取值流程，并返回结果。
进入链表的取值流程，链表结构进行顺序遍历查找操作，每次用 == 符号 和 equals( ) 方法来判断 key 是否相同，满足条件则直接返回该结点。链表遍历完都没有找到则返回空。
【3】resize方法（扩容）？
首先判断数组长度，如果大于0说明已经被初始化过，那么按当前数组长度的2倍进行扩容，阈值也变为原来的二倍。
若数组未被初始化过，且阈值大于0说明调用了HashMap的有参构造方法，那么就把数组大小设为阈值。
若数组未被初始化过，且阈值为0说明调用了HashMap的无参构造方法，那么就把数组的大小设为16，阈值设为16*负载因子。
接着需要判断如果不是第一次初始化，那么扩容之后1，要通过hash&旧数组中的位置重新计算键值对的位置，若为0索引位置不变，不为0则并把他们新的位置=旧位置+旧数组长度，如果节点是红黑树类型的化则需要进行红黑树的拆分。
