乐趣区

关于java:精选常见Java集合面试题

jiezi

起源：码农田小齐

明天这篇文章是单纯的从面试的角度登程，以答复面试题为线索，再把整个 Java 汇合框架温习一遍，心愿能帮忙大家拿下面试。

先上图：

当面试官问问题时，我会先把问题归类，锁定这个知识点在我的常识体系中的地位，而后延展开来想这一块有哪些重点内容，面试官问这个是想考查什么、接下来还想问什么。

这样本人的思路不会凌乱，还能预测面试官下一个问题，或者，也能够 疏导面试官问出你精心筹备的问题，这场面试实质上就是你在主导、你在 show off 本人扎实的基础知识和良好的沟通交流能力。

其实我在 LRU 那篇文章里就说到过这个观点，而后就有读者问我，说会不会被面试官看穿？

答：看进去了又怎么？面试官阅人有数，是有可能看进去的，然而也只会莞尔一笑，感觉这个同学很用心。

精心筹备面试既是对面试官集体工夫的尊重，也是表明了你对这家公司的趣味，这样的员工不是每家公司都想要的吗？

好了，进入正题，明天就来解决这 9 大面试题。

1. ArrayList vs LinkedList

这题的问法很多，比方

  • 最简略的就间接问 ArrayList 和 LinkedList 的区别和分割；
  • 或者问你什么时候要抉择 ArrayList，什么时候抉择 LinkedList；
  • 或者在你们聊到某个场景、或者在算法题中，面试官问你如何抉择。

万变不离其宗。

首先论断是：

  • 绝大多数的情景下都偏差于用 ArrayList，除非你有明确的要应用 LinkedList 的理由。
  • 如果你不确定用哪个，就用 ArrayList。

两者在 实现 层面的区别是：

  • ArrayList 是用一个可扩容的数组来实现的 (re-sizing array)；
  • LinkedList 是用 doubly-linked list 来实现的。

而 数组和链表之间最大的区别 就是数组是能够随机拜访的（random access）。

这个特点造成了在数组里能够通过下标用 O(1) 的工夫拿到任何地位的数，而链表则做不到，只能从头开始一一遍历。

两者在 增删改查 操作上的区别：

  • 在「改查」这两个性能上，因为数组可能随机拜访，所以 ArrayList 的效率高；
  • 在「增删」这两个性能上，如果不思考找到这个元素的工夫，数组因为物理上的连续性，当要增删元素时，在尾部还好，然而其余中央就会导致后续元素都要挪动，所以效率较低；而链表则能够轻松的断开和下一个元素的连贯，直接插入新元素或者移除旧元素。

然而呢，实际上你不能不思考找到元素的工夫啊。。。尽管 LinkedList 能够 O(1) 的工夫插入和删除元素，能够你得先找到中央啊！

不是有个例子么，修理这个整机只须要 1 美元，然而找到这个整机须要 9999 美元。咱们平时修 bug 也是如此，重点是找到 root cause 的过程。

而且如果是在尾部操作，数据量大时 ArrayList 会更快的。

事实上，LinkedList 是很多性能问题的 bug，那么为什么呢？

因为 ListNode 在物理内存里的不间断，导致它用了很多小的内存片段，这会影响很多过程的性能以及 cache-locality（局部性）；所以即使是实践上的工夫复杂度和 ArrayList 一样时，也会导致实际上比 ArrayList 慢很多。

2. ArrayList vs Vector

答：

  1. Vector 是线程平安的，而 ArrayList 是线程不平安的；
  2. 扩容时扩多少的区别，文邹邹的说法就是 data growth methods不同，
  • Vector 默认是扩充至 2 倍；
  • ArrayList 默认是扩充至 1.5 倍。

回顾下这张图，

Vector 和 ArrayList 一样，也是继承自 java.util.AbstractList，底层也是用数组来实现的。

然而当初曾经被弃用了，因为它是线程平安的。任何益处都是有代价的，线程平安的代价就是效率低，在某些零碎里很容易成为瓶颈，所以当初大家不再在数据结构的层面加 synchronized，而是把这个工作转移给咱们程序员。

那怎么晓得扩容扩多少的呢？

看源码：

这是 Vecotr 的扩容实现，因为通常并不定义 capacityIncrement，所以默认状况下它是扩容两倍。

VS

