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 方法，可以保证计算的准确性。