java集合类源码分析之Set详解

Set集合与List一样,都是继承自Collection接口,常用的实现类有HashSet和TreeSet。值得注意的是,HashSet是通过HashMap来实现的而TreeSet是通过TreeMap来实现的,所以HashSet和TreeSet都没有自己的数据结构,具体可以归纳如下:

•Set集合中的元素不能重复,即元素唯一

•HashSet按元素的哈希值存储,所以是无序的,并且最多允许一个null对象

•TreeSet按元素的大小存储,所以是有序的,并且不允许null对象

•Set集合没有get方法,所以只能通过迭代器(Iterator)来遍历元素,不能随机访问

1.HashSet

下面给出HashSet的部分源码,以理解它的实现方式。

static final long serialVersionUID = -5024744406713321676L;

 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的数据是存储在HashMap的实例对象map中的,并且对应于map中的key,而Object类型的引用PRESENT则是对应于map中的value的一个虚拟值,没有实际意义。联想到HashMap的一些特性:无序存储、key值唯一等等,我们就可以很自然地理解Set集合元素不能重复以及HashSet无序存储的特性了。

下面从源代码的角度来理解HashSet的基本用法:

•构造器(四种)

1.HashSet() 空的构造器,初始化一个空的HashMap

2.HashSet(Collection<? extends E> c) 传入一个子集c,用于初始化HashMap

3.HashSet(int initialCapacity, float loadFactor) 初始化一个空的HashMap,并指定初始容量和加载因子

4.HashSet(int initialCapacity) 初始化一个空的HashMap,并指定初始容量

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

 public HashSet(int initialCapacity) {
  map = new HashMap<>(initialCapacity);
 }

•插入元素

1.add(E e) 插入指定元素(调用HashMap的put方法实现)

   Set<String> hashSet = new HashSet<String>();
   hashSet.add("D");
   hashSet.add("B");
   hashSet.add("C");
   hashSet.add("A");

•查找元素

1.contains(Object o) 判断集合中是否包含指定的元素(调用HashMap的containsKey方法实现)

  public boolean contains(Object o) {
   return map.containsKey(o);
  }

2.由于HashSet的实现类中没有get方法,所以只能通过迭代器依次遍历,而不能随机访问(调用HashMap中keySet的迭代器实现)

  public Iterator<E> iterator() {
   return map.keySet().iterator();
  }

应用示例:

Set<String> hashSet = new HashSet<String>();
  hashSet.add("D");
  hashSet.add("B");
  hashSet.add("C");
  hashSet.add("A");
  for (Iterator iterator = hashSet.iterator(); iterator.hasNext();) {
   String string = (String) iterator.next();
   System.out.print(string+" ");
  }//D A B C

•修改元素

由于HashMap中的key值不能修改,所以HashSet不能进行修改元素的操作

•删除元素

1.remove(Object o) 删除指定元素(调用HashMap中的remove方法实现,返回值为true或者false)

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

2.clear() 清空元素(调用HashMap中的clear方法实现,没有返回值)

public void clear() {
   map.clear();
  }

2.TreeSet

TreeSet是SortedSet接口的唯一实现类。前面说过,TreeSet没有自己的数据结构而是通过TreeMap实现的,所以TreeSet也是基于红黑二叉树的一种存储结构,所以TreeSet不允许null对象,并且是有序存储的(默认升序)。

private transient NavigableMap<E,Object> m;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

上述源代码中的NavigableMap是继承自SrotedMap的一个接口,其实现类为TreeMap,因此TreeSet中的数据是通过TreeMap来存储的,此处的PRESENT也是没有实际意义的虚拟值。

下面从源代码的角度来理解HashSet的基本用法:

•构造器(四种)

1.TreeSet() 空的构造器,初始化一个空的TreeMap,默认升序排列

2.TreeSet(Comparator<? super E> comparator) 传入一个自定义的比较器,常常用于实现降序排列

3.TreeSet(Collection<? extends E> c) 传入一个子集c,用于初始化TreeMap对象,默认升序

4.TreeSet(SortedSet<E> s) 传入一个有序的子集s,用于初始化TreeMap对象,采用子集的比较器

public TreeSet() {
  this(new TreeMap<E,Object>());
 }

 public TreeSet(Comparator<? super E> comparator) {
  this(new TreeMap<>(comparator));
 }

 public TreeSet(Collection<? extends E> c) {
  this();
  addAll(c);
 }

 public TreeSet(SortedSet<E> s) {
  this(s.comparator());
  addAll(s);
 }

应用示例

