2021-10-04

Java集合之Set去重引言：

有关于Java集合类你知道哪些？他们各自有什么特征？应用场景为何？

本文以面试题来展开，并以实际编码查看源码来解释。

题目：

Set的特征是什么，应用场景是什么？

Set的去重是怎么做到的？

Set是否能对对象去重？

如何实现Set对对象的去重？

1. Java集合之Set

先来看一段代码，然后思考一个问题：

有一个Person类，里面有两个字段，那么和address，对外提供了get，set方法：

class Person {
    private String name;
    private String address;

    public String getName() {
        return name;
    }

    public Person setName(String name) {
        this.name = name;
        return this;
    }

    public String getAddress() {
        return address;
    }

    public Person setAddress(String address) {
        this.address = address;
        return this;
    }
}

然后有一个MainTest类，里面有一个Person的集合personSet，add四个一样内容的person对象:

public class MainTest {
    public static void main(String[] args) {
        Set personSet = new HashSet<>();
        personSet.add(new Person().setName("张三").setAddress("上海"));
        personSet.add(new Person().setName("张三").setAddress("上海"));
        personSet.add(new Person().setName("张三").setAddress("上海"));
        personSet.add(new Person().setName("张三").setAddress("上海"));
        System.out.println(personSet.size());

    }
}

那么问题来了，控制台打印出来的personSet.size()是几呢？这里提供两个答案：

a. 1: 原因是set再保存数据时会进行去重的操作，由于四个对象的内容是一样的，所以只保存了一个对象，所以答案是1

b. 4：原因是每次add操作都是new的新的对象，在内存中是四个内存空间，四个地址，所以在add操作时实际上时比较的对象的地址值，所以答案是4

所以正确答案是几呢？让我们运行一下，感兴趣的同学也可以在自己的电脑是试一下：

好，答案是4。接下来问题来了，不是说set集合是可以去重吗，为什么这里没有实现去重的操作，我要如何才能实现对对象的去重操作呢？

接下来再看一段代码，这里对Perspon类做了一些调整，使用了lombok插件，这里注释掉了我们自己写的get，set方法，添加了@Data的注解和一个链式加载的注解：

@Data
@Accessors(chain = true)
class Person {
    private String name;
    private String address;


}

好，我们再来看一下这一次的运行结果又是怎么样的呢？

好的，现在的答案是1，为什么又是1了呢，为什么就实现了对象的去重了呢？

我们先往下进行第一层的探索：

这里我们使用了lombok插件的注解，所以再代码编译时会添加一些处理代码，我们拿到生成的Person.class文件，然后反编译一下，看一下跟我们原始的Person类有什么不同，这里直接把反编译的代码放到下面：

//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by FernFlower decompiler)
//

package com.trademesh.service.oms.service;

class Person {
    private String name;
    private String address;

    public Person() {
    }

    public String getName() {
        return this.name;
    }

    public String getAddress() {
        return this.address;
    }

    public Person setName(String name) {
        this.name = name;
        return this;
    }

    public Person setAddress(String address) {
        this.address = address;
        return this;
    }

    public boolean equals(Object o) {
        if (o == this) {
            return true;
        } else if (!(o instanceof Person)) {
            return false;
        } else {
            Person other = (Person)o;
            if (!other.canEqual(this)) {
                return false;
            } else {
                Object this$name = this.getName();
                Object other$name = other.getName();
                if (this$name == null) {
                    if (other$name != null) {
                        return false;
                    }
                } else if (!this$name.equals(other$name)) {
                    return false;
                }

                Object this$address = this.getAddress();
                Object other$address = other.getAddress();
                if (this$address == null) {
                    if (other$address != null) {
                        return false;
                    }
                } else if (!this$address.equals(other$address)) {
                    return false;
                }

                return true;
            }
        }
    }

    protected boolean canEqual(Object other) {
        return other instanceof Person;
    }

    public int hashCode() {
        int PRIME = true;
        int result = 1;
        Object $name = this.getName();
        int result = result * 59 + ($name == null ? 43 : $name.hashCode());
        Object $address = this.getAddress();
        result = result * 59 + ($address == null ? 43 : $address.hashCode());
        return result;
    }

    public String toString() {
        return "Person(name=" + this.getName() + ", address=" + this.getAddress() + ")";
    }
}

从上面代码中，我们发现代码比我们自己编辑的代码多了很多，主要有：

帮我们生成了get，set方法
添加了equals方法，hash方法和toString方法

所以究竟是哪个改变使得帮助我们的对象可以实现set的去重操作呢？肯定不是get,set，也不是toString，见名知意，这里猜测是equals，然后我们怎么验证呢？这就要去看我们的set的add方法了，接下来我们看一下Set的源码。

我们这里使用的是Set的实现类HashSet，直接来查看对应的add方法，这里也将英文注释做了翻译供同学们参考：

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

等等，不知道有没有同学发现，这里为什么是map.put操作？map是什么，跟map有什么关系，一起看看这个map是个啥东东：

好家伙，这里面竟然是一个HashMap，所以HashSet的实现原来是个HashMap呀，そうですね（sou dei si nai）

那我们就要继续往下看一下HashMap的put操作了，上吧，勇敢往前冲

接下来我们来到了HashMap的列车上，直接上代码吧，这里把官方的注释翻译了一下，相信能看到这里你已经蠢蠢欲动（昏昏欲睡）了：

这里调用了putVal方法，将前面传入的e和PRESENT作为key和value使用，接下来上本文中的重点，putVal()

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node 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 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)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;
    }

完了，晕死，卒…

等等，看这个尸体，他还在动，哇，这个尸体诈尸啦，扶朕起来，朕还能干

2 minutes later…

好，接下来我们简单分析下这个方法的操作，注意，简单分析~~

	    Node[] tab; Node 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);

首先判断该table是否为空，如果为空，则代表还没插入元素，然后计算元素应该存储到在数组的下标（HashMap底层的额实现是数组+链表+红黑树。在本文不做设方面的探究，默认使用）

查看对应数组下标是否保存了元素，没有为空，则直接新建一个新的Node存放我们要保存的对象

如果对应下标的位置已经有元素了，则接下来就是下面一段的逻辑了

	else {
            Node 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)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;
            }
        }

至于以上这一段代码，需要一点点品了，这里就不品了。大概的意思就是根据key的hash值判断是否已存在，如果已存在则进一步判断key是否相同，如不同则记录为新的元素添加，如果一样则表示已存在则不添加。

总的来讲，Java1.8 HashMap的put操作流程如下图所示：

接下来我们debug一下：

这里把断点搭载第一次add操作上，然后执行debug运行

到这里就完成了第一个元素的添加工作，接下来我们继续debug，看一下第二次add的场景，这一次两次if判断都不成立，执行else里面的操作:

到此就基本结束了，由于hash值一样并且key是一样的(说明一下，我们使用的HashSet存放的数据，Key实际上才是我们存放的对象，value就是一个Object对象)，所以这里最终生成的Set仅保存了一个对象。每次用于比较的是hash值，所以这里是由于重写了hashCode和equals方法实现了值比较，而非简单的对象地址值比较，完成了对象的去重操作。

最后验证一下，我们把Person类改一下，重写hashCode和equals方法再测试

@Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Person)) return false;
        Person person = (Person) o;
        return Objects.equals(name, person.name) && Objects.equals(address, person.address);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, address);
    }

最终的运行结果也可以看到是1

2021-10-04

Java相关栏目本月热门文章