Java集合--Set(深入学习)

1 Set集合主要源码分析

上一篇,我们介绍了Java集合框架中的Set集合,主要讲了HashSet和TreeSet这两个实现类。本篇,依旧对这两个实现类进行学习,通过学习源码来深入地了解。

1.1 HashSet源码分析(基于JDK1.7.0_75)

HashSet基于HashMap,底层方法是通过调用HashMap的API来实现,因此HashSet源码结构比较简单,代码较少。

  • 成员变量:

在HashSet中,有两个成员变量比较重要--map、PRESENT;

其中,map就是存储元素的地方,实际是一个HashMap。当有元素插入到HashSet中时,会被当做HashMap的key保存到map属性中去。

对于HashMap来说,光有key还不够,在HashSet的实现中,每个key对应的value都默认为PRESENT属性,也就是new了一个Object对象而已;

public class HashSet<E> 
    extends AbstractSet<E> 
    implements Set<E>, Cloneable, java.io.Serializable{

    static final long serialVersionUID = -5024744406713321676L;

    //HashSet通过HashMap保存集合元素的:
    private transient HashMap<E,Object> map;

    //HashSet底层由HashMap实现,新增的元素为map的key,而value则默认为PRESENT。
    private static final Object PRESENT = new Object();
}
  • 构造方法:

HashSet的构造方法很简单,主要是在方法内部初始化map属性,new了一个HashMap对象;

public class HashSet<E>
        extends AbstractSet<E>
        implements Set<E>, Cloneable, java.io.Serializable {
    
    //无参构造方法:
    public HashSet() {
        //默认new一个HashMap
        map = new HashMap<>();
    }

    // 带集合的构造函数
    public HashSet(Collection<? extends E> c) {
        // 进行初始化HashMap容量判断,
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

    // 指定HashSet初始容量和加载因子的构造函数:主要用于Map内部的扩容机制
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

    // 指定HashSet初始容量的构造函数
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

    //与前4个不同,此构造最终new了一个LinkedHashMap对象:
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
}
  • add():

HashSet的add(E e)方法,主要是调用底层HashMap的put(K key, V value)方法。

其中key就是HashSet集合插入的元素,而value则是默认的PRESENT属性(一个new Object());

//调用HashMap中的put()方法:
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}
  • remove():

与add(E e)方法类似,HashSet的remove(Object o)也是调用了底层HashMap的(Object key)方法;

主要是计算出要删除元素的hash值,在HashMap找到对应的对象,然后从Entry<K,V>[]数组中删除;

//调用HashMap中的remove方法:
public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

1.2 TreeSet源码分析(基于JDK1.7.0_75)

上面说了HashSet,接下来说说TreeSet。

与HashSet类似,TreeSet底层也是采用了一个Map来保存集合元素,这个Map就是NavigableMap。

不过,NavigableMap仅仅是一个接口,具体的实现还是使用了TreeMap类;

  • 成员变量

当你看到下面的代码之后,你就会明白我为什么一直在说TreeSet底层使用了Map集合了;成员变量m是一个NavigableMap类型的Map集合,常用实现是TreeMap对象;

在TreeMap中,key是我们TreeSet插入的元素,而value则是TreeSet中另一个成员变量PRESENT,一个普通的不能再普通的Object对象;

public class TreeSet<E> extends AbstractSet<E>
        implements NavigableSet<E>, Cloneable, java.io.Serializable {

    //TreeSet中保存元素的map对象:
    private transient NavigableMap<E,Object> m;

    //map对象中保存的value:
    private static final Object PRESENT = new Object();
}
  • 构造方法

    public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable {

      //最底层的构造方法,不对外。传入一个NavigableMap接口的实现类
      TreeSet(NavigableMap<E,Object> m) {
          this.m = m;
      }
    
      //无参构造:向底层构造传入一个TreeMap对象:
      public TreeSet() {
          this(new TreeMap<E,Object>());
      }
    
      //传入比较器的构造:通常传入一个自定义Comparator的实现类;
      public TreeSet(Comparator<? super E> comparator) {
          this(new TreeMap<>(comparator));
      }
    
      //将集合Collection传入TreeSet中:
      public TreeSet(Collection<? extends E> c) {
          this();
          addAll(c);
      }
    
      //将集合SortedSet传入TreeSet中:
      public TreeSet(SortedSet<E> s) {
          this(s.comparator());
          addAll(s);
      }
    

    }

  • add

向TreeSet中添加元素:

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

