java面试题 --- 集合

1. java 集合你了解吗？

java 集合最顶层接口是 Collection 和 Map；
Collection 有三个核心接口，分别是 List，Set，Queue；
List 是有序可重复的，它的主要实现类有 ArrayList、LinkedList 和 Vector；
ArrayList 是数组实现的，查询快增删慢线程不安全；
LinkedList 是链表实现的，查询慢增删快线程不安全；
Vector 相当于线程安全的 ArrayList；
Set 是无序不重复的，它的主要实现类有 HashSet、TreeSet 和 LinkedHashSet，它们分别是用对应的 Map 实现的，比如 HashSet 就是用 HashMap实现的，注意 TreeSet 是有序的；
Queue 是队列，主要有阻塞队列 BlockingQueue。Map 的主要实现类有 HashMap、LinkedHashMap、HashTable 和 TreeMap。
2. 什么是集合的快速失败机制？

集合内部会维护一个 modCount 变量，遍历的时候，会判断 modCount 变量的值是否等于期望值，不等就会报并发修改异常。
3. 用 for 循环遍历集合的同时移除元素可以吗？

不可以，会报并发修改异常。要边遍历边移除元素，只能用迭代器。
4. HashMap 底层是用什么实现的？

jdk1.7 的 HashMap 采用拉链法，数组加链表实现的；
jdk1.8 的 HashMap 采用了数组加链表加红黑树实现。
5. HashMap (jdk1.8) 怎么初始化的？

如果调用的是无参构造，不会立即初始化数组，要等 put 元素时才会初始化一个长度为 16 的数组；
如果调用的是带参构造，就会将数组长度初始化为最接近传入参数的 2 的 n 次幂，比如传入的是 6，那就初始化为 8。
6. HashMap (jdk1.8) 怎么计算索引的？

首先会对 key 的 hashCode 值的高十六位与低十六位做一个异或 (^) 运算，这样做是为了让 key 的整个 hashCode 都能参与接下来的计算，减少 hash 碰撞的概率，且异或运算得到 0 和 1 的概率一样，不会影响数据分布；
接着拿到刚才计算出来的值，和数组长度减一之后的值进行与 (&) 运算，就得到了索引。
7. HashMap (jdk1.8) 计算索引时为什么用与 (&) 操作？

正常情况计算索引应该是 hashCode 值对数组长度取模，即求余，但是取模运算的效率不高，所以改用与 (&) 操作。
8. HashMap (jdk1.8) 数组长度为什么是 2 的 n 次幂？

只有当数组长度为 2 的 n 次幂时，hashCode 值与 (&) 数组长度减一的计算结果才会和 hashCode 值对数组长度取模的计算结果才会一致；
同时 2 的 n 次幂减一的二进制是若干个 1，和奇数计算最后结果是奇数，和偶数计算的结果是偶数，如果最后一位是 0，那么不管和奇数还是偶数进行与 (&) 计算的结果都是偶数，不能保证散列分布均匀。
9. HashMap (jdk1.8) 计算拿到索引后直接把元素存在那个位置吗？

拿到索引后，先判断索引位置是否有元素，如果没有，直接把元素放到索引位置；
如果有，判断 key 是否一样，如果一样，新值覆盖旧值；
如果不一样，就在此处生成链表，元素存到链表中。
10. HashMap (jdk1.8) 什么时候生成红黑树？

当链表长度达到 8，且数组长度达到 64 的时候，就会生成红黑树；
当红黑树节点少于 6 个的时候，又会将红黑树转回链表。
11. HashMap (jdk1.8) 数组什么时候扩容？

扩容因子是 0.75，当数组中元素个数达到数组长度的 3/4 时就扩容，扩容为原来的两倍。
12. HashMap (jdk1.8) 数组扩容后数据怎么转移？

如果原先数组那位位置的元素是单个元素或者红黑树，那就放到 hash 与 (&) 新数组长度减一的位置；
如果是链表，那就判断 hash 与 (&) 旧数组长度是否为 0，如果是，就放在原来索引处，如果不是，就放在原来索引加上旧数组长度处。
13. 既然 HashMap (jdk1.8) 不安全，那并发情况下用什么？

用 ConcurrentHashMap。
14. ConcurrentHashMap 的底层你知道吗？

jdk1.7 的 ConcurrentHashMap 底层是 Segment 数组，Segment 数组存放的元素是 HashEntry 数组，HashEntry 数组存放的元素是链表。每次锁住一个 Segment，保证安全性的同时提高了并发性，这就是锁分段机制；
jdk1.8 的 ConcurrentHashMap 的底层是数组加链表加红黑树，用 Synchronized 和 CAS 来保证线程安全。
15. ArrayList 的 elementData 为什么用 transient 修饰？

加上 transient 就不会直接序列化整个数组，序列化的时候只序列化数组中存的元素，而不是整个数组，既加快了序列化速度也减小了序列化后文件的大小。
16. List 和 Set 如何选用？

List 支持随机快速访问，支持用索引获取元素，Set 不支持。所以如果增删操作比较多，适合用 Set，查询操作比较多，适合用 List；
List 是有序可重复的，而 Set 是无序不重复的。所以可以根据存入的元素是否需要顺序、是否可以重复来决定用什么。
17. HashSet 如何保证元素不重复？

HashSet 底层是 HashMap，HashSet 存储的元素就存放在 HashMap 的 key 中，HashMap 的 key 是否相同是先比较 hashCode 值再用 equals 方法比较。
18. 为什么 String、Integer 适合作为 HashMap 的 key？

因为 String 和 Integer 都是 final 类型的，能够保证 hash 值的不可更改性；
String 和 Integer 已经重写了 hashCode 方法和 equals 方法，可以保证计算的准确性。