hashset_hashset底层原理 - CSDN
hashset 订阅
HashSet类,是存在于java.util包中的类 [1]  。同时也被称为集合,该容器中只能存储不重复的对象。 展开全文
HashSet类,是存在于java.util包中的类 [1]  。同时也被称为集合,该容器中只能存储不重复的对象。
信息
别    称
集合
特    点
存储不重复的对象
存在于
java.util.HashSet [1]
所属语言
java
基    础
HashMap
外文名
HashSet
HashSetHashSet 概述
对于 HashSet 而言,它是基于 HashMap 实现的,底层采用 HashMap 来保存元素,所以如果对 HashMap 比较熟悉了,那么学习 HashSet 也是很轻松的 [2]  。我们先通过 HashSet 最简单的构造函数和几个成员变量来看一下,证明咱们上边说的,其底层是 HashMap:
收起全文
精华内容
参与话题
  • HashSet

    千次阅读 2018-06-11 22:02:37
    今天学习一下HashSet,之前也用的少,但是自己也有必要了解一下什么是hashSet。简单地概括一下hashSet的一些关键点1.无参构造器发现set底层是依靠了hashMap的。2.add(E e)(1)可以看见是讲传进的参数当成map的key...

    今天学习一下HashSet,之前也用的少,但是自己也有必要了解一下什么是hashSet。简单地概括一下hashSet的一些关键点

    1.无参构造器


    发现set底层是依靠了hashMap的。

    2.add(E  e)


    (1)可以看见是讲传进的参数当成map的key,也因此需要对传进的参数重写equals()方法。

    (2)在map里,如果是key不存在,那么会返回null,如果key存在,就会替换,并且返回原本的key对应的value。

    (3)由(2)可以得出,set是不能存放相同元素的。

    3.contains(E e)


    其实就是调用了map的containsKey,这一方法可以在我的hashMap博客中找到

    4.remove(e)

    其实也是调用map.remove(key)的方法

    5.讲一下hashSet的遍历吧

    还是使用set.iterator()方法



    再接着KeyIterator往下看,返现KeyIterator只有next()方法,并且是返回k,那么hasNext(),remove()都是在hashIterator里面了


    进入关键类:hashIterator里,


    可以看见next()方法其实关键在于hashIterator的nextNode()方法。


    最后一个是remove()方法。


    也就是调用了map的removeNode(hash,key,null,matchValue,movable)方法,然后更新expectedModCount的值

    展开全文
  • 【Java集合】HashSet

    2020-06-03 18:02:11
    平时关注比较多的都是HashMap,没怎么关注过HashSet,今天仔细看了一遍HashSet的源码,解决了困扰了比较久的几个问题,分别是: 1.HashSet的底层结构是什么? 2.HashSet如何实现去重? 1、HashSet的底层结构 这个...

    平时关注比较多的都是HashMap,没怎么关注过HashSet,今天仔细看了一遍HashSet的源码,解决了困扰了比较久的几个问题,分别是:
    1.HashSet的底层结构是什么?
    2.HashSet如何实现去重?

    1、HashSet的底层结构

    这个问题在打开源码的一瞬间就找到了答案,注释里面作了清楚的说明:This class implements the Set interface, backed by a hash table (actually a HashMap instance) ,HashSet内部包含了一个HashMap的实例,对HashSet的操作实际都是对HashMap实例的操作。比较有意思的地方在于HashSet还定义了一个成员变量PRESENT作为所有添加到HashSet中元素的值,即以添加到HashSet中的元素为Key,以此处定义的成员变量PRESENT为Value,组成Key-Value键值对,然后添加到HashMap实例中。

    //用于储存对象
    private transient HashMap<E,Object> map;
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    
    //HashSet.add(E e)方法
    public boolean add(E e) {
            return map.put(e, PRESENT)==null;
        }
    

    2、HashSet如何实现去重

    这个问题的答案也在add方法中,不过具体得看HashMap的put()方法,源码如下:
    HashMap#put

    public V put(K key, V value) {
            return putVal(hash(key), key, value, false, true);
        }
    

    HashMap#putVal

     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;
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
                Node<K,V> e; K k;
                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;
        }
    

    对于该方法中有关添加元素的逻辑判断等不作展开,此处需要关注的是下面这段代码:

    //省略其他代码。。。
    //p为HashMap中key索引位置原来存在的元素
    if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
    
    //省略其他代码,在满足上面条件的情况下,会跳转到下面的代码块
     if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    //@param onlyIfAbsent if true, don't change existing value
                    if (!onlyIfAbsent || oldValue == null)  
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
    

    从上面代码可以看出,在HashMap中,当添加元素的Key已经存在时,HashMap会替换key所对应的value,同时返回oldvalue。而当添加元素的Key不存在时,则正常添加,最后返回null。
    回到HashSet中,由于添加到HashSet中的元素在其内部HasMap的实例中充当的角色是Key,所以当重复添加时map.put(e,PRSENT)==null值为false,表示添加失败。

    3、迭代器问题

    在HashSet的类注释中有这么一段话:

    Iterating over this set requires time proportional to the sum of
     the <tt>HashSet</tt> instance's size (the number of elements) plus the
    "capacity" of the backing <tt>HashMap</tt> instance (the number of
     buckets).  Thus, it's very important not to set the initial capacity too
     high (or the load factor too low) if iteration performance is important.
    

    遍历该集合的时间取决于HashSet实例的规模和HashMap实例规模的和,如果对迭代性能要求较高,不要设置太高的初始容量或太低的装载因子。

    展开全文
  • JAVA集合Set之HashSet详解

    万次阅读 2018-05-29 11:01:36
    HashSet这个类实现了Set集合,实际为一个HashMap的实例。并且HashSet提供了三个构造函数

    HashSet这个类实现了Set集合,实际为一个HashMap的实例。对集合的迭代次序没有任何保证; 特别是,它不能保证订单会随着时间的推移保持不变。这个类允许null 元素。

    并且HashSet提供了三个构造函数:


    无参数的构造函数,此构造函数创建一个大小为16的容器,加载因子为0.75(容器的大小始终是2的冥,默认为16不在赘述,在后面文章中介绍另外的构造函数,添加指定值的时候会介绍程序是如何保证始终是2的冥,透露一点如果我们传值为5的一个容器大写,那么创建的容器实际大小为8,感兴趣的可以先去看一下算法。),具体看一下实例化一个hashSet的具体参数,并且为了保证速度,我们在实例化的这个参数的时候尽量不要把容器设置的太大,或者加载因子设置太小,后面在说得到HashSet的另外三个构造函数。

    Set<String> set =new HashSet<>();

    由此图我们可以看到确实实例化了一个容量为16的HashMap,其中loadFactor为加载因子,当容量*加载因子=threshold,

    为这个容器的临界值,当存储的元素到了这个临界值,那么容器就会自动扩容。

    那么我接下来思考,容器是怎么保证添加的元素不重复的呢?(由于Set取值的时候是调用值本身来取值的,所以不能重复,如果重复了,根据值去取的时候就会不知道取哪一个。list是根据下标map是根据具体key取值

    接下来我们看一下HashSet的add方法:

    这个方法实际上是添加的一个put方法,描述的意思是:向这个set集合中添加元素,如果这个元素没有在集合中则添加到这个集合中。如果这个集合已经存在元素调用将离开。(其中PRESENT)

    K为我们添加的参数,V为一个Object的定值。

    下面我们看一下具体的put方法:

    如果key为空,我们添加一个null=value的一个元素到容器里面,如果此时容器中有一个k,v 为 null=“1234”的元素,我们在添加一个null= “456”的一个元素,容器是怎么计算的:

    我们看一下这个方法return putForNullKey(value):


    卸载这个put空的key。什么意思?就是删除并替换的意思。

    会循环拿出容器里面的元素,e=table[0],然后判断e != null 说明这个集合中是有元素的,那么紧接着开始判断,因为是K,V的形式,拿到这个k判断是否为空,如果为空,那么就用当前的value值替换原来对应的value值,也就是 null = 1234 的这个元素被null = 456 的元素替换掉。

    如果第一个e=table[0]的元素,e=null 那么就不在进入这个方法,直接modCount 做累加,然后添加这个key=null,value=456的值。上面是添加key=null,后面讲addEntry方法的具体实现。

    下面我们分析具体添加的实现,来理解key是如何保证key不重复的:

    其中

    为计算的具体hash值,具体实现如下:


    useAltHashing具体是什么目前还没有理解,我们就按默认的false来计算这个hash值。

    ^为异或运算符这里简单说一下这个异或:

    ^是异或运算符(把数据转换成二进制,然后按位进行运算)。
    运算规则:0^0 = 0, 1^0 = 1,  0^1 = 1,  1^1 = 0,运算对象相同为0,不同为1.
    如:3^5 的运算过程为:
        (1)先将3和5转换成二进制的11和101
        (2)再按对应的位分别进行运算,11位数不足补零
                 011
           ^   101
          -----------
                 110
         (3)运算结果转换成10进制:6
     
    异或运算的三个个特点:
        (1) 0^0=0,   0^1=1   0与任何数异或=任何数
        (2) 1^0=1,   1^1=0   1与任何数异或 =任何数取反
        (3) 任何数异或自己=把自己置0

    还有 | & 可以百度了解下

    然后简单介绍一下HashCode的算法:下面说两种

    1.Integer的算法:

    return当前的一个值,这个比较简单。

    2.String的算法:


    String中的hash算法,我们以int h = hash; h = 0 为基础算:例如传值为:String str = "srt";

    char val[] = {'s','r','t'}

    循环获取数组val的值,其中  h = 31 * h + val[i],val[i] 获取的是ASCII十进制的对应值,循环计算相加。最后返回具体的hash值。

    最后在


    这样计算出具体的hash值,也就是存储在map中的具体位置,相当于数组中的下标,所以效率上是非常快的。

    后面就好理解了:

    根据hash得到具体的位置,然后判断这个位置上面你的值是否hash一样并且key是否一样,如果一样,那么就替换掉,如果不一样就填加进去,具体添加方法为:

    其中处理为:


    添加值到容器中,在适当的时候扩容,什么时候扩容,当当前size >= threshold,临界值时候,扩容当前table大小的两倍,如16,到了size= 12 时候扩容到32.

    具体添加如下:

    另外三个构造函数简答列举一下:

    HashSet(Collection<? extends E> c)
    构造一个包含指定集合中的元素的新集合。  
    HashSet(int initialCapacity)
    构造一个新的空集合; 背景HashMap实例具有指定的初始容量和默认负载因子(0.75)。  
    HashSet(int initialCapacity, float loadFactor)
    构造一个新的空集合; 背景HashMap实例具有指定的初始容量和指定的负载因子。 

    这些都有在jdk的API中可以具体看一下。

    最后总结一下:

    此文章主要介绍了一下Set的一种实现HashSet的具体实现和保证key不重复的源码算法和原因。并且在最后说明一下上面忘记了:此实现不同步,为线程不安全的实现,如果有多个线程同时访问这个容器(HashSet),并对立面的元素进行了修改,则需要在外部同步。保证数据的冥等性(幂等是数据中得一个概念,表示N次变换和1次变换的结果相同。

    后面后再其他文章分别介绍TreeSet和LinkedHashSet

    如果有对此文好的建议欢迎评价交流。



    展开全文
  • HashSet简单讲解

    万次阅读 多人点赞 2019-09-18 19:47:54
    HashSet简单的理解就是HashSet对象中不能存储相同的数据,存储数据时是无序的。但是HashSet存储元素的顺序并不是按照存入时的顺序(和List显然不同) 是按照哈希值来存的所以取数据也是按照哈希值取得。存储是无序的...

    HashSet简单的理解就是HashSet对象中不能存储相同的数据,存储数据时是无序的。但是HashSet存储元素的顺序并不是按照存入时的顺序(和List显然不同) 是按照哈希值来存的所以取数据也是按照哈希值取得。存储是无序的这就和C++里的Set就不一样了C++里面的Set是有序的我认为这是在使用时候的主要区别。下面就是HashSet简单的用法:

    .申请方式括号里面的类型是随你的需要更改的。

    二.常用方法:

       类型                                            方法名                                          功能

       boolean                                    add(E e)                                       如果当前列表中不存在e, 则将e加入列表

       void                                           clear()                                           从列表中删除所有元素

       boolean                                     contains(Object j)                        判断列表中是否有元素j

       Iterator<E>                                iterator()                                      得到当前列表的遍历器

       boolean                                      remove(Object j)                         如果列表中存在元素j,则将其从列表中删除

       int                                               size()                                       得到列表中元素的个数

    .遍历的方法:

             1.用Iterator来遍历

                

                这是比较常用的方法, 但是这种方法在使用的时候HashSet修改一次之后如果想再次遍历,必须重新申请Iterator,否则               无法遍历,但是把Itetator放在一个函数里, 那么就省去多次申请Iterator了。

                2.这种方法就是用for循环遍历。

                   

                 这种方法我感觉还行,具体用那种方法遍历自己斟酌。

    四.简单的使用

    package cn.java.text.Main;
    import java.util.*;
    public class Main4 {//HashSet
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		Scanner ip = new Scanner(System.in);
            HashSet<String> hashSet = new HashSet<String>();
            int i;
            String aString;
            for(i = 0; i < 6; i++) {
            	aString = ip.next();
            	hashSet.add(aString);//加入列表
            }
            Iterator<String> iterator = hashSet.iterator();//遍历器
            while(iterator.hasNext())System.out.print(iterator.next()+" ");//判断是否有,有就输出
            String bString;
            bString =  ip.next();
            hashSet.remove(bString);//删除
            /*Iterator iterator2 = hashSet.iterator();
            while(iterator2.hasNext()) {//遍历器遍历
            	System.out.print(iterator2.next()+"  ");
            
            }*/
            for(String string: hashSet)System.out.print(string + " ");//for循环遍历
    
    	}
    
    }
    

    五.当HashSet是整型时

    展开全文
  • 什么是hashset

    千次阅读 2018-05-22 23:30:20
    hashset的定义开门见山,说白了,hashset就是阉割版的hashmap(底层都是哈希表实现的,但一个存的是键值对,一个存的只是对象,直接阉割了一半啊)hashset的特点无序性唯一性(允许使用null)本质上来讲就是hashmap...
  • 关于HashSet的各种使用方法总结

    万次阅读 多人点赞 2018-04-21 15:26:33
    1,HashSet是set接口的实现类,也是我们最常用的set集合储存的是无序,唯一的对象由于是无序的所以每组数据都没有索引,很多list可用的方法他都没有凡是需要通过索引来进行操作的方法都没有所以也不能使用普通for...
  • HashSet的三种输出方式

    千次阅读 2018-02-08 15:15:43
    import java.util.HashSet; import java.util.Iterator; public class HashSetOutputDemo { /** * HashSet的三种输出方式 * 1、toString * 2、foreach * 3、Iterator */ public static void...
  • HashSet源码解析(基于JDK1.8)

    千次阅读 2018-06-04 12:57:48
    HashSet是Java中经常被用到的集合,弄清它的底层实现,有利于我们更好地使用它,又是这句话….. 不过HashSet相对于其他集合框架简单了不少。 老规矩,还是先看看它的UML图: ①:实现了Serializable接口,表明...
  • 27.HashSet

    2020-10-11 12:22:59
    HashSet 代码 package JAVA.JAVASE.Collection.List_test; import java.util.HashSet; import java.util.Iterator; public class Set_test { public static void main(String[] args) { //1.创建集合对象 ...
  • java集合——HashSet的用法

    万次阅读 多人点赞 2016-08-08 16:28:25
    java集合——HashSet的用法 一、HashSet的构造 HashSet hashset=new HashSet(); 二、HashSet添加元素 //向hashset中添加一个字符串 hashset.add("abc"); //向hashset中添加一个整数 hashset.add(1); /...
  • HashSet的内容如何排序

    万次阅读 2009-06-14 17:10:00
    方法一:把HashSet保存在ArrayList里,再用Collections.sort()方法比較private void doSort(){ final HashSet va = new HashSet(); va.add(2007111315); va.add(2007111314); va
  • Java中很多时候都要用到HashSet的查找功能,那么在类的定义时,数据成员假如就是HashSet类型的,我们定义数据成员之后,不好直接调用add函数来实现初始化,这个时候怎么办?  我们可以这样来做: public ...
  • Java从HashSet中取元素

    万次阅读 2015-05-23 20:51:22
    import java.util.HashSet; import java.util.Iterator; import java.util.Set; public class TestHashSet { public static void main(String[] args) { Set set = new HashSet(); set.add("one"); set.add
  • //通过迭代器遍历HashSet Iterator it = hash.iterator(); while(it.hasNext()) { System.out.println(it.next()); } System.out.println("=================="); //通过加强for循环遍历HashSet for(String s: ...
  • Java的HashSet的对象遍历

    万次阅读 2014-08-12 23:04:40
    import java.util.Set;...import java.util.HashSet; import java.util.Iterator; public class SetTest { public static void main(String[] args) { Set set = new HashSet(); set.add("aaa"); set.add(
  • HashSet数据结构原理

    万次阅读 2018-09-06 00:26:08
    hashSet数据结构原理 从源码中发现HashSet源码内部维护一个HashMap变量,来看看add方法: add添加的元素存放在HashMap中,其他方法结合源码分析,参考HashMap HashMap数据结构分析链接: 特性 HashSet为...
  • HashSet:无序不重复(能存null)

    千次阅读 2016-09-23 10:51:43
    HashSet:无序不重复(能存入null) 因为HashSet是无序的,所以就没有像ArrayList修改元素(set())的方法和获得元素的方法(get()),因为ArrayList有序所以有下标 为什么HashSet是无序的: 例子:HashSet 或者...
  • HashSet进行排序

    千次阅读 2017-10-22 18:53:59
    两种办法 1转成List进行排序 2转成TreeSet进行排序 ... import java.util.ArrayList; import java.util.Collections;...import java.util.HashSet; import java.util.List; import java.util.TreeSet; public class
  • HashSet与TreeSet的区别

    万次阅读 2017-07-04 16:53:21
    1、HashSet与TreeSet接口的一点不同,HashSet 保存的数据是无序的,TreeSet保存的数据是有序的,所以如果要想保存的数据有序应该使用TreeSet子类。 2、利用TreeSet保存自定义类对象的时候,自定义所在的类一定要...
  • HashSet获取第一个元素

    万次阅读 2018-10-31 16:24:51
    背景:对外提供接口,返回的是去重后的数据(成员是java对象,使用HashSet),查询条件是多个,当传入的查询参数是唯一性的id时,实际上只会返回一条数据。有时候前端为了解析方便同时也是为了使返回的数据接口更...
1 2 3 4 5 ... 20
收藏数 173,503
精华内容 69,401
关键字:

hashset