Java基础底层-Collection和HashSet底层源码分析

亦凉 2022-12-27 08:46 197阅读 0赞

## 一、Java集合 ##

### 1. Java集合概述 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0h1YW5nMTE3ODM4Nzg0OA_size_16_color_FFFFFF_t_70]

从上面的集合框架图可以看到，Java 集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，称为单列集合，另一种是图（Map），存储键/值对映射，称为双列集合。  
Java集合大致可以分为Set、List、Queue和Map四种体系，其中List代表有序、可重复的集合；Set代表无序、不可重复的集合；而Map则代表具有映射关系的集合，Java 5 又增加了Queue体系集合，代表一种队列集合实现。

### 1. Java集合特点 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0h1YW5nMTE3ODM4Nzg0OA_size_16_color_FFFFFF_t_70 1]

## 二、Collection 底层实现 ##

### 1. 概述 ###

是单例集合的顶层接口，它表示一组对象，这些对象也称为Collection的元素  
JDK 不提供此接口的任何直接实现，它提供更具体的子接口（如Set，List）实现

### 2. 源码解析 ###

#### 2.1 继承关系 ####

public interface Collection<E> extends Iterable<E> {

iterable 接口是java集合大家庭的最顶级的接口之一了，实现此接口使集合对象可以通过迭代器遍历自身元素(迭代器在JDK1.8版本增加了可分割迭代器，更有利于并发处理)

*  iterable 源码拓展

// 返回一个内部元素为T类型的迭代器（JDK1.5只有这个接口）
    // iterator()方法，是接口中的核心方法,主要是获取迭代器，获取到的iterator有next(),hasNext(),remove()等方法
    Iterator<T> iterator();
    
    // 遍历内部元素，action意思为动作，指可以对每个元素进行操作（JDK1.8添加）
    default void forEach(Consumer<? super T> action) { }
    
    // 创建并返回一个可分割迭代器（JDK1.8添加），分割的迭代器主要是提供可以并行遍历元素的迭代器，可以适应现在cpu多核的能力，加快速度。
    default Spliterator<T> spliterator() { 
    	return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }

#### 2.2 成员方法 ####

集合操作的常用方法，方便其他继承Collection的实现类使用

int size();	 /*返回集合的大小 */
    boolean isEmpty(); 	/*判断集合是否为空 */
    Iterator<E> iterator();		/*返回集合中元素的迭代器 */
    boolean add(E e); 	/*添加元素 */
    boolean addAll(Collection<? extends E> c); 	/*添加集合C中所有元素 */
    boolean remove(Object o); 	/*删除元素 */
    boolean removeAll(Collection<?> c); 	/*删除集合C中包含的元素 */
    void clear(); 	/*清除集合里的所有元素，集合长度变为0 */
    boolean equals(Object o); 	/*判断与指定元素是否相等 */
    int hashCode(); 	/*返回集合的哈希码值 */

*  Jdk1.8后新增的方法

default boolean removeIf(Predicate<? super E> filter)   /*移除此集合中满足给定条件的所有元素 */
    default Spliterator<E> spliterator()  /*继承自Iterable，内部迭代器还可转换为可分割迭代器Spliterator */
    default Stream<E> stream()    /*返回一个顺序流 */
    default Stream<E> parallelStream()  /*返回一个并行流 */

#### 2.3 Stream流概述 ####

官方API定义： Stream 流将要处理的元素集合看作一种流， 流在管道中传输， 并且可以在管道的节点上进行处理， 比如筛选、排序、聚合等。元素流在管道中经过中间操作（intermediate operation）的处理，最后由终端操作 (terminal operation) 得到前面处理的结果。Stream流可以说是对集合（Collection）对象功能的增强。

总结来说：流 (Stream) 是数据渠道，用于操作数据源（集合、数组等）所生成的元素序列

// 流中间操作 : 多个中间操作可以连接起来形成一个 流水线，除非流水线上触发终止操作，否则中间操作不会执行任何的处理.而在终止操作时一次性全部处理.
    filter(Predicate p)		//接收 Lambda ， 从流中排除某些元素。
    distinct()		//筛选，通过流所生成元素的 hashCode() 和 equals() 去除重复元素
    map(Function f)		//接收一个函数作为参数，该函数会被应用到每个元素上，并将其映射成一个新的元素
    sorted()		//产生一个新流，其中按自然顺序排序
    sorted(Comparator comp)		//产生一个新流，其中按比较器顺序排序
    //流终止操作 ： 终端操作会从流的流水线生成结果。其结果可以是任何不是流的值.
    allMatch(Predicate p)		//检查是否匹配所有元素
    anyMatch( (Predicate p) )	//检查是否至少匹配一个元素
    findFirst()		//返回第一个元素
    findAny()		//返回当前流中的任意元素
    count()		//返回流中元素总数

## 三、HashSet 底层原理实现 ##

### 1. 概述 ###

Set的出现，是为了维持一种元素唯一的集合。HashSet ，是在HashMap的基础之上保持这一特性，并且拥有自身的特点

*  特点：  
    不保证元素顺序； 非同步，如果需要同步需要通过代码来保证； 集合元素可以为null

### 2. 源码解析 ###

#### 2.1 继承关系 ####

public class HashSet<E>  extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable

实现了Serializable接口，表明支持序列化  
实现了Cloneable接口，表明支持克隆，可以调用超类的clone()方法进行浅拷贝（需注明什么是深拷贝什么是浅拷贝）  
继承了AbstractSet抽象类,实现了Set接口;AbstractSet 是一个抽象类，它继承于AbstractCollection。AbstractCollection实现了Set中的绝大部分函数，为Set的实现类提供了便利

> 深拷贝对引用数据类型的成员变量的对象图中所有的对象都开辟了内存空间,修改对象不会影响原来的对象  
> 而浅拷贝只是传递地址指向，新的对象并没有对引用数据类型创建内存空间,修改对象会影响原来的对象

#### 2.2 构造函数 ####

/* 无参构造函数：实例化了HashMap*/
    public HashSet() { 
    	map = new HashMap<>();
    }
    
