Set集合

标签: java

首先从顶层类来介绍:

Set:

set定义:不可重复存储的数据接口。

set接口相关的一些方法:

public interface Set<E> extends Collection<E> {
   // Query Operations
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();  //返回一个包含set中所有元素的数组
    <T> T[] toArray(T[] a); //返回一个包含此set中所有元素的数组;返回数组的运行时类型是指定数组的类型

    // Modification Operations
    boolean add(E e);
    boolean remove(Object o);

    // Bulk Operations
    boolean containsAll(Collection<?> c); //如果此set包含指定 collection 的所有元素,则返回 true
    boolean addAll(Collection<? extends E> c);
    boolean retainAll(Collection<?> c); //仅保留set中那些包含在指定 collection中的元素
    boolean removeAll(Collection<?> c); //移除set中那些包含在指定 collection中的元素
    void clear();

    // Comparison and hashing
    boolean equals(Object o);
    int hashCode(); //返回set的哈希码
    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT);
    }
}

可以看到set接口继承自Collection接口,这些方法就不介绍了,前面都有介绍。
接下来再看下一层的抽象实现类AbstractSet:

public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {

    protected AbstractSet() {
    }


    // 比较指定对象与此 set的相等性,如果指定的对象也是一个set,并且两个set有相同的大小,元素,则返回true。
    public boolean equals(Object o) {
        if (o == this)
            return true;

        //1.先检查指定的对象是不是set
        if (!(o instanceof Set))
            return false;
        Collection<?> c = (Collection<?>) o;
        //2.再检查指定set的大小与这个set的大小是否相等
        if (c.size() != size())
            return false;
        try {
            //3.最后检查这个set是否包含指定set中的所有元素
            return containsAll(c);
        } catch (ClassCastException unused)   {
            return false;
        } catch (NullPointerException unused) {
            return false;
        }
    }

    //返回此set的哈希码值:即该set中所有元素的哈希值之和
    public int hashCode() {
        int h = 0;
        Iterator<E> i = iterator();
        while (i.hasNext()) {
            E obj = i.next();
            if (obj != null)
                h += obj.hashCode();
        }
        return h;
    }

    //从此 set中移除包含在指定 collection中的所有元素
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        boolean modified = false;

        //如果此set的大小>指定集合c的大小
        if (size() > c.size()) {
            //迭代指定集合c中的元素,并在此set中逐个删除
            for (Iterator<?> i = c.iterator(); i.hasNext(); )
                modified |= remove(i.next()); 
        } else {
            for (Iterator<?> i = iterator(); i.hasNext(); ) {
                if (c.contains(i.next())) {
                    i.remove();
                    modified = true;
                }
            }
        }
        return modified;
    }
}

接下来就是本文的几个重点之一:HashSet

hashSet:散列表,无序的数据存储结构.简单介绍下hashCode的概念:在Object中(如果该类没有覆盖hashCode()方法的话)表示某个对象内存的一个映射数字,通过该数字可以找到对应的对象内存块,类似于数据库中的索引的概念,当然有些类会重写hashCode方法,例如字符串,基本类型的封装类等。由于在集合类添加元素(包括但是不限于)等判断两个对象是否一样时我们是利用equals方法比较的,如果equals的比较结果为true,则hashCode也必须相同,这里就要求equals重写了则应该也要重写hashCode,以保证他们的对应关系。

  知道了hashCode的概念后,我们就可以大概了解hashSet的原理了:hashSet通过hashCode建立一个索引表,用于储存其内的所有对象的内存位置,add元素进来的时候,通过该表便可以快速地判断元素是否在set内,在取元素的时候,也可以通过该表快速定位对象了,这样可以保证其快速高效地添加和查询元素。

  具体的set内部原理大概是这样的:java中会将set的内部存储机构分为多个链表(即链表数组)(我们下面称这些链表为桶),在添加元素时,通过元素的hashCode和桶的个数取余,得到的余数表示了该对象需要装到哪个桶中,只要保证桶数目够多,便可快速定位到该对象所在的位置,当发生hashCode重复时,调用冲突解决算法:该算法将hashCode相同但是eauqls为false的方法放在一个单独的链表中。具体请看下面的丑图:

这里写图片描述
好了,上图大概阐明了set的主要数据结构,归根到底就是一句话:set是利用hashCode进行对象定位,利用链表数组进行存储的数据结构!

一个小例子:

public class SimpleCollection {
    public static void main(String[] args) {
        Set<Person> sp=new HashSet<>();
        sp.add(new Person("gxx"));
        sp.add(new Person("gxx"));
        System.out.println(sp.size());


    }
}