//自定义一个比较器,实现降序排列
  Set<Integer> treeSet = new TreeSet<Integer>(new Comparator<Integer>() {

   @Override
   public int compare(Integer o1, Integer o2) {
//    return 0;  //默认升序
    return o2.compareTo(o1);//降序
   }
  });
  treeSet.add(200);
  treeSet.add(120);
  treeSet.add(150);
  treeSet.add(110);
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  } //200 150 120 110
ArrayList<Integer> list = new ArrayList<Integer>();
  list.add(300);
  list.add(120);
  list.add(100);
  list.add(150);
  System.out.println(list); //[300, 120, 100, 150]

  //传入一个子集,默认升序排列
  TreeSet<Integer> treeSet = new TreeSet<Integer>(list);
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  }//100 120 150 300
/*
   * 传入一个有序的子集,采用子集的比较器
   *  注意子集的类型必须是SortedSet及其子类或者实现类,否则将采用默认的比较器
   *  所以此处subSet的类型也可以是TreeSet。
   */

  SortedSet<Integer> subSet = new TreeSet<Integer>(new Comparator<Integer>() {

   @Override
   public int compare(Integer o1, Integer o2) {
//    return 0;  //默认升序
    return o2.compareTo(o1);//降序
   }
  });
  subSet.add(200);
  subSet.add(120);
  subSet.add(150);
  subSet.add(110);
  for (Iterator iterator = subSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  } //200 150 120 110 

  System.out.println();
  Set<Integer> treeSet = new TreeSet<Integer>(subSet);
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  }//200 150 120 110 

  System.out.println();
  treeSet.add(500);
  treeSet.add(100);
  treeSet.add(105);
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  }//500 200 150 120 110 105 100

• 插入元素

1.add(E e) 插入指定的元素(调用TreeMap的put方法实现)

2.addAll(Collection<? extends E> c) 插入一个子集c

ArrayList<Integer> list = new ArrayList<Integer>();
  list.add(300);
  list.add(120);
  list.add(100);
  list.add(150);
  System.out.println(list); //[300, 120, 100, 150]

  Set<Integer> treeSet = new TreeSet<Integer>();

  //插入一个子集,默认升序
  treeSet.addAll(list);
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  }//100 120 150 300

•查找元素

1.contains(Object o) 判断集合中是否包含指定对象(调用TreeMap的containsKey方法实现)

2.与HashSet一样,TreeSet的实现类中没有get方法,所以只能通过迭代器依次遍历,而不能随机访问(调用TreeMap中keySet的迭代器实现)。

•修改元素

TreeSet不能进行修改元素的操作,原因与HashSet一样。

•删除元素

1.remove(Object o) 删除指定元素(调用TreeMap中的remove方法实现,返回true或者false)

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

2.clear() 清空元素(调用TreeMap中的clear方法实现,无返回值)

  public void clear() {
   m.clear();
  }

应用示例:

ArrayList<Integer> list = new ArrayList<Integer>();
  list.add(300);
  list.add(120);
  list.add(100);
  list.add(150);
  System.out.println(list); //[300, 120, 100, 150]

  Set<Integer> treeSet = new TreeSet<Integer>();

  //插入一个子集,默认升序
  treeSet.addAll(list);
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  }//100 120 150 300 

  System.out.println(treeSet.remove(100));//true
  for (Iterator iterator = treeSet.iterator(); iterator.hasNext();) {
   Integer integer = (Integer) iterator.next();
   System.out.print(integer+" ");
  }//120 150 300 

  treeSet.clear();
  System.out.println(treeSet.size());//0

至此,HashSet和TreeSet的存储结构及基本用法介绍完毕。