    /*带集合的构造函数： 初始化了HashMap*/
    public HashSet(Collection<? extends E> c) { 
    	map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    	addAll(c);
    }
    /*初始化hashSet*/
    public HashSet(int initialCapacity, float loadFactor) { 
    	map = new HashMap<>(initialCapacity, loadFactor);
    }
    
    public HashSet(int initialCapacity) { 
    	map = new HashMap<>(initialCapacity);
    }
    /*使用了LinkedHashMap实现*/
    HashSet(int initialCapacity, float loadFactor, boolean dummy) { 
    	map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

#### 2.3 成员变量 ####

// 序列化ID
    static final long serialVersionUID = -5024744406713321676L;
    // 底层使用了HashMap存储数据
    private transient HashMap<E,Object> map;    /*此处需要注意map的key为泛型，value为Object；*/
    // 用来填充底层数据结构HashMap中的value,因为HashSet只用key存储数据
    private static final Object PRESENT = new Object();

#### 2.4 常用方法 ####

##### 2.4.1 添加新元素 #####

//底层仍然利用了HashMap键进行了元素的添加。
    //在HashMap的put()方法中，该方法的返回值是对应HashMap中键值对中的值，而值总是PRESENT,
    //该PRESENT一直都是private static final Object PRESENT = new Object();
    //PRESENT只是初始化了，并不能改变，所以PRESENT的值一直为null。
    //所以只要插入成功了，put（）方法返回的值总是null。
    public boolean add(E e) { 
    	return map.put(e, PRESENT)==null;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0h1YW5nMTE3ODM4Nzg0OA_size_16_color_FFFFFF_t_70 2]

*  注具体HashMap源码解析请点 [Java基础底层-HashMap底层源码分析][Java_-HashMap].

##### 2.4.2 删除元素 #####

//该方法底层实现了仍然使用了map的remove（）方法。
    //map的remove（）方法的返回的是被删除键对应的值。（在HashSet的底层HashMap中的所有
    //键值对的值都是PRESENT）
    public boolean remove(Object o) { 
        return map.remove(o)==PRESENT;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0h1YW5nMTE3ODM4Nzg0OA_size_16_color_FFFFFF_t_70 3]

##### 2.4.3 克隆方法 #####

//底层仍然使用了Object的clone（）方法，得到的Object对象，并把它强制转化为HashSet<E>,
    //然后把它的底层的HashMap也克隆一份（调用的HashMap的clone（）方法），并把它赋值给newSet，最后返回newSet即可
    public Object clone() { 
    	try { 
        	HashSet<E> newSet = (HashSet<E>) super.clone();
        	newSet.map = (HashMap<E, Object>) map.clone();
        	return newSet;
    	} catch (CloneNotSupportedException e) { 
        	throw new InternalError(e);
    	}
    }

### 3. HashSet一致性如何维护 ###

元素唯一性由hashCode()和equals()保证的，二者缺一不可

if (e.hash == hash && ((k = e.key) == key || key.equals(k))){ 
    ......//e.hash调用了hashCode()方法获得了e元素的hash值

注：HashSet所谓的唯一 ，不是真正的唯一，而是取决于程序员如何定义HashCode和equals方法，当然其中还会经历 ==（对象比较是比较的地址） 的判断

### 4. HashMap与HashSet的区别 ###

看过 HashSet 源码的话就应该知道：HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0h1YW5nMTE3ODM4Nzg0OA_size_16_color_FFFFFF_t_70 4]

> 关于HashSet较HashMap来说比较慢是一个很有争议性的描述。HashSet的所有操作基本都是调用HashMap实现的，性能上本身是没有什么可比较的，理应是没有区别的。  
> 其实HashMap和HashSet唯一的区别是他们的**使用场景不同导致了他们的哈希值计算不同**  
> **HashMap**的Key键一般是String，Integer或者基本的数据类型；  
> 而**HashSet**的Key键一般是自定义对象；  
> 基本数据类型或者是String/Integer对象计算Hash码的数组比自定义对象的哈希码计算速度快的多；且自定义对象的Hash值计算方法和equal方法都得重写。  
> **总结**：区别就在于HashMap的键主要是String/Integer，他们计算Hash码的速度大于HashSet存储的自定义对象的Hash码计算速度；也就是说如果HashMap的键和存储在HashSet中的键是相同的对象，那么两者的性能是没有区别的。

### 5. 常见面试问题 ###

#### 5.1 如何保证同步 ####

*  将HashSet或HashMap转换为线程安全，使用Collections.synchronizedSet或Collections.synchronizedMap方法；
 *  使用Collections.newSetFromMap(new ConcurrentHashMap<Integer, Boolean>())或使用java.util.concurrent包下的ConcurrentHashMap；
 *  仍然使用HashSet或HashMap，使用时手动进行加锁或同步；// 注意加锁粒度，尽可能保证性能

#### 5.2 无序性和不可重复性的意思 ####

*  什么是无序性？无序性不等于随机性 ，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ，而是根据数据的哈希值决定的。
 *  什么是不可重复性？不可重复性是指添加的元素按照 equals()判断时 ，返回 false，需要同时重写 equals()方法和 HashCode()方法。

#### 5.3 HashSet如何检查重复性 （一致性如何维护） ####

我们使用Set集合都是需要去掉重复元素的, 如果在存储的时候逐个equals()比较, 效率较低,哈希算法提高了去重复的效率, 降低了使用equals()方法的次数。  
当HashSet调用add()方法存储对象的时候, 先调用对象的hashCode()方法得到一个哈希值, 然后在集合中查找是否有哈希值相同的对象。  
如果没有哈希值相同的对象就直接存入集合。  
如果有哈希值相同的对象, 就和哈希值相同的对象逐个进行equals()比较,比较结果为false就存入, true则不存

#### 5.4 HashSet，TreeSet和LinkedHashSet三者的异同 ####

*  HashSet 是 Set 接口的主要实现类 ，HashSet 的底层是 HashMap，线程不安全的，可以存储 null 值；
 *  LinkedHashSet 是 HashSet 的子类，能够按照添加的顺序遍历；
 *  TreeSet 底层使用红黑树，能够按照添加元素的顺序进行遍历，排序的方式有自然排序和定制排序。

#### 5.5 过滤重复的自定义对象 ####

*  代码demo
 *  注： 对自定义对象使用HashSet去重时需要重写hashCode方法和equal方法；

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0h1YW5nMTE3ODM4Nzg0OA_size_16_color_FFFFFF_t_70]: /images/20221120/9b7880544a1c403ea1ed64bb177b02eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0h1YW5nMTE3ODM4Nzg0OA_size_16_color_FFFFFF_t_70 1]: /images/20221120/85313070369c4e80bdfdf76ac507ee9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0h1YW5nMTE3ODM4Nzg0OA_size_16_color_FFFFFF_t_70 2]: /images/20221120/d41c3d4d963244c1b9675836eba6255c.png
[Java_-HashMap]: https://blog.csdn.net/Huang1178387848/article/details/110484045
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0h1YW5nMTE3ODM4Nzg0OA_size_16_color_FFFFFF_t_70 3]: /images/20221120/1bfe561210d9415ea09236bcc36db0f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0h1YW5nMTE3ODM4Nzg0OA_size_16_color_FFFFFF_t_70 4]: /images/20221120/48f4a05be21f442fae5402dfeb0a47b5.png