最常考的Java后台面试题（二）Java集合

总览概述

常见的集合 ArrayList

底层实现常用方法ArrayList和Vector的区别？ArrayList和Array的区别？ArrayList和linkedList的区别？ HashMap

底层实现常用方法HashMap的负载因子为什么是0.75？HashMap的寻址方法？HashMap的扩容方法？为什么HashMap线程不安全？ ConcurrentHashMap

原理 其他

迭代器Iterator？快速失败(fail-fast)和安全失败(fail-safe)？

参考内容：Java面试小抄

（一）Java基础（二）Java集合（三）JVM（四）Java并发（五）MySQL（六）计算机网络（七）操作系统 概述 常见的集合

这里的集合指的是Java自带的集合框架，其将常用的工具做成类以供实例化使用。
这些工具都基于两个根接口实现：Collection和Map。而Collection又派生出三个子接口：List、Set、Queue。

ArrayList的底层是通过数组实现的。因此添加元素是O(1)，而插入或删除元素则是O(n)。同时因为是数组，所以可以快速访问。但会有空间浪费，ArrayList一般最后会空一部分。
ArrayList一开始以一个容量初始化，然后按照数组方式添加元素；当元素个数多于容量时，ArrayList会自动进行扩容。扩容就是生成一个现有大小的1.5倍的新数组，再将数据复制过去。

添加：arraylist.add(“abc”);访问：arraylist.get(i);修改：arraylist.set(i, “abc”);删除：arraylist.remove(i);计算大小：arraylist.size();清空：arraylist.clear();排序：Collections.sort(arraylist);
此时的Collections不同于Collection，Collections是一个工具类，Collection是一个接口。 ArrayList和Vector的区别？

Vector也是一个动态数组，但相比于ArrayList有几点不同：

线程安全：Vector有synchronized关键字，所以是时刻同步的；多线程时用Vector；扩容一倍：Vector扩容是直接扩一倍，不是ArrayList的扩0.5倍；包含一些不属于集合框架的传统方法。 ArrayList和Array的区别？

Array就是数组，大小不可变，元素可以是基本类型和对象类型，但是ArrayList的元素只能是对象类型。Arrays类可以操作数组，包括排序.sort()方法、填充方法.fill(int[] a, int val)等等。

两者核心的区别是linkedList是由双向循环链表的数据结构构造的。
所以linkedList可以O(1)的插入或删除，但是无法随机访问，同时每个链表节点由于多保存了前驱和后继，所以一般来说占用会更大（但是没有ArrayList的空表尾冗余）。

JDK 1.7：数组 + 链表JDK 1.8：数组 + 链表 + 红黑树

数组是将key通过哈希码找到数组坐标，然后填入，这样就可以以O(1)的效率增加或删除。但发生冲突时，HashMap解决冲突的方式是采用拉链法，即将冲突的节点连成一个链表。这样在查找到某个坐标但是有多个数据时，就按照链表的连接顺序一个一个查找。
在JDK1.8中，HashMap做了优化：但链表长度大于8且数组长度超过64时，将链表转换为红黑树。

树是一种数据结构，一个节点有孩子节点，孩子节点有孩子的孩子节点。二叉树是最多只有两个孩子的树。有序二叉树是判断val值来决定插入位置的二叉树。但是如果按照1-2-3-4-…的顺序插入，有序二叉树会成为一个只有右子树的类似与链表的结构，这样无法保证查找效率为O(logn)。平衡二叉树是任意左右子树高度差不大于1的有序二叉树。这样可以保证查找效率，但是使得增加和删除节点需要大量改动结构，而由于平衡的要求，会经常改动。红黑树是保留了查找效率但是减少删改消耗的有序二叉树。红黑树的平衡是左右子树的高度差小于一倍的关系。

红黑树设定了很多规则，主要是取消了平衡二叉树的高度差不大于1的要求，然后设定了每个节点的颜色只能为红色或者黑色：根节点必须为黑色，null算作叶节点且必须为黑色，红节点的子节点必须为黑色，任意一点到两个叶子节点的路径中黑色节点数量必须一致。
上述规则中，最关键的就是路径中黑色节点数量一致。最坏的情况下，红黑相间，这样两路径的高度也只是二倍关系。所以红黑树放宽了平衡二叉树的平衡条件，插入或删除节点时需要大改的次数更少。而将全部的红色节点去掉，我们就得到了一个黑色的平衡二叉树，这棵二叉树的查找效率为O(logn)，这里的n是黑色节点的数量；若再加上红色节点，最坏的情况下，查找效率为2O(logn)，所以总体时间复杂度依然为对数级。即，减少了大改次数却依然保证了查找效率。故HashMap在链表节点数量大于8时会将其改为红黑树而不是平衡二叉树。

添加：hashmap.put(1, "abc");访问：hashmap.get(1);删除：hashmap.remove(1);计算大小：hashmap.size();是否为空：hashmap.isEmpty();是否包含指定键：hashmap.containsKey(1);是否包含指定值：hashmap.containsValue("abc"); HashMap的负载因子为什么是0.75？

