小心程序猿QAQ 潜水
  • 4发帖数
  • 4主题数
  • 0关注数
  • 0粉丝
开启左侧

深入Java源码剖析之Set集合

[复制链接]
小心程序猿QAQ 发表于 2021-8-17 20:34:02 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
Java的集合类由Collection接口和Map接口派生,此中:

  • List代表有序集合,元素有序且可重复
  • Set代表无序集合,元素无序且不可重复
  • Map集合存储键值对
那么本篇文章将从源码角度讨论一下无序集合Set。
HashSet

HashSet实现 Set 接口,由哈希表(实际上是一个 HashMap 实例)支持。它不保证 set 的迭代顺序;特别是它不保证该顺序恒久稳定。此类答应使用 null 元素。看下面的一个例子:
        HashSet hs = new HashSet();        // 添加元素        hs.add("hello");        hs.add("world");        hs.add("java");        hs.add("world");        hs.add(null);                //遍历        for (String str : hs) {                System.out.println(str);        }复制代码执行结果:
nullworldjavahello复制代码由执行结果可知,它答应参加null,元素不可重复,且元素无序。 那我们想,它是如何保证元素不重复的呢?这就要来分析一下它的源码。 首先是HashSet集合的add()方法:
public boolean add(E e) {    return map.put(e, PRESENT)==null;}复制代码该方法中调用了map对象的put()方法,那么map对象是什么呢?
private transient HashMap map;复制代码可以看到,这个map对象就是HashMap,我们继续查看HashSet的构造方法:
public HashSet() {    map = new HashMap();}复制代码到这里,应该就能明白,HashSet的底层实现就是HashMap,所以调用的put()方法就是HashMap的put()方法,那我们继续查看put()方法:
public V put(K key, V value) {    return putVal(hash(key), key, value, false, true);}复制代码put()方法调用了putVal()方法,那么重点就是这个putVal()方法了:
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {        Node[] tab; Node p; int n, i;         //判定hashmap对象中 tabel属性是否为空--->为空---->resize()        if ((tab = table) == null || (n = tab.length) == 0)            n = (tab = resize()).length;        //发现tab 没有值,直接存入即可        if ((p = tab[i = (n - 1) & hash]) == null)            tab = newNode(hash, key, value, null);        else {                //tab有值,分情况讨论            Node e; K k;            // 如果新插入的元素和table中p元素的hash值,key值相同的话            if (p.hash == hash &&                ((k = p.key) == key || (key != null && key.equals(k))))                e = p;            // 如果是红黑树结点的话,进行红黑树插入            else if (p instanceof TreeNode)                e = ((TreeNode)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);                        // 链表长度大于8时,将链表转红黑树                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                            treeifyBin(tab, hash);                        break;                    }                    // 如果与单向链表上的某个结点key值相同,则跳出循环,此时e是需要修改的结点,p是e的前驱结点                    if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))                        break;                     //更新变量p                    p = e;                }            }            //处置惩罚完毕,添加元素            if (e != null) { // existing mapping for key                V oldValue = e.value;                //判定是否答应覆盖,而且value是否为空                if (!onlyIfAbsent || oldValue == null)                    e.value = value;                afterNodeAccess(e);                return oldValue;            }        }        ++modCount;// 更改操作次数        //如果大于临界值        if (++size > threshold)                //将数组大小设置为原来的2倍,并将原先的数组中的元素放到新数组中            resize();        afterNodeInsertion(evict);        return null;    }复制代码我们一起分析一下这段源码,首先它将table对象赋值给tab,并判定tab是否为空,这里的table就是哈希表,因为HashMap是基于哈希表的Map接口的实现,如果哈希表为空则调用resize()方法开发存储空间并赋值给tab,然后将tab的长度赋值给n。接着根据 (n - 1) & hash 算法盘算出i并获取tab的第i个元素,如果没有值,那么可以直接存入,如果有值,那么就存在两种情况:

  • hash值重复
  • 位置冲突
也就是说,如果在添加过程中发现key值重复,那么就把p复制给e,p为当前位置上的元素,e为需要被修改的元素。而位置冲突又分为几种情况:

  • 产生位置冲突时,table数组下面的结点以单链表的形式存在,插入结点时直接放在链表最末位
  • 产生位置冲突时,key值和之前的结点一样
  • 产生位置冲突时,table数组下面的结点以红黑树的形式存在,插入结点时需要在树中查找合适位置
那么根据这三种情况,需要分别作出判定:如果p是TreeNode的实例(p instanceof TreeNode),说明p下面挂着红黑树,需要在树中找到一个合适的位置e插入。如果p下面的结果数没有超过8,则p就是以单向链表的形式存在,然后在链表中逐个往下找到空位置;如果超过了8,就要将p转换为红黑树;如果与单向链表上的某个结点key值相同,则跳出循环,此时e是需要修改的结点,p是e的前驱结点。最后就是判定插入后的大小,如果大于threshold,则继续申请空间。
那么这是jdk1.8之后的关于HashMap的存储方式,也就是数组 + 链表 + 红黑树的结构,而在1.8之前,HashMap是由数组 + 链表的结构作为存储方式的。 所以HashSet如何保证元素是唯一的呢?关键就在于这一句判定:
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))复制代码它先看hashCode()值是否相同,如果相同,则继续看equals()方法,如果也相同,则证明元素重复,break跳出循环,元素不添加,如果不相同则进行添加。所以当一个自定义的类想要正确存入HashSet集合,就应该去重写equals()方法和hashCode()方法,而String类已经重写了这两个方法,所以它就可以把相同的字符串去掉,只保留此中一个。
那我们继续看下面的一个例子: 自定义学生类
public class Student {        private String name;        private int age;                public Student(String name, int age) {                this.name = name;                this.age = age;        }                public String getName() {                return name;        }        public void setName(String name) {                this.name = name;        }        public int getAge() {                return age;        }        public void setAge(int age) {                this.age = age;        }                @Override        public String toString() {                return "Student [name=" + name + ", age=" + age + "]";        }}复制代码然后编写测试代码:
        HashSet hs = new HashSet();        //添加元素        Student s = new Student("刘德华",30);        Student s2 = new Student("陈奕迅",31);        Student s3 = new Student("周星驰",32);        Student s4 = new Student("刘德华",30);                hs.add(s);        hs.add(s2);        hs.add(s3);        hs.add(s4);        //遍历        for (Student student : hs) {                System.out.println(student);        }复制代码在上述代码中,s4和s对象的姓名和年事都相同,按理说这是两个相同的对象,是不能同时在HashSet集合中存在的,然而我们看运行结果:
