美文网首页
HashSet实现原理

HashSet实现原理

作者: Josaber | 来源:发表于2016-12-26 12:38 被阅读0次

HashMap的实现原理中,详细地介绍了HashMap的实现。那么你可能会问:这跟HashSet有什么关系?

HashSet简述

HashSet中不允许有重复元素,这是因为HashSet是基于HashMap实现的,HashSet中的元素都存放在HashMap的key上面,而value中的值都是统一的一个private static final Object PRESENT = new Object();。HashSet跟HashMap一样,都是一个存放链表的数组。

现在知道了二者的关系了,我们分析一下HashSet的源码:

HashSet的构造

对于HashSet而言,它是基于HashMap实现的,HashSet底层使用HashMap来保存所有元素,更确切的说,HashSet中的元素,只是存放在了底层HashMap的key上, 而value使用一个static final的Object对象标识。因此HashSet 的实现比较简单,相关HashSet的操作,基本上都是直接调用底层HashMap的相关方法来完成

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }


    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
    ... ...
}

通过源码,很容易地看出来HashSet是由HashMap构造而成。

HashSet操作

   public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

    public int size() {
        return map.size();
    }

    public boolean isEmpty() {
        return map.isEmpty();
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

    public void clear() {
        map.clear();
    }

HashSet的操作基本上都是由HashMap来实现的。

总结

HashSet底层由HashMap实现
HashSet的值存放于HashMap的key上
HashMap的value统一为PRESENT

参考

JDK API:HashSet

相关文章

网友评论

      本文标题:HashSet实现原理

      本文链接:https://www.haomeiwen.com/subject/ubjjvttx.html