---

Java核心 - 集合 相关的面经。

既可以临阵磨枪，也可以 作为 对知识结构树的补充。

• 集合和数组的区别

  • 数组的长度 是固定的；集合的长度 是可变的。

  • 数组 可以存储 基本类型数据 或 引用类型数据；集合 只能存储 引用类型数据。

  • 数组存储的元素 必须是 同一个数据类型；集合存储的元素 可以是 不同的数据类型。

Collection

Collection 接口。

List

• List 的特征：

  • 有序的；

  • 可以 对其中 每个元素的插入位置 进行精确地控制；

  • 可以通过索引 来 访问元素、遍历元素。

常用的实现类：ArrayList、LinkedList 、 Vector。

对List进行操作

遍历List

• 遍历方式：

  • for 循环。

    基于计数器。
    在集合外部维护一个计数器，然后依次读取每一个位置的元素，当读取到最后一个元素后停止。

  • 迭代器(Iterator)遍历。

    迭代器(Iterator) 是面向对象的一个设计模式，目的是 屏蔽 不同数据集合的特点，统一 遍历集合的接口。

    Java 在 Collections 中支持了 Iterator 模式。

  • foreach 循环。

    foreach 内部也是采用了 Iterator 的方式实现，使用时不需要显式声明 Iterator 或计数器。

    优点是代码简洁，不易出错；
    缺点是只能做简单的遍历，不能在遍历过程中操作数据集合，例如删除、替换。

Arraylist

Arraylist类。

实现了List接口。

• 底层数据结构：Object类型的数组。

• 并发编程：线程不安全。

LinkedList

LinkedList 类。

• LinkedList 继承了AbstractSequentialList类。

• LinkedList实现了：

  • Cloneable接口。

    可实现克隆。

  • Deque接口。

    可作为队列使用。

  • List接口。

    可进行列表的相关操作。

  • java.io.Serializable接口。

    可支持序列化，能通过序列化 进行传输。

  • Queue接口。

    可作为队列使用。

• 底层数据结构：链表。

  链表的优点：添加/删除元素操作 的效率很高。

  • 双向循环链表：查找效率较高。

    • 双向链表 比 单向链表 多了一个属性，用来指向 上一个节点的地址。

    • 双向链表 对比 单向链表，牺牲了 空间利用率，提高了 查找效率。

    • JDK 7 开始使用。

  • 单向链表：查找效率较低。

    • JDK 7 之前使用，JDK 7 开始弃用。

• 并发编程：线程不安全。

Vector

Vector类。

实现了List接口。

Vector 类实现了一个动态数组。

• Vector 和 ArrayList 很相似，但是两者是不同的：

  • Vector 是同步访问的（并发编程：线程安全）。

  • Vector 包含了许多传统的方法，这些方法不属于集合框架。

• 底层数据结构：Object类型的数组。

• 并发编程：线程安全。

Queue

队列，特征是

Set

Set 接口。

• Set的特征：

  • 元素不允许重复（唯一性）。

HashSet

HashSet 类。

HashSet的实现原理

HashSet 是基于 HashMap 实现的，HashSet 底层使用 HashMap 来保存所有元素。

HashSet的值 存放于其内部HashMap的 key 上，HashMap的 value 统一为PRESENT。

因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是 直接调用底层 HashMap 的相关方法来完成。

HashSet的特征

• HashSet的元素 不允许重复（唯一性）。

• HashSet的元素 可以为null。

HashSet是如何保证数据不可重复的

向 HashSet 中 添加元素时，遍历并判断元素 是否存在：先比较 hash 值（hash code）是否一致，再通过equles()方法 判断是否相同。

HashSet 中的 add() 方法 会调用 HashMap 的 put() 方法。

HashMap 的 key 是唯一的，由源码可以看出 HashSet 添加进去的值就是作为HashMap 的key，并且在 HashMap 中如果 K/V 相同时，会用新的 V 覆盖掉旧的 V，然后返回旧的 V。
以此保证 HashSet 中 元素的唯一性。

TreeSet

TreeSet类。

实现了Set接口。

• 底层数据结构：红黑树。

• 并发编程：线程不安全。

Map

Map接口。

Map 是一个 键值对 集合，存储 键(Key)和值(Value) 之间的映射。

• Map 的特征：

  • Key 无序，唯一；Value 不保证有序，允许重复。

  • 从 Map 中 检索元素时，只要给出键对象，就会返回对应的值对象。

Map接口的实现类，主要包括：HashTable，HashMap，IdentityHashMap，SortedMap，WeakHashMap

HashMap

HashMap与HashTable的区别

1. HashMap没有考虑同步，是线程不安全的；Hashtable使用了synchronized关键字，是线程安全的；
2. HashMap允许K/V都为null；Hashtable的K/V都不允许为null；
3. HashMap继承自AbstractMap类；而Hashtable继承自Dictionary类。

哈希冲突

哈希冲突（哈希碰撞）：多个不同的输入值，根据同一个散列函数 计算出相同的散列值 的现象。

---

📖参看

---

※参考和引用

1. ^ 维基百科，自由的百科全书

---

🔗外部链接

• Wikipedia's external link ltr-icon