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完全一致。

继承关系

1
2
3
4
5
6
// 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)

1
2
3
4
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,自身无方法实现和声明。

涉及基础知识点

  1. NIL

参考文献

  1. NIL




------------- End of this article, thanks! -------------


  版权声明:本文由Nathan R. Lee创作和发表,采用署名(BY)-非商业性使用(NC)-相同方式共享(SA)国际许可协议进行许可,转载请注明作者及出处。
  本文作者为 Nathan R. Lee
  本文标题为 Java Collection 11 - LinkedHashSet
  本文链接为 https://marcuseddie.github.io/2018/java-Collection-LinkedHashSet.html