class Person{
    private  String name;
    public Person(String name){
        this.name=name;
    }
    public String getName() {
        return name;
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof Person 
                ? this.name==((Person)obj).getName()
                :false
                ;
    }
    @Override
    public int hashCode() {
        return name.hashCode();
    }
}

自定义类使用hashset存储,为什么需要重写equals和hashcode方法?
https://jingyan.baidu.com/article/d5a880eb8fb61d13f147cc99.html

接下来就是HashSet的方法:

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;


    private static final Object PRESENT = new Object();


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


    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }


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


    public int size() {
        return map.size();
    }


    public boolean isEmpty() {
        return map.isEmpty();
    }


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


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


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


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


    @SuppressWarnings("unchecked")
    public Object clone() {
        try {
            HashSet<E> newSet = (HashSet<E>) super.clone();
            newSet.map = (HashMap<E, Object>) map.clone();
            return newSet;
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }


    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out any hidden serialization magic
        s.defaultWriteObject();

        // Write out HashMap capacity and load factor
        s.writeInt(map.capacity());
        s.writeFloat(map.loadFactor());

        // Write out size
        s.writeInt(map.size());

        // Write out all elements in the proper order.
        for (E e : map.keySet())
            s.writeObject(e);
    }


    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden serialization magic
        s.defaultReadObject();

        // Read capacity and verify non-negative.
        int capacity = s.readInt();
        if (capacity < 0) {
            throw new InvalidObjectException("Illegal capacity: " +
                                             capacity);
        }

        // Read load factor and verify positive and non NaN.
        float loadFactor = s.readFloat();
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new InvalidObjectException("Illegal load factor: " +
                                             loadFactor);
        }

        // Read size and verify non-negative.
        int size = s.readInt();
        if (size < 0) {
            throw new InvalidObjectException("Illegal size: " +
                                             size);
        }

        // Set the capacity according to the size and load factor ensuring that
        // the HashMap is at least 25% full but clamping to maximum capacity.
        capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
                HashMap.MAXIMUM_CAPACITY);

        // Create backing HashMap
        map = (((HashSet<?>)this) instanceof LinkedHashSet ?
               new LinkedHashMap<E,Object>(capacity, loadFactor) :
               new HashMap<E,Object>(capacity, loadFactor));

        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            @SuppressWarnings("unchecked")
                E e = (E) s.readObject();
            map.put(e, PRESENT);
        }
    }


    public Spliterator<E> spliterator() {
        return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
    }
}

可以看出来底层全是map的实现,所以在以后介绍map时候具体阐述。

LinkedHashSet:
LinkedHashSet的特征:
LinkedHashSet是HashSet的一个子类,LinkedHashSet也根据HashCode的值来决定元素的存储位置,但同时它还用一个链表来维护元素的插入顺序,插入的时候即要计算hashCode又要维护链表,而遍历的时候只需要按链表来访问元素。查看LinkedHashSet的源码发现它是样的,

//LinkedHashSet 源码