以上这篇java集合类源码分析之Set详解就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • Java中的collection集合类型总结

    Java集合是java提供的工具包,包含了常用的数据结构:集合.链表.队列.栈.数组.映射等.Java集合工具包位置是java.util.* Java集合主要可以划分为4个部分:List列表.Set集合.Map映射.工具类(Iterator迭代器.Enumeration枚举类.Arrays和Collections). Java集合工具包框架如下图. 说明:看上面的框架图,先抓住它的主干,即Collection和Map. Collection是一个接口,是高度抽象出来的集合,它包含了集合的基本操作

  • 总结Java集合类操作优化经验

    在实际的项目开发中会有很多的对象,如何高效.方便地管理对象,成为影响程序性能与可维护性的重要环节.Java 提供了集合框架来解决此类问题,线性表.链表.哈希表等是常用的数据结构,在进行 Java 开发时,JDK 已经为我们提供了一系列相应的类来实现基本的数据结构,所有类都在 java.util 这个包里,清单1 描述了集合类的关系. 清单 1.集合类之间关系 Collection ├List │├LinkedList │├ArrayList │└Vector │ └Stack └Set Map

  • Java集合类的组织结构和继承、实现关系详解

    Collection继承.实现关系如下(说明(I)表示接口, (C)表示Java类,<--表示继承,<<--表示实现): (I)Iterable |<-- (I)Collection |<-- (I)List |<<-- (C)ArrayList |<<-- (C)LinkedList |<<-- (C)Vector |<-- (I)Set |<<-- (C)HashSet |<-- (I)Queue [kju] M

  • java集合类arraylist循环中删除特定元素的方法

    在项目开发中,我们可能往往需要动态的删除ArrayList中的一些元素. 一种错误的方式: <pre name="code" class="java">for(int i = 0 , len= list.size();i<len;++i){ if(list.get(i)==XXX){ list.remove(i); } } 上面这种方式会抛出如下异常: Exception in thread "main" java.lang.I

  • Redis有序集合类型的操作_动力节点Java学院整理

    今天我们说一下Redis中最后一个数据类型 "有序集合类型",回首之前学过的几个数据结构,不知道你会不会由衷感叹,开源的世界真好,写这些代码的好心人真的要一生平安哈,不管我们想没想的到的东西,在这个世界上都已经存在着,曾几何时,我们想把所有数据按照数据结构模式组成后灌输到内存中,然而为了达到内存共享的方式,不得不将这块内存单独部署,同时还要考虑怎么序列化,何时序列互的问题,烦心事太多太多...后来才知道有redis这么个玩意,能把高级的,低级的数据结构单独包装到一个共享内存中(Redi

  • Java的Hibernate框架中集合类数据结构的映射编写教程

    一.集合映射 1.集合小介 集合映射也是基本的映射,但在开发过程中不会经常用到,所以不需要深刻了解,只需要理解基本的使用方法即可,等在开发过程中遇到了这种问题时能够查询到解决方法就可以了.对应集合映射它其实是指将java中的集合映射到对应的表中,是一种集合对象的映射,在java中有四种类型的集合,分别是Set.Map.List还有普通的数组,它们之间有很大的区别: (1)Set,不可以有重复的对象,对象是无序的: (2)List,可以与重复的对象,对象之间有顺序: (3)Map,它是键值成对出现

  • redis集合类型_动力节点Java学院整理

    我们来看看Redis五大类型中的第四大类型:"集合类型",集合类型还是蛮有意思的,先看redis手册,如下: 上面就是redis中的set类型使用到的所有方法,还是老话,常用的方法也就那么四个(CURD)... 一: 常用方法 1. SAdd 这个方法毫无疑问,就是向集合里面添加数据,比如下面这样,我往fruits集合里面添加喜爱的水果. 127.0.0.1:6379> sadd fruits apple (integer) 1 127.0.0.1:6379> sadd f

  • 浅析Java中的set集合类型及其接口的用法

    概念 首先,我们看看Set集合. (01) Set 是继承于Collection的接口.它是一个不允许有重复元素的集合. (02) AbstractSet 是一个抽象类,它继承于AbstractCollection,AbstractCollection实现了Set中的绝大部分函数,为Set的实现类提供了便利. (03) HastSet 和 TreeSet 是Set的两个实现类.     HashSet依赖于HashMap,它实际上是通过HashMap实现的.HashSet中的元素是无序的.   

  • Java集合类中文介绍

    Java集合是java提供的工具包,包含了常用的数据结构:集合.链表.队列.栈.数组.映射等.Java集合工具包位置是java.util.*Java集合主要可以划分为4个部分:List列表.Set集合.Map映射.工具类(Iterator迭代器.Enumeration枚举类.Arrays和Collections)..Java集合工具包框架图(如下):大致说明:看上面的框架图,先抓住它的主干,即Collection和Map.1 Collection是一个接口,是高度抽象出来的集合,它包含了集合的基

  • java集合类源码分析之Set详解

    Set集合与List一样,都是继承自Collection接口,常用的实现类有HashSet和TreeSet.值得注意的是,HashSet是通过HashMap来实现的而TreeSet是通过TreeMap来实现的,所以HashSet和TreeSet都没有自己的数据结构,具体可以归纳如下: •Set集合中的元素不能重复,即元素唯一 •HashSet按元素的哈希值存储,所以是无序的,并且最多允许一个null对象 •TreeSet按元素的大小存储,所以是有序的,并且不允许null对象 •Set集合没有ge

  • Java集合框架源码分析之LinkedHashMap详解

    LinkedHashMap简介 LinkedHashMap是HashMap的子类,与HashMap有着同样的存储结构,但它加入了一个双向链表的头结点,将所有put到LinkedHashmap的节点一一串成了一个双向循环链表,因此它保留了节点插入的顺序,可以使节点的输出顺序与输入顺序相同. LinkedHashMap可以用来实现LRU算法(这会在下面的源码中进行分析). LinkedHashMap同样是非线程安全的,只在单线程环境下使用. LinkedHashMap源码剖析 LinkedHashM

  • JAVA 枚举单例模式及源码分析的实例详解

    JAVA 枚举单例模式及源码分析的实例详解 单例模式的实现有很多种,网上也分析了如今实现单利模式最好用枚举,好处不外乎三点: 1.线程安全 2.不会因为序列化而产生新实例 3.防止反射攻击但是貌似没有一篇文章解释ENUM单例如何实现了上述三点,请高手解释一下这三点: 关于第一点线程安全,从反编译后的类源码中可以看出也是通过类加载机制保证的,应该是这样吧(解决) 关于第二点序列化问题,有一篇文章说枚举类自己实现了readResolve()方法,所以抗序列化,这个方法是当前类自己实现的(解决) 关于

  • nginx源码分析线程池详解

    nginx源码分析线程池详解 一.前言 nginx是采用多进程模型,master和worker之间主要通过pipe管道的方式进行通信,多进程的优势就在于各个进程互不影响.但是经常会有人问道,nginx为什么不采用多线程模型(这个除了之前一篇文章讲到的情况,别的只有去问作者了,HAHA).其实,nginx代码中提供了一个thread_pool(线程池)的核心模块来处理多任务的.下面就本人对该thread_pool这个模块的理解来跟大家做些分享(文中错误.不足还请大家指出,谢谢) 二.thread_

  • Vue编译器源码分析compileToFunctions作用详解

    目录 引言 Vue.prototype.$mount函数体 源码出处 options.delimiters & options.comments compileToFunctions函数逐行分析 createFunction 函数源码 引言 Vue编译器源码分析 接上篇文章我们来分析:compileToFunctions的作用. 经过前面的讲解,我们已经知道了 compileToFunctions 的真正来源你可能会问为什么要弄的这么复杂?为了搞清楚这个问题,我们还需要继续接触完整的代码. 下面

  • nginx源码分析configure脚本详解

    nginx源码分析--configure脚本 一.前言 在分析源码时,经常可以看到类似 #if (NGX_PCRE) .... #endif 这样的代码段,这样的设计可以在不改动源码的情况下,通过简单的定义宏的方式来实现功能的打开与关闭,但是在nginx/src目录下始终没有找到宏 NGX_PCRE 对应的 #define 语句. 在之前介绍event模块的时候,讲到init_cycle函数中对cycle进行了初始化,其中很重要一步操作就是讲包含所有module信息的数组拷贝到这个cycle对应

  • jQuery源码分析之Callbacks详解

    代码的本质突出顺序.有序这一概念,尤其在javascript--毕竟javascript是单线程引擎. javascript拥有函数式编程的特性,而又因为javascript单线程引擎,我们的函数总是需要有序的执行.优秀代码常常 把函数切割成各自的模块,然后在某一特定条件下执行,既然这些函数是有序的执行,那么我们为什么不编写一个统一管理的对象,来帮助我们管理这些函数--于是,Callbacks(回调函数)诞生. 什么是Callbacks javascript中充斥着函数编程,例如最简单的wind

  • Django restframework 源码分析之认证详解

    前言 最近学习了 django 的一个 restframework 框架,对于里面的执行流程产生了兴趣,经过昨天一晚上初步搞清楚了执行流程(部分方法还不太清楚),于是想详细的总结一下当来一个请求时,在该框架里面是如何执行的? 启动项目时 昨天在调试django时,发现在 APIView 中打的断点没有断下来,而是打在 View 中的断点断下来了,调试了很多次,最后发现,在 django 项目启动时,会首先加载 urls 中的文件,执行 views 中类的 as_view方法,其实是继承自 API

  • 通过JDK源码分析关闭钩子详解

    关闭钩子 用户关闭关闭程序,需要做一些善后的清理工作,但问题是,某些用户不会按照推荐的方法关闭应用程序,肯能导致善后工作无法进行.像tomcat调用server的start方法启动容器,然后会逐级调用start.当发出关闭命令是会启动关闭功能,但是关闭可能会有一些意外产生,导致应用程序没有进入到我们制定的关闭方法去.如何解决这个问题呢,使得即使有意外也能正常进入关闭流程. 好在java提供了一种优雅的方式去解决这种问题.使得关闭的善后处理的代码能执行.java的关闭钩子能确保总是执行,无论用户如

  • Java源码解析之TypeVariable详解

    TypeVariable,类型变量,描述类型,表示泛指任意或相关一类类型,也可以说狭义上的泛型(泛指某一类类型),一般用大写字母作为变量,比如K.V.E等. 源码 public interface TypeVariable<D extends GenericDeclaration> extends Type { //获得泛型的上限,若未明确声明上边界则默认为Object Type[] getBounds(); //获取声明该类型变量实体(即获得类.方法或构造器名) D getGenericDe

随机推荐