转载

Java内功系列-HashSet是如何保证元素不重复的

面试官：你能简单介绍下List和Set有什么区别吗？

小憨：

List是一个有序的集合，在内存是连续存储的，可以存储重复的元素，List查询快，增删慢；
Set是一个无序的集合，在内存中不连续，不可以存储重复的元素，Set增删快，查询慢；

面试官：那HashSet是如何保证元素不重复的？

小憨： 3分钟。。。

为了避免出现小憨这种知其然不知其所以然的尴尬，我们还是有必要来分析下上述问题的。

客官，且看下文

我们都知道HashSet存放的元素是不允许重复的，那么HashSet又是是如何保证元素不可重复的，你知道吗？

先看段源码

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);
    }
}

乍一看这段代码，哎呦我去，new HashSet()操作不就不是维护了一个HashMap嘛，要是这么往下演的话，我觉得我这点功力也能看个大概呀！

诸位同仁，咱接着往下看

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

什么，这不就是map操作么，瞬间我来个下饭推理；

Map中的key是不允许重复的，而你HashSet正好利用我Map中key不重复的特性来校验重复元素，妙哉妙哉。

确实，HashSet确实是利用Map的这一特性实现了元素的不重复特性，但是我们再来深挖一下，Map他又是如何来保证key不重复的呢？

与其说这篇文章是介绍HashSet如何保证元素不重复的，倒不如说Map是如何保证Key不重复的。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
            
        // 1、如果该位置不存在，直接插入
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            // 2、如果存在，判断是否是重复元素
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

上面部分我重点圈了两段代码，分别是1和2。

第一段

if ((p = tab[i = (n - 1) & hash]) == null)

这段代码其实主要是通过hash计算该元素的位置，然后判断该位置是否有值，如果没有值，那么可以直接插入，最后返回null；

第二段

if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;

如果通过计算，该位置上已经有其他元素，那么接下来就会通过hash和equals进行判断，判断它是不是重复元素，如果重复元素，那么最后会将这个重复元素返回。

通过第二段代码我们可以发现，判断元素是否重复，使用的是hash和equals方法进行判断的，所有我们Set里面如果存放的是对象，那么一定要重写hash和equals方法。

现在是不是很清晰了，为啥要重写equals方法了，不会出现那么诡异的代码了，这两个对象值都一样啊，为什么Set没去重呢！

原文 https://segmentfault.com/a/1190000022469915

正文到此结束

所属分类： Java 编程技术

本文标签： key id https App Collection node CTO IO tab CEO 文章源码代码 http HashSet java final zab UI list equals map value HashMap
版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
本文海报： 生成海报一生成海报二

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

Java内功系列-HashSet是如何保证元素不重复的

热门推荐

相关文章

说给你听

本文目录

随机标签

书籍教程

近期评论

网站信息

其他链接

关于本站

问题交流