创意电子

标题: 深入Java源码剖析之Set集合 [打印本页]

作者: 小心程序猿QAQ 时间: 2021-8-17 20:34
标题: 深入Java源码剖析之Set集合
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

欢迎光临创意电子 (https://wxcydz.cc/) Powered by Discuz! X3.4