精华内容
下载资源
问答
  • HashSet判断重复原理

    2019-06-13 17:55:51
    首先会调用Object的hashCode方法判hashCode是否已经存在,如存在则直接插入元素; 如果已存在则调用Object对象的equals方法判断是否返回true,如果为true则说明元素已经存在,如为false则插入元素。 注:图片...

    这个知识点完全属于今天的意外收获\(≧▽≦)/

    首先会调用Object的hashCode方法判hashCode是否已经存在,如不存在则直接插入元素;

    如果已存在则调用Object对象的equals方法判断是否返回true,如果为true则说明元素已经存在,如为false则插入元素。

    注:图片是借鉴他人博客,我再上面添加了一些额外标记


    首先我们看HashSet的源码中add方法

    /**
         * Adds the specified element to this set if it is not already present.
         * More formally, adds the specified element <tt>e</tt> to this set if
         * this set contains no element <tt>e2</tt> such that
         * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
         * If this set already contains the element, the call leaves the set
         * unchanged and returns <tt>false</tt>.
         *
         * @param e element to be added to this set
         * @return <tt>true</tt> if this set did not already contain the specified
         * element
         */
        public boolean add(E e) {
            return map.put(e, PRESENT)==null;
        }
    

    我们看到它里面调用的是map的put方法,map就是HashSet中定义的一个HashMap

    Set的add方法中传入的参数作为map的key,突然间恍然大悟,原来Set存放数据不重复的原理和Map的key不重复是一样的

    那我们继续跳进map的put方法

    /**
         * Associates the specified value with the specified key in this map.
         * If the map previously contained a mapping for the key, the old
         * value is replaced.
         *
         * @param key key with which the specified value is to be associated
         * @param value value to be associated with the specified key
         * @return the previous value associated with <tt>key</tt>, or
         *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
         *         (A <tt>null</tt> return can also indicate that the map
         *         previously associated <tt>null</tt> with <tt>key</tt>.)
         */
        public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
    

    put方法中调用了同类中的putVal方法,这个方法的第一个参数就是一个hash值,hash值是通过同类中的hash方法来获取的

    /**
         * Computes key.hashCode() and spreads (XORs) higher bits of hash
         * to lower.  Because the table uses power-of-two masking, sets of
         * hashes that vary only in bits above the current mask will
         * always collide. (Among known examples are sets of Float keys
         * holding consecutive whole numbers in small tables.)  So we
         * apply a transform that spreads the impact of higher bits
         * downward. There is a tradeoff between speed, utility, and
         * quality of bit-spreading. Because many common sets of hashes
         * are already reasonably distributed (so don't benefit from
         * spreading), and because we use trees to handle large sets of
         * collisions in bins, we just XOR some shifted bits in the
         * cheapest possible way to reduce systematic lossage, as well as
         * to incorporate impact of the highest bits that would otherwise
         * never be used in index calculations because of table bounds.
         */
        static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }

    这个代码我看不太懂,但是可以出来hash方法里获取了key的hashCode并做了相应的处理。

    (借鉴)

    我上网查了一下,原来这个hash方法叫做“扰动函数”。有人解释说:API的设计者,不能假定用户实现了良好的hashCode方法,所以通常会对hashCode再计算一次。在get和put计算下标时,先对hashCode进行hash操作,然后再通过hash值进一步计算下标。

    好,那我们重新回到putVal方法中看看,这里面都做了什么??

        /**
         * Map.put()方法的实际实现
         *
         * @param hash key的hash值
         * @param key 键值对中的key
         * @param value 键值对中的value
         * @param onlyIfAbsent 如果为true,则键值对中的值已经存在则不修改这个值
         * @param evict 如果为false,则是处于创建模式
         * @return 上一次的value,如果上一次的value不存在,则为null
         */
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
            //tab用于暂存散列表table。p为散列表中对应索引的链表的头节点的指针。n存储tab的长度。i则为命中的散列表的索引
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            //给tab和n赋值
            //当tab为null或者tab的长度n为0时,触发resize()来初始化tab
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            //使用(n - 1) & hash(等价于hash%n)计算命中的散列表索引,同时判断散列表对应索引的链表是否存在
            if ((p = tab[i = (n - 1) & hash]) == null)
                //散列表对应索引的链表不存在则创建一个新的链表
                tab[i] = newNode(hash, key, value, null);
            else {//散列表对应索引的链表已存在
                Node<K,V> e; K k;
                // 判断头节点的hash值和key是否与入参的hash值和key一致。需要注意,null的hash值为0
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    // 对应的键值对已经存在,记录下来
                    e = p;
                else if (p instanceof TreeNode)//判断对应的链表是否转化为红黑树
                    //若是,则直接调用红黑树的putTreeVal()方法
                    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开始,所以为阈值-1 
                                // 将链表转化为红黑树
                                treeifyBin(tab, hash);
                            // 中断循环
                            break;
                        }
                        // 判断当前遍历的节点的hash值和key是否与入参的hash值和key一致,即key是否已经存在
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            // key已经存在,中断循环
                            break;
                        // 记录当前遍历的节点
                        p = e;
                    }
                }
                if (e != null) { // Map中存在重复的key
                    V oldValue = e.value;//记录下旧值
                    if (!onlyIfAbsent || oldValue == null)//判断值存在是否可以进行修改以及旧值是否为null
                        e.value = value;//修改该节点的值
                    afterNodeAccess(e);// 链表节点的回调方法,此处为空方法
                    return oldValue;//返回旧值
                }
            }
            // HashMap发生结构变化,变化次数累加
            ++modCount;
            // 键值对个数自增,同时判断是否达到扩容的阈值
            if (++size > threshold)
                resize();
            // 链表节点的回调方法,此处为空方法
            afterNodeInsertion(evict);
            // 此处返回null是因为链表新增了节点,所以上一次的值必然为null
            return null;
        }

     

    展开全文
  • JAVA HashSet 去除重复原理 ​ 今天在写SQL的时候,对数据进行去除重复的时候出了一个问题:[Err] ORA-00600: 内部错误代码, 参数: [kkqcbydrv:1], [], [], [], [], [], [], []。我只要加了 DISTINCT或者GROUP BY...

    JAVA HashSet 去除重复值原理

    ​ 今天在写SQL的时候,对数据进行去除重复的时候出了一个问题:[Err] ORA-00600: 内部错误代码, 参数: [kkqcbydrv:1], [], [], [], [], [], [], []。我只要加了 DISTINCT或者GROUP BY试图进行去重,就会报这个问题。

    我实在是解决不了这个问题,我只能想用代码来解决,我就想到了用Set 来进行处理。

    ​ 总所周知Set的底层是Map来实现的,那么就很好理解是如何来实现去重的。在HashMap的put()方法添加key-value对时就会去找Map 中的key 进行覆盖,而Set 直接是 map.put(e, PRESENT)==null;, 新添加的Entry的value值 用PRESENT来固定value,又由于Map的key是不可能有重复的(因为map.put方法就会去找key,找了就对value进行覆盖,没有找到就新增),就这样做到了去重。

    	/** 
         * 如果此set中尚未包含指定元素,则添加指定元素。 
         * 更确切地讲,如果此 set 没有包含满足(e==null ? e2==null : e.equals(e2)) 
         * 的元素e2,则向此set 添加指定的元素e。 
         * 如果此set已包含该元素,则该调用不更改set并返回false。 
         * 
         * 底层实际将将该元素作为key放入HashMap。 
         * 由于HashMap的put()方法添加key-value对时,当新放入HashMap的Entry中key 
         * 与集合中原有Entry的key相同(hashCode()返回值相等,通过equals比较也返回true), 
         * 新添加的Entry的value会将覆盖原来Entry的value,但key不会有任何改变, 
         * 因此如果向HashSet中添加一个已经存在的元素时,新添加的集合元素将不会被放入HashMap中, 
         * 原来的元素也不会有任何改变,这也就满足了Set中元素不重复的特性。 
         * @param e 将添加到此set中的元素。 
         * @return 如果此set尚未包含指定元素,则返回true。 
         */   
        @Override
        public boolean add(E e) {
            return map.put(e, PRESENT)==null;
        }
    
    

    ​ 以上是个人理解,下面有一篇写的很好的文章,可以参考阅读。

    ​ 参考:

    ​ [JAVA HashSet 去除重复值原理](

    展开全文
  • hashSet保证不重复原理

    千次阅读 2017-10-06 20:45:41
    总的来说,在向hashSet中add()元素时,判断元素是否存在的依据,仅仅是hash码值就能够确定的,同时还要结合equles方法。HashSet 类中的add()方法:public boolean add(E e) { return map.put(e, PRESENT)==null; ...

    总的来说,在向hashSet中add()元素时,判断元素是否存在的依据,不仅仅是hash码值就能够确定的,同时还要结合equles方法。

    HashSet 类中的add()方法:

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

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

    可以看到for循环中,遍历table中的元素,
    1,如果hash码值不相同,说明是一个新元素,存;

    如果没有元素和传入对象(也就是add的元素)的hash值相等,那么就认为这个元素在table中不存在,将其添加进table;

    2(1),如果hash码值相同,且equles判断相等,说明元素已经存在,不存;

    2(2),如果hash码值相同,且equles判断不相等,说明元素不存在,存;

    如果有元素和传入对象的hash值相等,那么,继续进行equles()判断,如果仍然相等,那么就认为传入元素已经存在,不再添加,结束,否则仍然添加;

    展开全文
  • 先调用被添加元素的 hashCode(),和 HashSet 中已有元素的 hashCode 比较是否相同 如果相同,直接存储该元素 如果相同,再调用 equals 方法比较元素是否相同 如果相同,直接存储该元素 如果相同,认为是...
    1. 先调用被添加元素的 hashCode(),和 HashSet 中已有元素的 hashCode 比较是否相同

    2. 如果不相同,直接存储该元素

    3. 如果相同,再调用 equals 方法比较元素是否相同

    4. 如果不相同,直接存储该元素

    5. 如果相同,认为是同一元素,不存储

    HashCode方法:根据一套特殊的计算方法返回一个整形值,此值被 HashSet 用来定位对象的存储地址。

    equals方法:判断两个对象的内容是否相等。

    展开全文
  • 为什么可以用HashSet的这个不重复的值的特性来去重复呢。 为什么要用HashSet去重复的时候,要重写Java model的hashcode和equal方法 先看如下HashSet的几个构造方法如下: /** * Constructs a new, empty set; ...
  • HashSet的实现原理

    2020-03-14 23:28:10
    HashSet的实现原理 HashSet实际上是一个HashMap实例,都是一个...HashSet允许有重复元素,这是因为HashSet是基于HashMap实现的,HashSet中的元素都存放在HashMap的key上面,而value中的值都是统一的一个固定对...
  • Java中的set是一个包含重复元素的集合,确切地说,是包含e1.equals(e2)的元素对。Set中允许添加null。Set能保证集合里元素的顺序。 在往set中添加元素时,如果指定元素存在,则添加成功。也就是说,如果set...
  • HashSet中,基本的操作都是由HashMap底层实现的,因为HashSet底层是用HashMap存储数据。当向HashSet中添加元素的时候,首先...如果为空,则用 equals 方法比较元素是否相等,相等就添加,否则找一个空位添加...
  • HashSet 的实现原理

    2019-03-05 19:38:06
    HashSet 概述 对于 HashSet 而言,它是基于 HashMap 实现的,底层采用 HashMap 来保存元素,所以如果对 HashMap 比较熟悉了,那么学习 HashSet 也是很轻松的。 我们先通过 HashSet 最简单的构造函数和几个成员变量来...
  • 在以下的讨论中,以字符串作为HashSet集合的存储元素 public class test { public static void main(String[] args) { HashSet<String> hs = new HashSet<String>(); hs.add("hello");//Hash值为...
  • import java.util.HashSet; /* * 实时(现场)代码模板(Live Templates) * (1)psvm (2)sout (soutm、soutv、soutp、xxx.sout) * (3)fori (iter、数组或集合.fori)(4)inn (ifn 、xxx.nn、xxx.null) *...
  • 一、HashSet实现原理总结 二、HashSet的实现原理详解 1. HashSet概述: 2. HashSet的实现: HashMap的原理 HashSet的源代码 一、HashSet实现原理总结 HashSet的实现原理总结如下: ①是基于HashMap实现的...
  • HashSet的底层原理

    2021-06-25 23:10:26
    确定其在哈希表的位置,如果该位置为空,则直接插入,如果为空,则需要将元素与链表中的所有元素逐一比较(调用equals方法),看看是否存在,如果存在,则将其添加到该链中,如果存在将不再重复添加。...
  • 0.参考文献 深入Java集合学习系列:HashSet的实现原理 1.HashSet概述:  HashSet实现Set接口,由哈希表(实际上是一个HashMap实例)...HashSet允许有重复元素,这是因为HashSet是基于HashMap实现的,HashSet...
  • HashSet底层存储原理

    2021-05-02 11:09:04
    HashSet作为Set的主要实现类,其存储的是无序的、重复的数据。 (1)无序性:等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加,而是根据数据的哈希值 (2)重复性:保证添加的元素按照...
  • HashSet集合里面的元素允许重复,而且存储没有顺序 没有索引,可以使用普通for循环遍历,但可以使用正确for循环—>foreach遍历。可以使用迭代器iterator()进行迭代遍历,但要注意并发异常问题。 底层是使用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,206
精华内容 12,482
关键字:

hashset不重复原理