HashMap的构造函数中包含：

int threshold;          // 临界点、阈值、容纳键对的最大值
final float loadFactor; // 负载因子

table的默认初始长度是16，而threshold = length * loadFactor，负载因子的默认值为0.75，所以threshold的值就为12，代表HashMap中的数组如果有12个以上被使用了，HashMap的数组就要扩容。
为什么使用0.75，这是时间和空间的一个平衡。太大就会增加时间成本，大小就会增加空间成本；同时，由于长度为2的幂次方，所以四分之三可以直接计算为整数，更加方便。

取key的hashCode()的值：key.hashCode();根据hashCode进行高低位运算得到hash值hash = (h = key.hashCode()) ^ (h >>> 16);
>>>表示无符号右移16位，一共有32位，所以就是相当于把hashcode的高位值取出来和低位值进行异或计算；根据hash值用位运算取模获得数组下标(n - 1) & hash;
上图中的n等于16，也就是HashMap的默认初始容量；而n-1用二进制表示就是1111，对先前计算的hash值进行异或运算，相当于只取后四位，也就确保了最终值在数组范围内，也就是做完了取模操作。

为什么不直接用hashcode而是用高低位运算得到hash？
因为一开始HashMap的容量为16，只有四位，很小，所以如果hashcode值很大，如2¹⁰ 、2²⁰ 、2³⁰ 这些，这几个数在前四位都是0，所以直接取模会产生冲突。为了应对这种情况，应尽量使得高位的值也参与到计算数组下标的过程中以减少冲突。所以采用这种方法。
为什么不直接取模？
因为位运算算得更快。

当容量超过负载因子和数组大小定义的容量之后，就要进行扩容；扩容直接扩一倍，构建一个新的容量为原来二倍的数组；查看元素最高位的hash值，若为0，则保留原位置；若为1，则新位置等于原位置加上旧容量。

对第三行进行解释：假设初始数组大小为16，一个元素是5，另一个是21，则根据取模操作二者位置一样；扩容之后，由于现在的容量是32，所以5位置不变，21更新到5+16的位置上。在二进制看来，两者的区别就是最高位是0还是1，所以无需重新计算哈希值。

JDK1.8 相较于 JDK1.7的改进有：

用判最高位0还是1的方法重新计算索引，无需重新计算哈希值；链表采用尾插法取代头插法。 为什么HashMap线程不安全？

多线程下扩容死循环；
因为链表采用头插法，所以扩容时重新安排链表会和原先的链表逆序；而如果两线程同时经历扩容，则可能导致线程一已经链表逆序完了。线程二保存的还是旧链表的指针，这样线程二继续移动链表时就会产生循环。JDK1.8通过将头插法改为尾插法解决了这个问题。多线程下put可能导致元素的丢失；
当多线程同时put且索引位置一致时，可能导致前一个key被后一个key覆盖，这样就丢失了元素；单线程时二者会连到链表上。多线程下put和get并发可能get一个空值。
当put一个元素导致扩容时，put的位置可能会更新，而get旧位置找不到put的元素，就会错误get一个空值。 ConcurrentHashMap 原理

之前说过，HashMap多线程不安全，为解决这个问题，最简单的办法，就是加锁！

HashTable：好一把大锁

给整个表加一个大锁，只有有人在用，就谁都不许进。
如果不想使用HashTable还想要多线程安全，可以使用Collections.synchronizedMap方法，对HashMap加同步锁，其实也就是相当于把HashMap变成了HashTable。

JDK1.7之前的ConcurrentHashMap：好几把中锁

设置一个Segment锁，其实就是将原先的一个数组再进行划分，每个小组安排一个锁。当有人在使用这小组内的位置的时候，就加锁不让其他人使用小组位置；但是别人可以使用除了这个小组位置的其他位置。相比于HashTable，增加了并发时的灵活性。但由于每次找到一个位置需要两次哈希，降低了效率。

JDK1.8之后的ConcurrentHashMap：每人一把小锁

在每个数组的入口按一个小锁，这样只需要一次哈希就可以确定数组下标，同时由于锁的粒度变得更小，并发灵活性更高。

迭代器是一种用于迭代访问集合的方法。假设arraylist是ArrayList实例化后的一个包含String的对象，则迭代器的使用方式为：

Iterator it = arraylist.iterator();
while(it.hasNext()) {
    System.out.println(it.next());
}

Iterator和ListIterator有什么区别？

类型：Iterator可以迭代包含List、Set、Map在内的所有集合类型，ListIterator只能遍历List类型；方向：Iterator只能向前遍历，ListIterator可以向前和向后遍历。 快速失败(fail-fast)和安全失败(fail-safe)？

fail-fast:
在迭代器遍历集合框架中的对象时，若另一个线程修改了对象内容，则会抛出Concurrent Modification Exception并终止遍历。
java.util包下的集合类都是快速失败的。fail-safe:
迭代器遍历时，先将原有集合内容拷贝并复制，迭代器在复制后的集合上遍历，因此不会抛出同时修改异常。
java.util.concurrent包下的容器都是安全失败的。