Student [name=周星驰, age=32]Student [name=刘德华, age=30]Student [name=陈奕迅, age=31]Student [name=刘德华, age=30]复制代码如果前面的源码分析大家都理解了的话,这个信赖大家就能明白,这是因为我们没有去重写hashCode()方法和equals()方法,而它默认就会去调用Object的方法,所以它会以为每个学生对象都是不相同的。那我们现在来重写一下这两个方法:
        @Override        public int hashCode() {                return 0;        }        @Override        public boolean equals(Object obj) {                //添加了一条输出语句,用于显示比力次数                System.out.println(this + "---" + obj);                if (this == obj) {                        return true;                }                if (!(obj instanceof Student)) {                        return false;                }                Student s = (Student) obj;                return this.name.equals(s.name) && this.age == s.age;        }复制代码然后我们运行步伐:
Student [name=陈奕迅, age=31]---Student [name=刘德华, age=30]Student [name=周星驰, age=32]---Student [name=刘德华, age=30]Student [name=周星驰, age=32]---Student [name=陈奕迅, age=31]Student [name=刘德华, age=30]---Student [name=刘德华, age=30]Student [name=刘德华, age=30]Student [name=陈奕迅, age=31]Student [name=周星驰, age=32]复制代码可以看到,虽然去除了重复元素,但是比力的次数未免过多,因为hashCode()方法返回的是一个固定值0,所以在进行判定的时候hashCode值永远相同从而多次调用equals()进行判定,那么我们就可以尽可能地使hashCode值不相同,那么哈希值和哪些内容干系呢? 因为它和对象的成员变量值干系,所以我们可以进行如下步调: 如果是根本范例变量,直接加值; 如果是引用范例变量,加哈希值。 所以对hashCode()作如下修改:
@Overridepublic int hashCode() {        //为了避免某种偶合导致两个不相同的对象其盘算后返回的hashCode值相同,这里对根本范例age进行一个乘积的运算        return this.name.hashCode() + this.age * 15;}复制代码现在运行看效果:
Student [name=刘德华, age=30]---Student [name=刘德华, age=30]Student [name=周星驰, age=32]Student [name=刘德华, age=30]Student [name=陈奕迅, age=31]复制代码重复元素成功被去除,而比力次数缩减为了一次,大大提升了步伐运行效率。
LinkedHashSet

它是具有可预知迭代顺序的 Set 接口的哈希表和链接列表实现,该集合方法全部继承自父类HashSet,但它与HashSet的唯一区别就是它具有可预知迭代顺序,它遵从存储和取出顺序是一致的。直接举例说明:
        LinkedHashSet linkedHashSet = new LinkedHashSet();        //添加元素        linkedHashSet.add("hello");        linkedHashSet.add("world");        linkedHashSet.add("java");        //遍历        for (String str : linkedHashSet) {                System.out.println(str);        }复制代码运行结果:
helloworldjava复制代码TreeSet

它是基于 TreeMap 的 NavigableSet 实现。使用元素的自然顺序对元素进行排序,或者根据创建 set 时提供的 Comparator 进行排序,详细取决于使用的构造方法。 举例说明:
        TreeSet treeSet = new TreeSet();        //添加元素        treeSet.add(10);        treeSet.add(26);        treeSet.add(20);        treeSet.add(13);        treeSet.add(3);        //遍历        for(Integer i : treeSet) {                System.out.println(i);        }复制代码运行结果:
310132026复制代码由此可见,TreeSet是具有排序功能的。但请注意,如果使用无参构造创建TreeSet集合,它将默认使用元素的自然排序;当然你也可以传入比力器来构造出TreeSet。 那么它是如何实现元素的自然排序的呢?我们通过源码来分析一下: 首先看它的add()方法
public boolean add(E e) {    return m.put(e, PRESENT)==null;}复制代码方法内部调用了m对象的put()方法,而这个m是一个NavigableMap对象:
private transient NavigableMap m;复制代码当我们继续跟进put()方法的时候,发现它是一个抽象方法:
V put(K key, V value);复制代码该方法处于Map接口中,那么我们就要去找Map接口的实现类,我们知道,TreeSet是基于TreeMap实现的,所以我们以为它调用的其实是TreeMap的put()方法,查阅TreeMap的继承结构也可以证实这一点:
java.util 类 TreeMapjava.lang.Object  继承者 java.util.AbstractMap      继承者 java.util.TreeMap范例参数:K - 此映射维护的键的范例V - 映射值的范例所有已实现的接口: Serializable, Cloneable, Map, NavigableMap, SortedMap 复制代码TreeMap确实也实现了NavigableMap接口,那我们就来看一看TreeMap的put()方法:
        public V put(K key, V value) {        Entry t = root;        //创建树的根结点        if (t == null) {            compare(key, key); // type (and possibly null) check            root = new Entry(key, value, null);            size = 1;            modCount++;            return null;        }        int cmp;        Entry parent;        // split comparator and comparable paths        Comparator
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

猜你喜欢
在线客服QQ
2241998733

24x7小时免费咨询

Powered by 创意电子 ©2018-现在 专注资源实战分享源码下载站联盟商城繁体中文