public class LinkedHashSet extends HashSet  
    implements Set, Cloneable, Serializable  
{  

    public LinkedHashSet(int i, float f)  
    {  
        super(i, f, true);  
    }  

....  

在JAVA7中, LinkedHashSet没有定义任何方法,只有四个构造函数,它的构造函数调用了父类(HashSet)的带三个参数的构造方法,父类的构造函数如下,
//HashSet构造函数


    HashSet(int i, float f, boolean flag)  
    {  
        map = new LinkedHashMap(i, f);  
    }  

……
由此可知,LinkedHashSet本质上也是从LinkedHashMap而来,LinkedHashSet的所有方法都继承自HashSet, 而它能维持元素的插入顺序的性质则继承自LinkedHashMap.
下面是一个LinkedHashSet维持元素插入顺序的例子,

TreeSet Vs HashSet:
 首先,hashTree既然包含数组机构,那肯定在所有桶数到达临界点时,要进行大规模的扩桶操作,这样毫无疑问会大大影响性能。当然,也正因为它的无序性和包含链表的部分特性(数组链表嘛),它的插入元素是非常快的(毕竟插入时不用重新排序嘛),另外,它的查询操作速度上也还可以,毕竟它包含了一种数组的结构在里面(数组性质就是通过游标可以快速定位嘛);

    然后呢,再说treeSet吧,作为树状的结构,扩展时时不存在什么问题的,但是在插入元素的时候,显然要重新排列数据,所以插入输入肯定比不上hashSet的。当然,在查询元素中,treeSet的速度可不是盖的,毕竟人家是tree的结构(就算是简单的二叉有序树复杂度也只是logn)。
    总的来说:hashSet扩展性不好,但是查和插入(删除也一样)速度都不错;treeSet扩展性不错,查速度也不错,就是插入会速度慢点。

参考博文:
http://blog.csdn.net/lirx_tech/article/details/51514248
https://www.cnblogs.com/UniqueColor/p/5707704.html
https://www.cnblogs.com/lcplcpjava/p/6602049.html
http://blog.csdn.net/solafy/article/details/52960777

版权声明:本文为pulong0748原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/pulong0748/article/details/79236668

智能推荐

剑指offer 合并两个排序的链表

题目 链接:https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/ 思路 我想的是,与合并两个有序数组一样的思维,新建一个链表,然后判断谁的值大,进而在新的链表上面进行插入。 看书思路 合并链表是一个递归问题:合并一个节点后可以转化为一个子问题。终止条件是其中一个链表为空 代码 链表反转也可以用递归解决...

Java编程思想 第三章:操作符

Java中的操作符和c/c++中的操作符基本一致,因为我之前学习过C语言和C++,所以本章的内容大部分都已熟知,下面只做简单的介绍。 Java操作符及优先级 Java中的操作符包括算术操作符,关系操作符,逻辑操作符,位运算符、自操作运算符、移位运算符、赋值运算符和其他运算符。 算术操作符:包括加减乘除和取余(%),优先级乘除取余高于加减,都是双元运算符,其中加法(+)可以用来连接两个字符串,比如:...

JetBrains 系列开发工具,如何配置 `SCSS` `File Watcher` ,相关输出配置参数详解:webStorm phpStorm IDEA

JetBrains 系列开发工具,如何配置 SCSS File Watcher ,相关输出配置参数详解:webStorm phpStorm IDEA 前言 你目前已经了解了如何使用 SCSS 进行开发,了解了该文章的内容:『 SCSS 日常用法 』 在 JetBrains 系列开发工具中通过 FileWatcher 进行编译的 SCSS 文件都是通过 sass 这个程序进行的。『 如何添加 Fil...

C语言小函数—二进制与十六进制

测试如下 “` int main() { long int num = 15; } “`...

仿微博或微信的文章多图显示(自定义MultiImageView)

按照一般的规矩,先上张图来供大伙看看 如果大致是大伙们需要实现的功能,不烦一观 自定义MultiImageView 工具类 具体使用 app.gradle中添加依赖 implementation 'com.github.bumptech.glide:glide:4.8.0' AndroidManifest.xml中配置联网权限 <uses-permission android:name=&q...

猜你喜欢

经典进程同步和互斥问题

经典进程同步与互斥问题 前言 一、生产者-消费者问题 1.问题描述 2.问题分析 3.代码 二、读者-写者问题 1.问题描述&&分析 2.代码 三、哲学家进餐问题 1.问题描述&&分析 2.代码 四、理发师问题 1.问题描述&&分析 2.代码 前言 在多道程序设计环境中,进程同步是一个非常重要的问题,下面讨论几个经典的进程同步问题。 一、生产者-消费...

java设计模式——ThreadLocal线程单例

1、定义一个ThreadLocal线程单例,代码如下: 2、定义一个多线程类,代码如下: 3、定义一个测试类,代码如下: 4、输出结果,如下图:...

【tensorflow】线性模型实战

线性模型:y = 1.477 * x + 0.089   1. 采样数据 采样噪声eps在均值0,方差0.01的高斯分布中,而后在均匀分布U(0,1)中,区间[-10,10]进行n=100次随机采样:   2. 计算误差 循环计算每个点的预测值与真是值之间差的平方并累加,从而获得训练集上的均芳误差损失值。   3. 计算梯度   4. 梯度更新 对权重w和偏...

常见损失函数和评价指标总结(附公式&代码)

网上看到一篇很实用的帖子关于常见损失函数和评价指标,收藏下来 本文转载于https://zhuanlan.zhihu.com/p/91511706 ------------------------------------------------------------------------------------------------------------------------------...

为什么 4G/5G 的直播延时依然很高

通信技术的发展促进了视频点播和直播业务的兴起,4G 和 5G 网络技术的进步也使得流媒体技术变得越来越重要,但是网络技术并不能解决流媒体直播的高延迟问题。 本文不会介绍网络对直播业务的影响,而是会分析直播中常见的现象 — 主播和观众之间能够感觉到的明显网络延迟。除了业务上要求的延迟直播之外,有哪些因素会导致视频直播的延迟这么高呢? live-streaming  图 1 - ...