首页 > 代码库 > Java集合之LinkedHashSet源码分析
Java集合之LinkedHashSet源码分析
1.简介
我们知道Set不允许包含相同的元素，如果试图把两个相同元素加入同一个集合中，add方法返回false。根据源码实现中的注释我们可以知道LinkedHashSet是具有可预知迭代顺序的Set接口的哈希表和链接列表实现。此实现与HashSet的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可为插入顺序或是访问顺序。使用示例如下：
package com.test.collections;import java.util.Iterator;import java.util.LinkedHashSet;public class LinkedHashSetTest { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub LinkedHashSet<Integer> set = new LinkedHashSet<Integer>(); set.add(2); set.add(4); set.add(1); Iterator<Integer> iter = set.iterator(); System.out.println(set.isEmpty()); System.out.println(set.size()); System.out.println(set.contains(2)); System.out.println(set.containsAll(c)); System.out.println(set.remove(2)); set.clear(); }}2.继承结构
通过源代码可以看到LinkedHashSet继承了HashSet类，实现了Set、Cloneable以及Serializable接口，通过实现了Set接口我们知道不允许包含相同的元素。可是这个功能限制是如何实现的，我们来看下源代码就可以一目了然了。
3.源码解析
a:LinkedHashSet类中除了一个序列化ID没有其他的属性了，除了几个构造函数外没有其他的方法，其他的方法都是从HashSet直接继承而来，那就让我们从构造函数入手进行简单的分析。
public LinkedHashSet(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor, true); } public LinkedHashSet(int initialCapacity) { super(initialCapacity, .75f, true); } public LinkedHashSet() { super(16, .75f, true); } public LinkedHashSet(Collection<? extends E> c) { super(Math.max(2*c.size(), 11), .75f, true); addAll(c); }从代码中给出的四个构造函数我们可以看出功能各异。我们先来看看简单的构造函数，第一个构造函数制定了两个参数，第二个制定了一个参数，第三个是没有参数设定一个空的构造函数，第四个针对集合的初始化的构造函数。如果我们想要清楚构造函数到底做了什么事情，那么我们需要弄清楚super()方法做了什么事情，以及addAll做了什么事情。看源码：
HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor); } public boolean addAll(Collection<? extends E> c) { boolean modified = false; Iterator<? extends E> e = c.iterator(); while (e.hasNext()) { if (add(e.next())) modified = true; } return modified; }原来这两个方法就是我们构造函数出现的。通过第一个方法HashSet,中有一个Map，那这又是什么呢。原来HashSet中有一个熟悉private transient HashMap<E,Object> map;这下我们明白了原来Set的底层是采用一个Map实现的。这个很重要的东西，通过Map的相关方法调用来模仿Set的功能。Super方法做的事情就是创建了一个指定大小和加载因子的Map，addAll()方法就是遍历这个集合然后依次将他们放入我们的Map中去，从而实现了用一个集合直接构造含有值的Set。
回过头来我们看看上面的四个构造方法。第一个方法就是制定了初始容量和加载因子的Set,第二个构造函数就是制定了初始容量的Set,使用系统默认的加载因子0.75。第三个构造函数就是直接调用了一个空的构造函数，默认初始化一个容量为16，加载因子为0.75的Set,最后一个就是使用一个集合初始化Set.
b：iterator（）
public Iterator<E> iterator() { return map.keySet().iterator(); }iterator（），调用它就可以返回Set的迭代对象，底层是采用Map的keySet()方法实现的。
c:size()
public int size() { return map.size(); }直接返回了Map的容量就得到了Set的元素个数。
d:isEmpty()
public boolean isEmpty() { return map.isEmpty(); }也是调用map的集合是否为空方法。
e:contains()
public boolean contains(Object o) { return map.containsKey(o); }判断是否含有某一个元素。
f:add()
public boolean add(E e) { return map.put(e, PRESENT)==null; }
g：remove()和clear()
public boolean remove(Object o) { return map.remove(o)==PRESENT; } public void clear() { map.clear(); }删除元素的时候就是调用map的方法，clear也是一样。
4.其他（小结）
LinkedHashSet集合是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起 来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。LinkedHashSet在迭代访问Set中的全部元素时，性能比HashSet好，但是插入时性能稍微逊色于HashSet。Set的很多操作都是依赖Map来实现的，下次来学习下Map的源码相关。
Java集合之LinkedHashSet源码分析