这是 ArrayList 的扩容实现，算术右移操作是把这个数的二进制往右挪动一位，最右边补符号位，然而因为容量没有正数，所以还是补 0.

那右移一位的成果就是除以 2，那么定义的新容量就是原容量的 1.5 倍。

3. ArrayDeque vs LinkedList

首先要分明它们之间的关系：

答：

  1. ArrayDeque 是一个可扩容的数组，LinkedList 是链表构造；
  2. ArrayDeque 里不能够存 null 值，然而 LinkedList 能够；
  3. ArrayDeque 在操作头尾端的增删操作时更高效，然而 LinkedList 只有在当要移除两头某个元素且曾经找到了这个元素后的移除才是 O(1) 的；
  4. ArrayDeque 在内存应用方面更高效。
  5. 所以，只有不是必须要存 null 值，就抉择 ArrayDeque 吧！

那如果是一个很 资深 的面试官问你，什么状况下你要抉择用 LinkedList 呢？

答：Java 6 以前。因为 ArrayDeque 在 Java 6 之后才有的。为了版本兼容的问题，理论工作中咱们不得不做一些斗争。

4. HashSet 实现原理

答：

HashSet 是基于 HashMap 来实现的，底层采纳 Hashmap 的 key 来贮存元素，次要特点是无序的，基本操作都是 O(1) 的工夫复杂度，很快。所以它的实现原理能够用 HashMap 的来解释。

5. HashMap 实现原理

答：

  • 在 JDK1.6/1.7，数组 + 链表；
  • 在 JDK 1.8，数组 + 红黑树。

具体说来，

对于 HashMap 中的每个 key，首先通过 hash function 计算出一个 哈希值 ，这个哈希值就代表了在桶里的编号，而“桶”实际上是通过 数组 来实现的，然而桶有可能比数组大呀，所以把这个 哈希值 模上 数组的长度 失去它在数组的 index，就这样把它放在了数组里。

这是现实状况下的 HashMap，但事实中，不同的元素可能会算出雷同的哈希值，这就是 哈希碰撞，即多个 key 对应了同一个桶。

为了解决哈希碰撞呢，Java 采纳的是 Separate chaining 的解决形式，就是在碰撞的中央加个链子，也就是上文说的 链表或者红黑树。

6. HashMap vs HashTable

答：

  1. Hashtable 是线程平安的，HashMap 并非线程平安；
  2. HashMap 容许 key 中有 null 值，Hashtable 是不容许的。这样的益处就是能够给一个默认值。

其实 HashMap 与 Hashtable 的关系，就像 ArrayList 与 Vector，以及 StringBuilder 与 StringBuffer。

Hashtable 是晚期 JDK 提供的接口，HashMap 是新版的。这些新版的改良都是因为 Java 5.0 之后容许数据结构不思考线程平安的问题，因为理论工作中咱们发现没有必要在数据结构的层面上上锁，加锁和放锁在零碎中是有开销的，外部锁有时候会成为程序的瓶颈。

所以 HashMap, ArrayList, StringBuilder 不再思考线程平安的问题，性能晋升了很多。

7. 为什么改 equals() 肯定要改 hashCode()？

答：

首先基于一个假如：任何两个 object 的 hashCode 都是不同的。也就是 hash function 是无效的。

那么在这个条件下，有两个 object 是相等的，那如果不重写 hashCode()，算进去的哈希值都不一样，就会去到不同的 buckets 了，就迷失在茫茫人海中了，再也无奈相认，就和 equals() 条件矛盾了，证毕。

  1. hashCode() 决定了 key 放在这个桶里的编号，也就是在数组里的 index；
  2. equals() 是用来比拟两个 object 是否雷同的

8. Collection vs Collections

这俩看似相近，实则相差十万八千里，就如同 坏蛋 和坏蛋卡 的区别似的。

Collection 是

  • 汇合接口；
  • 是 Java 汇合框架 的 root interface；
  • 落脚点是一个 interface；
  • 蕴含了以下这些接口和类：

想零碎学习 Collection，能够在公众号内回复「汇合」，获取爆款文章。

而 Collections 是工具类 utility class，是汇合的操作类，提供了一些静态方法供咱们应用，比方：

  • addAll()
  • binarySearch()
  • sort()
  • shuffle()
  • reverse()
退出移动版