搞懂 HashSet & LinkedHashSet 源码以及集合常见面试题目-白红宇

搞懂 HashSet & LinkedHashSet 源码以及集合常见面试题目

阅读量：305 次

发布时间：2019-03-03

本文共 3200 字，大约阅读时间需要 10 分钟。

HashSet & LinkedHashSet 源码分析及集合面试题总结

Set 集合概述

Set 是 Java 中的一种集合，它的特点是允许存储唯一的元素，不允许重复存储，并且通常不关心元素的顺序。Set 的主要实现类包括 HashSet、TreeSet 和 LinkedHashSet。这些集合的内部实现都依赖于 HashMap、TreeMap 和 LinkedHashMap 的存储结构。

HashSet 和 LinkedHashSet 的实现分别依赖于 HashMap 和 LinkedHashMap 的存储结构，而 TreeSet 则依赖于 TreeMap。从继承关系来看，HashSet 和 LinkedHashSet 继承自 AbstractSet，TreeSet 继承自 AbstractSet 和 NavigableSet。

HashSet 源码分析

HashSet 的实现非常简单，其内部实际上使用了 HashMap 来存储元素。HashSet 的构造方法调用了 HashMap 的相应构造方法来初始化存储结构。以下是 HashSet 的关键构造方法和实现：

构造方法:
- HashSet()：初始化一个默认容量和默认加载因子的 HashSet，内部调用 HashMap 的空构造方法。
- HashSet(int initialCapacity)：初始化一个指定容量的 HashSet，内部调用 HashMap 的指定容量构造方法。
- HashSet(int initialCapacity, float loadFactor)：初始化一个指定容量和加载因子的 HashSet，内部调用 HashMap 的相应构造方法。
- HashSet(Collection c)：初始化一个容量根据集合 c 的大小确定的 HashSet，内部调用 HashMap 的相应构造方法，并将集合 c 中的元素全部添加到 HashSet 中。

存储结构:HashSet 的底层存储结构由 HashMap 实现，通过 map.put(e, PRESENT) 来存储元素。PRESENT 是一个静态的 Object 对象，用于表示元素的值。

方法实现:HashSet 实现了 Set 接口中的所有方法，包括 add、remove、contains、isEmpty、size 等方法。这些方法通过调用 HashMap 的相应方法来实现。

迭代器:HashSet 的迭代器由 HashMap 的 KeyIterator 实现，通过调用 next() 方法可以得到当前元素。

LinkedHashSet 源码分析

LinkedHashSet 的实现类似于 HashSet，但它的底层存储结构依赖于 LinkedHashMap。LinkedHashSet 维护了一个双向链表来记录元素的插入顺序。以下是 LinkedHashSet 的关键构造方法和实现：

构造方法:
- LinkedHashSet()：初始化一个默认容量和默认加载因子的 LinkedHashSet，内部调用 HashMap 的空构造方法。
- LinkedHashSet(int initialCapacity)：初始化一个指定容量的 LinkedHashSet，内部调用 LinkedHashMap 的相应构造方法。
- LinkedHashSet(int initialCapacity, float loadFactor)：初始化一个指定容量和加载因子的 LinkedHashSet，内部调用 LinkedHashMap 的相应构造方法。
- LinkedHashSet(Collection c)：初始化一个容量根据集合 c 的大小确定的 LinkedHashSet，内部调用 LinkedHashMap 的相应构造方法，并将集合 c 中的元素全部添加到 LinkedHashSet 中。

存储结构:LinkedHashSet 的底层存储结构由 LinkedHashMap 实现，通过 map.put(e, PRESENT) 来存储元素。

方法实现:LinkedHashSet 实现了 Set 接口中的所有方法，包括 add、remove、contains、isEmpty、size 等方法。这些方法通过调用 LinkedHashMap 的相应方法来实现。

迭代器:LinkedHashSet 的迭代器由 LinkedHashMap 的 EntryIterator 实现，通过调用 next() 方法可以得到当前元素及其对应的值。

集合面试题总结

ArrayList 与 LinkedList 的区别:

ArrayList 的存储结构是数组，查询效率高，增删效率一般。

LinkedList 的存储结构是双向链表，查询效率较低，增删效率高。

ArrayList 不允许存储 null，LinkedList允许存储 null。

ArrayList 与 Vector 的区别:

ArrayList 的默认容量为 10，扩容时增加 1.5 倍的容量，而 Vector 每次扩容增加 2 倍的容量。

ArrayList 和 Vector 都是动态数组，但 Vector 是线程安全的，所有方法都带有 synchronized 关键字。

ArrayList 和 LinkedList 可通过 Collections.synchronizedList 方法生成线程安全的集合。

HashMap 的工作原理及 JDK 1.8 的优化:

HashMap 在 JDK 1.8 中引入了红黑树来替代单链表，提高了哈希表的查询效率。

HashMap 的扩容机制在 JDK 1.8 中进行了优化，使用位运算和异或运算减少了扩容时的计算量。

HashMap 与 Hashtable 的区别:

HashMap 是线程不安全的，而 Hashtable 是线程安全的。

HashMap 允许 key 和 value 为 null，但只允许一个 null key 存放在哈希表中。

HashMap 的默认容量是 2^4，而 Hashtable 的默认容量是 11。

HashMap 与 LinkedHashMap 的区别:

LinkedHashMap 是基于 LinkedHashMap 实现的，内部维护了一个双向链表，记录元素的访问顺序。

LinkedHashMap 在元素插入时可以指定是否记录访问顺序。

HashSet 如何检查重复:

HashSet 内部使用 HashMap 存储元素，通过元素的 hashCode 方法和 equals 方法来判断是否存在重复元素。

快速失败规则:

快速失败规则用于检测集合的结构是否发生了修改，防止并发修改时的 ConcurrentModificationException。

迭代器在遍历集合时，通过 modCount 变量和 expectedModCount 变量来检测集合的结构是否发生了修改。

集合的迭代与删除:

集合在使用 for 循环或高级 for 循环遍历时不允许使用 remove 方法，否则会抛出 ConcurrentModificationException。

Iterator 可以安全删除当前元素，因为 Iterator 的 remove 方法会修改 modCount 和 expectedModCount，避免 ConcurrentModificationException。

总结

本文分析了 HashSet 和 LinkedHashSet 的源码实现，揭示了 Set 与 Map 之间的关系，并总结了集合面试中的常见问题。这些知识点在面试中非常重要，理解了集合的实现原理和各个集合之间的区别，可以帮助开发高效率的代码。

转载地址：http://enzq.baihongyu.com/

你可能感兴趣的文章