转载

Java 集合框架综述

本篇力图梳理 Java 面试中经常碰到的集合框架部分内容。

概述

集合（Collection）框架的是设计一门语言肯定需要碰到的问题，重要的不是一门语言本身提供多少种数据结构可供调用，而是这一整套设计是否有其背后的逻辑所在。比如，如果两个集合类的应用场景几乎一样，那么从根源上说这就是设计上的一个失败，重要的不是工具箱里面有多少货，而是这套工具否五脏俱全，或者说是否有“一个核心的，统一的主题” [1] 。

从上述角度来看 Java 的集合框架，就不需要逐一记忆或背诵了，个人感觉可以从 ”如何高效查询数据 “和 ”如何高效更新数据“ 两个维度展开即可。

可以看出，Java 集合框架主要包含 Collection 和 Map 两类型的容器，其中 Collection 包括 List，Set和 Queue（Queue又可以基于 List 实现） — 对于List，用得多的为 ArrayList 和 LinkedList，前者底层使用数组实现，查询快，增删慢；而 LinkedList 基于链表，查询慢，增删快；对于Set，其特点是元素不重复，存取无序。 [2] 总结了 Collection 体系的特点：

而 Map 体系则是另一个故事，其保存的是键值对（key-value），key 需要唯一，而 value 可以重复。最常用的应用是 HashMap。

对于理解整个集合体系，我们可以从 [1] 中接口，具体类和算法三个维度逐层展开（如下），对此我的理解是 — Collection 和 Map 本质上是两种不同的存储方式（一种单值，一种双列存储），实现层面的展开就是基于这两种构造上的差异而来，这种差异取决于应用场景的不同（查询是否快速，增删是否快速等），同时，这类数据还需要抽取统一的应用算法，比如排序，遍历等等，这是对其共性的抽象。用这个思路作指导，剩下的多是应用层上的差异了。

一些常见问题

[3] , [4] 总结了 Java 集合面试的常见问题，这里择其精华摘要如下：

HashMap 的底层实现

JDK 1.8 对 HashMap 进行了调整，主要为对哈希冲突的解决方案的不同，JDK 1.8前使用”拉链法”解决（ “所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。” [3] ）。而1.8及之后，当链表长度大于阈值时，链表会转化红黑树以减少搜索时间。 [5] 给出了详细的对比分析。