Java中的LinkedHashSet

LinkedHashSet继承自HashSet，保留了HashSet的特性，在此基础上保证了元素插入的有序性

特点

1. 元素不重复：根据hash值和元素内容判断，插入的元素是否已存在
2. 元素是有序的：元素虽然是根据hash值随机放置，但是每个节点中都维护了前后指针，保证了元素插入顺序
3. 允许null值：集合中允许设置null值
4. 非线程安全：没有多线程操作支持，若需要支持线程安全，可使用Collections.synchronizedSet()或其他并发容器

设计原理

• LinkedHashSet底层数据结构是根据LinkedHashMap实现的，具有LinkedHashMap的所有特点(数组+链表+红黑树+双向链表)
• LinkedHashSet中的LinkedHashMap只有key存储实际的元素，value值是一个固定的常量
• LinkedHashSet中的LinkedHashMap初始化容量为16，当数组元素个数大于容量的75%时，会扩容到原来的2倍
• LinkedHashSet中的LinkedHashMap当链表长度大于8并且数组长度大于64，链表会进行树化，转化为红黑树
• LinkedHashSet中的LinkedHashMap的元素节点，额外维护了前后指针(双向链表)，保证元素的有序性
• LinkedHashSet使用了适配器模式，通过包装LinkedHashMap的接口，适配Set的接口

方法

构造方法

//继承自HashSet
public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = -2851667679971038690L;

   //创建一个自定义初始化容量，比例因子的LinkedHashSet
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }


    //创建一个自定义初始化容量的LinkedHashSet
    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }

    //创建一个LinkedHashSet，默认初始化容量为16，比例因子为0.75
    public LinkedHashSet() {
        super(16, .75f, true);
    }

    //创建一个LinkedHashSet，将集合元素放入
    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }
}

添加单个元素

    //实际调用LinkedHashMap的put方法
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

添加多个元素

    //实际调用AbstractCollection类中的addAll方法，循环遍历集合，
    //调用LinkedHashSet(也就是HashSet)中的add方法添加元素
    public boolean addAll(Collection<? extends E> c) {
        boolean modified = false;
        for (E e : c)
            if (add(e))
                modified = true;
        return modified;
    }

删除元素

    //实际调用LinkedHashMap中的remove方法
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

是否包含某个元素

    //实际调用hashmap中的containsKey方法(LinkedHashMap中也是调用的hashmap的containsKey)
    public boolean contains(Object o) {
        return map.containsKey(o);
    }

迭代器

    //实际调用的是LinkedHashMap的迭代器
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }