Java Collection 11 - LinkedHashSet

关于 java.util.LinkedHashSet<E> 的部分笔记。LinkedHashSet集合了散列表（hash table）和链表的特点于一身，解决了HashSet无法保证元素遍历顺序的问题，具有元素不重复，顺序固定的特点。本文演示代码段的执行环境基于JDK版本1.7。

概述

LinkedHashSet是基于散列表（hash table）和双向链表结构的Set实现类。和HashSet不同的是， LinkedHashSet保证了集合内元素的迭代顺序。该顺序是由双向链表来维护的，所以在集合元素遍历时，默认会按照元素被加入集合的顺序遍历并返回。
LinkedHashSet相对于HashSet保证了遍历顺序，同时也避免了随元素增多而导致的耗时增加（像TreeSet那样）。

LinkedHashSet提供了Set集合的所有方法，并且允许集合内存储null元素。和HashSet一样， LinkedHashSet对add(E e)、contains(Object o)、remove(Object o)的操作都是常量时间。在迭代集合时，
LinkedHashSet的耗时相对于HashSet好很多，因为LinkedHashSet需要的时间规模和其存储的元素总数成比例，而HashSet的时间规模和其存储的元素总数和其底层的HashMap的容量之和成比例。

LinkedHashSet也不是线程安全的，如果需要在多线程环境下使用LinkedHashSet，那么需要额外的处理来保证其线程安全。一种常用的方式是如下所示的处理方式：

1	Set s = Collections.synchronizedSet(new LinkedHashSet(...));

同样，LinkedHashSet集合返回的迭代器也含有快速失败检查，如果在遍历当前LinkedHashSet集合的过程中对集合做了结构化修改，那么就会抛出ConcurrentModificationException。同样的，LinkedHashSet集合也无法保证可以捕捉到所有的并发修改操作。

代码层面，LinkedHashSet只重新设计了构造方法，其他方法全部继承于HashSet。也就是说， LinkedHashSet的底层数据结构是一个LinkedHashMap，而HashSet的底层数据结构是一个HashMap，除此之外，LinkedHashSet在代码设计上和HashSet完全一致。

继承关系

// LinkedHashSet<E>
--java.lang.Object
  --java.util.AbstractCollection<E>
    --java.util.AbstractSet<E>
      --java.util.HashSet<E>
        --java.util.LinkedHashSet<E>

实现接口

类名	实现接口
LinkedHashSet<E>	Iterable<E>, Collection<E>, Set<E>, Serializable, Cloneable

LinkedHashSet

Constructor Summary

public LinkedHashSet(int initialCapacity, float loadFactor)

1
2
3

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

根据入参initialCapacity和加载因子loadFactor初始化一个LinkedHashSet集合。实际上是初始化了一个底层依赖的LinkedHashMap实例。

public LinkedHashSet(int initialCapacity)

1
2
3

public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}

根据入参initialCapacity初始化一个LinkedHashSet集合。实际上是初始化了一个底层依赖的LinkedHashMap实例，初始化LinkedHashMap的加载因子默认为0.75。

public LinkedHashSet()

1
2
3

public LinkedHashSet() {
    super(16, .75f, true);
}

初始化一个LinkedHashSet集合。初始化LinkedHashMap的加载因子默认为0.75，初始容量为16。

public LinkedHashSet(Collection<? extends E> c)

public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}

初始化一个LinkedHashSet集合，并将集合c中的元素全部加入到LinkedHashSet集合中。初始化LinkedHashMap的加载因子默认为0.75，初始容量为16。在初始化完成过程中通过AbstractCollection实现类的方法addAll(Collection<? extends E> c)完成元素加入操作。

部分方法

操作方法全部继承自HashSet，自身无方法实现和声明。

Mr.Muzi