删除TreeSet中元素o:

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

无论是HashSet,还是TreeSet,它们的API都是通过底层的Map来实现的。所以就源码来说,没有太多需要去理解地方。

在后面的Map讲解中,我会在详细进行说明。当你理解了Map之后,再回过头来看Set,就很容易去理解了;

1.3 SortedSet和NavigableSet到底是什么

本章节,是我在写的时候突然想起来的,觉得有必要加进来阐述下。

为什么觉得有必要呢?

主要是看了一些关于TreeSet讲解的文章,在介绍TreeSet的时候都会提到NavigableSet,接着会说下NavigableSet是个"导航Set集合",提供了一系列"导航"方法。看到这,我不禁想吐槽下,什么是"导航"方法。

针对于这个疑问,我查了下相关的资料,对这个类有个初步的理解。下面,我就说一下!

通过接口的定义,我们可以看到NavigableSet继承了SortedSet接口(后面说),实现了对其的扩展;

而通过下面的方法,我们得出NavigableSet实际提供了一系列的搜索匹配元素的功能,能获取到某一区间内的集合元素 ;

public interface NavigableSet<E> extends SortedSet<E> {
     
     E lower(E e);//返回此set集合中小于e元素的最大元素

     E floor(E e);//返回此set集合中小于等于e元素的最大元素

     E ceiling(E e);//返回此set集合中大于等于e元素的最小元素

     E higher(E e);//返回此set集合中大于e元素的最小元素
     
     E pollFirst(); //获取并移除此set集合中的第一个元素
     
     E pollLast();//获取并移除此set集合中的最后一个元素
     
     Iterator<E> iterator();//返回此set集合的迭代器--升序

     NavigableSet<E> descendingSet();//以倒序的顺序返回此set集合

     Iterator<E> descendingIterator();//返回此set集合的迭代器--倒序

     //返回此set集合的部分元素--从fromElement开始到toElement结束,其中fromInclusive、toInclusive意为返回的集合是否包含头尾元素
     NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive);

     //返回此set集合的部分元素--小于toElement,inclusive意味返回的集合是否包含toElement
     NavigableSet<E> headSet(E toElement, boolean inclusive);

     //返回此set集合的部分元素--从fromElement开始到toElement结束,包含头不含为尾
     SortedSet<E> subSet(E fromElement, E toElement);

     //返回此set集合的部分元素--小于toElement
     SortedSet<E> headSet(E toElement);
     
     //返回此set集合的部分元素--大于等于toElement
     SortedSet<E> tailSet(E fromElement);
}

说完了NavigableSet,我们在一起儿看下其父类SortedSet接口:

通过名字,我们可以得出此接口跟排序有关,会提供跟排序的方法;

public interface SortedSet<E> extends Set<E> {

    //返回与排序有关的比较器
    Comparator<? super E> comparator();

    //返回从fromElement到toElement的元素集合:
    SortedSet<E> subSet(E fromElement, E toElement);
    
    //返回从第一个元素到toElement元素的集合:
    SortedSet<E> headSet(E toElement);
  
    //返回从fromElement开始到最后元素的集合:
    SortedSet<E> tailSet(E fromElement);
    
    //返回集合中的第一个元素:
    E first();
   
    //返回集合中的最后一个元素:
    E last();
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,482评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,377评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,762评论 0 342
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,273评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,289评论 5 373
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,046评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,351评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,988评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,476评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,948评论 2 324
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,064评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,712评论 4 323
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,261评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,264评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,486评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,511评论 2 354
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,802评论 2 345

推荐阅读更多精彩内容

  • 一、基本数据类型 注释 单行注释:// 区域注释:/* */ 文档注释:/** */ 数值 对于byte类型而言...
    龙猫小爷阅读 4,254评论 0 16
  • 3.3 集合 一方面, 面向对象语言对事物的体现都是以对象的形式,为了方便对多个对象的操作,就要对对象进行存储。另...
    闫子扬阅读 717评论 0 1
  • 集合类简介 为什么出现集合类?面向对象语言对事物的体现都是以对象的形式,所以为了方便对多个对象的操作,就要对对象进...
    阿敏其人阅读 1,406评论 0 7
  • 概述 Java集合框架由Java类库的一系列接口、抽象类以及具体实现类组成。我们这里所说的集合就是把一组对象组织到...
    absfree阅读 1,248评论 0 10
  • Collection ├List │├LinkedList │├ArrayList │└Vector │└Stac...
    AndyZX阅读 869评论 0 1