来聊聊 ArrayList和LinkedList区别
- ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
- 对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
- 对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
说说Vector和ArrayList 区别：
- Vector的方法都是同步的(Synchronized),是线程安全的(thread-safe)，而ArrayList的方法不是，由于线程的同步必然要影响性能，因此,ArrayList的性能比Vector好。
- 当Vector或ArrayList中的元素超过它的初始大小时,Vector会将它的容量翻倍,而ArrayList只增加50%的大小，这样,ArrayList就有利于节约内存空间。
- 我们也可以用Collections.synchronizedList 来生成一个线程安全的List
说说HashSet和TreeSet的区别：
- TreeSet 是二叉树实现的,Treeset中的数据是自动排好序的，不允许放入null值。
- HashSet 是哈希表实现的,HashSet中的数据是无序的，可以放入null，但只能放入一个null，两者中的值都不能重复，就如数据库中唯一约束。
- HashSet要求放入的对象必须实现HashCode()方法，放入的对象，是以hashcode码作为标识的，而具有相同内容的 String对象，hashcode是一样，所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例 。
说说HashMap和HashTable的区别：
- HashMap是非线程安全的，Hashtable是线程安全的，所以Hashtable重量级一些，因为使用了synchronized关键字来保证线程安全。
- HashMap允许key和value都为null，而Hashtable都不能为null。
- HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常
上面的是我们集合的基础，下面来看看一些进阶面试题
能不能深度的总结下ArrayList
- 默认的无参构造的数组大小为10
- ArrayList用for循环遍历比iterator迭代器遍历快
- 一起来总结下它的扩容过程，第一步判断是否需要扩容（就是通过计算当前我数组的长度加上我要添加到数组的长度的和minCapacity 去和当前容量去比较，如果需要的话，那就进行第一次扩容，第一次扩容是的容量大小是原来的1.5倍，扩容之后再把扩容之后的值和前面的那个minCapacity和比较 如果还小的话，就进行第二次扩容，把容量扩成minCapacity，如果minCapacity大于最大容量，则就扩容为最大容量21亿左右
为什么ArrayList的elementData是用transient修饰的
- ArrayList实现了Serializable接口，这意味着ArrayList是可以被序列化的，用transient修饰elementData意味着我不希望elementData数组被序列化
- 序列化ArrayList的时候，ArrayList里面的elementData未必是满的，比方说elementData有10的大小，但是我只用了其中的3个，那么是否有必要序列化整个elementData呢？显然没有这个必要，因此ArrayList中重写了writeObject方法。
你重写过 hashcode 和 equals 么，为什么重写 equals 时必须重写 hashCode 方法？
- 如果两个对象相等，则 hashcode 一定也是相同的
- 两个对象相等,对两个对象分别调用 equals 方法都返回 true
- 两个对象有相同的 hashcode 值，它们也不一定是相等的
- 因此，equals 方法被覆盖过，则 hashCode 方法也必须被覆盖
- hashCode() 的默认行为是对堆上的对象产生独特值。如果没有重写 hashCode()，则该 class 的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）
聊聊HashSet 如何检查重复
当你把对象加入HashSet时，HashSet 会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。
说说HashMap 的底层实现
JDK1.8 之前
JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。
JDK1.8之后
相比于之前的版本， JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。
那么你可以聊聊红黑树吗
首先我们知道红黑数是一个二叉查找树， 它有以下的特点
- 左子树上所有结点的值均小于或等于它的根结点的值。
- 右子树上所有结点的值均大于或等于它的根结点的值。
- 左、右子树也分别为二叉排序树。
但是一般的二叉树在极端情况下，可能变成线性查找了，那么就失去它的查找特性意义了，而红黑树是一个自平衡树，它最重要的是增加了下面3个规则来确保它的自平衡
- 每个叶子节点都是黑色的空节点（NIL节点）。
- 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这里小六六说下，红黑树还是很复杂的，所以一般往下不会问了，如果变态点，就还会问问自平衡的过程，这边我就不一一解释了，大家自行去找。它的变色，它的左旋，右旋，哈哈确实掉头发。。
HashMap 的长度为什么是 2 的幂次方
- 首先考虑奇数行不行，在计算hash的时候，确定落在数组的位置的时候，计算方法是(n - 1) & hash ，奇数n-1为偶数，偶数2进制的结尾都是0，经过&运算末尾都是0，会增加hash冲突，并且有一半的空间不会有数据
- 为啥要是2的幂，不能是2的倍数么，比如6，10？
- hashmap 结构是数组，每个数组里面的结构是node（链表或红黑树），正常情况下，如果你想放数据到不同的位置，肯定会想到取余数确定放在那个数据里， 计算公式： hash % n，这个是十进制计算。在计算机中， (n - 1) & hash，当n为2次幂时，会满足一个公式：(n - 1) & hash = hash % n，计算更加高效。
- 只有是2的幂数的数字经过n-1之后，二进制肯定是 ...11111111 这样的格式，这种格式计算的位置的时候（&），完全是由产生的hash值类决定，而不受n-1(组数长度的二进制) 影响。你可能会想， 受影响不是更好么，又计算了一下，类似于扰动函数，hash冲突可能更低了，这里要考虑到扩容了，2的幂次方*2，在二进制中比如4和8，代表2的2次方和3次方，他们的2进制结构相 似,比如 4和8 00000100 0000 1000 只是高位向前移了一位，这样扩容的时候，只需要判断高位hash,移动到之前位置的倍数就可以了，免去了重新计算位置的运算。
HashMap 的扩容伐值为什么是0.75
- 当负载因子是1.0的时候，也就意味着，只有当数组的8个值（这个图表示了8个）全部填充了，才会发生扩容。这就带来了很大的问题，因为Hash冲突时避免不了的。当负载因子是1.0的时候，意味着会出现大量的Hash的冲突，底层的红黑树变得异常复杂。对于查询效率极其不利。这种情况就是牺牲了时间来保证空间的利用率。
- 负载因子是0.5的时候，这也就意味着，当数组中的元素达到了一半就开始扩容，既然填充的元素少了，Hash冲突也会减少，那么底层的链表长度或者是红黑树的高度就会降低。查询效率就会增加。
- 基本上为什么是0.75的答案也就出来了，这是时间和空间的权衡。
HashMap树化的条件
这个小六六说下，如果没看过源码，肯定印象没有那么深刻
- 第一个肯定是发生了hash碰撞
- 并且链表的长度大于8就会树化，小于6之后会退化
- 还有一个条件就是整个hashmap的容量要大于64
JDK1.7版本的hashmap死循环问题知道吗
小六六也大致说下，就是1.7在多线程的情况下，扩容的时候，假设2个线程同时扩容导致的我们链表的相互引用，导致的死循环，也就是我们所说的链表尾插，其实这也不算bug,因为官方明确说了 hashmap不应该在多线程的环境下使用，具体大家自行百度
说说hashmap的put操作
- 第一步当然是先计算key的hash值(有过处理的 (h = key.hashCode()) ^ (h >>> 16))
- 第二步调用putval方法，然后判断是否容器中全部为空，如果是的话，就把容器的容量扩容。
- 第三步，把最大容量和hash值求&值（i = (n - 1) & hash），判断这个数组下标是否有数据，如果没有就把它放进去。还要判断key的equals方法，看是否需要覆盖。
- 第四步，如果有，说明发生了碰撞，那么继续遍历判断链表的长度是否大于8，如果大于8，就继续把当前链表变成红黑树结构。
- 第五步，如果没有到8，那么就直接把数据存在链表的尾部
- 第六步，最后将容器的容量+1。
说说hashmap的resize的操作
- 如果到达最大容量，那么返回当前的桶，并不再进行扩容操作，否则的话扩容为原来的两倍，返回扩容后的桶；
- 根据扩容后的桶，修改其他的成员变量的属性值；
- 根据新的容量创建新的扩建后的桶，并更新桶的引用；
- 如果原来的桶里面有元素就需要进行元素的转移；
- 在进行元素转移的时候需要考虑到元素碰撞和转红黑树操作；
- 在扩容的过程中，按次从原来的桶中取出链表头节点，并对该链表上的所有元素重新计算hash值进行分配；
- 在发生碰撞的时候，将新加入的元素添加到末尾；
- 在元素复制的时候需要同时对低位和高位进行操作。
聊聊ConcurrentHashMap 1.7和1.8的比较
ConcurrentHashMap是conccurrent家族中的一个类，由于它可以高效地支持并发操作，以及被广泛使用，经典的开源框架Spring的底层数据结构就是使用ConcurrentHashMap实现的。与同是线程安全的老大哥HashTable相比，它已经更胜一筹，因此它的锁更加细化，而不是像HashTable一样为几乎每个方法都添加了synchronized锁，这样的锁无疑会影响到性能。
1.7和1.8实现线程安全的思想也已经完全变了其中抛弃了原有的Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。它沿用了与它同时期的HashMap版本的思想，底层依然由“数组”+链表+红黑树的方式思想。
- 不采用segment而采用node，锁住node来实现减小锁粒度。
- 设计了MOVED状态 当resize的中过程中 线程2还在put数据，线程2会帮助resize。
- 使用3个CAS操作来确保node的一些操作的原子性，这种方式代替了锁。
- sizeCtl的不同值来代表不同含义，起到了控制的作用。
聊聊ConcurrentHashMap的sizeCtl
- 负数代表正在进行初始化或扩容操作
- -1代表正在初始化
- -N 表示有N-1个线程正在进行扩容操作
- 正数或0代表hash表还没有被初始化，这个数值表示初始化或下一次进行扩容的大小，这一点类似于扩容阈值的概念。还后面可以看到，它的值始终是当前ConcurrentHashMap容量的0.75倍，这与loadfactor是对应的。
说说ConcurrentHashMap的put方法
- 第一步，一进去肯定判断key value是否为null 如果为null 抛出异常
- 第二步，当添加一对键值对的时候，首先会去判断保存这些键值对的数组是不是初始化了，如果没有就初始化数组。
- 第三步， 通过计算hash值来确定放在数组的哪个位置如果这个位置为空则直接添加（CAS的加锁方式），如果不为空的话，则取出这个节点来
- 第四步，如果取出来的节点的hash值是MOVED(-1)的话，则表示当前正在对这个数组进行扩容，复制到新的数组，则当前线程也去帮助复制
- 第五步，如果这个节点，不为空，也不在扩容，则通过synchronized来加锁，进行添加操作
- 第六步，如果是链表的话，则遍历整个链表，直到取出来的节点的key来个要放的key进行比较，如果key相等，并且key的hash值也相等的话，则说明是同一个key，则覆盖掉value，否则的话则添加到链表的末尾
- 第七步，如果是树的话，则调用putTreeVal方法把这个元素添加到树中去
- 第八步，最后在添加完成之后，会判断在该节点处共有多少个节点（注意是添加前的个数），如果达到8个以上了的话，则调用treeifyBin方法来尝试将处的链表转为树，或者扩容数
结尾
这个就是一些基础的面试题，当然还是很多不一定那么全，但是如果把这些都能回答出来，其实Java基础这块也算是蛮扎实了。
