`
wolfcame
  • 浏览: 80118 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

HashSet的重复值判定逻辑

    博客分类:
  • J2SE
阅读更多
HashSet是Set接口的一个具体实现类之一,它内部采用哈希算法,专门为快速查找而设计,它不允许插入重复的值,需要注意的问题是,存入HashSet的对象必须定义hashCode和equals方法。

下面我们来谈谈HashSet如何判定两个对象是否重复。
HashSet内部使用HashMap来保存对象,将需要存入的对象比如T a,以key的形式存入HashMap中,这可以从代码中看到:
    public boolean add(E e) {
	return map.put(e, PRESENT)==null;
    }

首先,说下HashMap内部是使用数组进行存储的,数组里存放的是HashMap的内部类Entry,它是一个自引用的类,支持链表结构,用于对哈希冲突的情况下保存多个对象。
    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        public final K getKey() {
            return key;
        }
        .........//略去大段代码
    }

然后我们在HashMap的put方法中可以看到它是如何进行重复性判断的:
    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

首先,可以通过key的hashCode,经过hash()函数的处理,得出一个i,这是这个对象应该存放的位置,然后去数组中查找第一个Entry,如何Entry不存在,直接进行添加操作;如果发现存在Entry,便对其进行遍历,使用条件(k = e.key) == key || key.equals(k)进行判断,如果为true,说明已经存在,便对其进行重新设置,但是因为hashSet使用的其实是key,value对其是没任何用处的。所以相当于没有任何改变。

这也就是我们为什么在使用HashSet存储自定义类时,需要重写hashCode()和equals()方法的原因,否则使用Object对象默认的hashCode()和equals方法,Object的hashCode()使用对象的地址计算散列码,使用内存地址进行equals()判定。这可能会出现你不想看到的结果。
分享到:
评论

相关推荐

    Java面试宝典Beta6.0.pdf

    hash类存储结构(HashSet、HashMap等等)添加元素会有重复性校验,校验的方式就是先取hashCode判断是否相等(找到对应的位置,该位置可能存在多个元素),然后再取equals方法比较(极大缩小比较范围,高效判断),...

    Java毕业生校外实习日记.doc

    * 项目的难点:数据的测试、业务逻辑层的判定、用户界面的设计 总结 * Java 是一个非常重要的编程语言,需要掌握 Java 基础内容、Java 网络编程、JDBC 等知识点 * 项目经验是非常宝贵的,需要总结和反思项目经验,...

    2021-2022计算机二级等级考试试题及答案No.13966.docx

    - Set(集合):元素无序、不可重复,主要实现类有 HashSet 和 TreeSet。 - Map(映射):存储键值对,元素成对出现,主要实现类有 HashMap 和 TreeMap。 14. **循环语句**:for 语句和 while 语句是循环控制结构...

    2021-2022计算机二级等级考试试题及答案No.3829.docx

    HashMap允许null键但不允许null值(C错误),HashSet集合中的元素无序且不可重复(D错误)。 20. **C程序执行**:C语言可执行程序的开始执行点是main()函数(C)。 21. **字符数组初始化**:不正确的字符数组初始...

    完美矩形(java代码).docx

    // 使用 HashSet 存储顶点,重复出现的顶点会被移除 if (!set.add(point1)) { set.remove(point1); } if (!set.add(point2)) { set.remove(point2); } if (!set.add(point3)) { set.remove(point3); } if...

    全国信息学奥林匹克竞赛NOIP试题汇总.pdf

    ### 全国信息学奥林匹克竞赛NOIP试题解析 #### 题一:级数求和(存盘名:NOIPC1) **知识点:** ...这些题目不仅考察了基本的数据结构与算法知识,还要求参赛者具备一定的逻辑思维能力和编程技巧。

    Java常用词汇(java英语)

    5. **Set Data Structures**(集合):Java中的集合接口如`Set`,不包含重复元素,实现了如`HashSet`和`TreeSet`等不同的实现方式。 6. **Kd-Trees**(线段树):Kd树是一种在高维空间中存储点的平衡二叉树,适用于...

Global site tag (gtag.js) - Google Analytics