【JavaSE】Set接口--深入源码解读HashSet与LinkedHashSet(上)

简介: 文章目录写在前面1 Set接口与常用方法2 HashSet解读2.1 HashSet说明2.2 不可重复指什么?2.3 模拟数组 + 链表的结构2.4 HashSet底层机制源码解读3 LinkedHashSet解读3.1 LinkedHashSet说明3.2 双向链表+数组的数据结构3.3 LinkedHashSet底层创建扩容机制源码解读写在最后

1 Set接口与常用方法

🆔 Set接口基本介绍:


无序(即添加和取出的顺序不一致),且没有索引;

不允许重复元素,最多只能有一个null;

🦁 常用方法:

Set接口同List接口一样,都是Collection的子接口,常用方法与Collection接口一样。在下面的例子中我们尝试给Set实现类添加几个元素,来 说明Set集合元素的无序与不重复:

import java.util.HashSet;
import java.util.Set;
/**
 * @author 小黄小黄不再迷茫
 * @version 1.0
 */
public class SetTest01 {
    public static void main(String[] args) {
        Set set = new HashSet();
        set.add("黄小黄");
        set.add("马小淼");
        set.add("黄小黄");
        set.add("懒羊羊");
        set.add(null);
        set.add(null);
        System.out.println("set = " + set);
    }
}


需要注意的是,虽然添加的顺序是无序的,但是取出的顺序始终是一致的,比如我们尝试取出10次,发现每次顺序都一样:


2 HashSet解读

2.1 HashSet说明

HashSet实现了Set接口;

HashSet底层实际是HashMap,见图源码:


HashSet不保证元素是有序的,不能有重复元素或者对象。

2.2 不可重复指什么?

不可重复对象或元素究竟指什么?我们来看下面的例子:

import java.util.HashSet;
/**
 * @author 小黄小黄不再迷茫
 * @version 1.0
 */
public class HashSetTest {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add("黄小黄");
        hashSet.add("黄小黄");
        hashSet.add(new Person("马小淼"));
        hashSet.add(new Person("马小淼"));
        System.out.println("hashSet = " + hashSet);
    }
}
class Person{
    private String name;
    public Person(String name){
        this.name = name;
    }
}


发现,由于Person两个对象不同,因此都成功加入到了hashSet中。然而,这有个很大的Bug,来接着往后看:



在上述例子中,虽然两个String对象不同,但是只成功添加进了一个对象。这与之前的结论相矛盾,具体我们需要了解HashSet中的add方法的底层原理, 在了解底层原理前,有必要先来学习一下前置知识。


2.3 模拟数组 + 链表的结构

HashSet底层是HashMap,HashMap是由数组+链表+红黑树构成的。这样做的目的是使操作更加高效。


整体结构示意如下图:


简易代码实现如下:

/**
 * @author 小黄小黄不再迷茫
 * @version 1.0
 */
public class HashSetStructure {
    public static void main(String[] args) {
        Node[] hashTable = new Node[12];
        hashTable[1] = new Node("lingling", null);
        Node lucy = new Node("lucy", null);
        hashTable[1].next = lucy;
        hashTable[4] = new Node("cat", null);
        Node elephant = new Node("elephant", null);
        elephant.next = new Node("dog", null);
        hashTable[4].next = elephant;
    }
}
class Node{
    Object name;  // 存储信息
    Node next;  // 指向下一个节点
    public Node(Object name, Node next){
        this.name = name;
        this.next = next;
    }
}

对代码进行debug后,hashTable结构如下:



2.4 HashSet底层机制源码解读

🦁 在HashSet中当添加一个元素时:


先获取元素的哈希值(由hashCode方法决定);

对哈希值进行运算,得出一个索引值即要存放在哈希表中的位置;

如果该位置没有其他元素,则直接存放;

如果有其他元素,则先使用equals方法进行判断,若相等,则不再添加,否则,以链表的形式添加在后面;不能简单认为,equals比较的是内容,具体的依据程序员自己重写的equals而定;

在Java8中,如果一条链表的元素个数到达了TREEIFY_THRESHOLD(默认8),并且table的大小大于等于MIN_TREEIFY_CAPAITY(默认64),则树化为红黑树。

🐴 运行下面的代码,并通过debug分析源码:

import java.util.HashSet;
/**
 * @author 小黄小黄不再迷茫
 * @version 1.0
 */
public class HashSetTest {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add("黄小黄");
        hashSet.add("马小淼");
        hashSet.add("黄小黄");
        System.out.println("set=" + hashSet);
    }
}

步骤详解:

1️⃣ 当执行第一行的创建hashSet对象时,执行无参构造器,其实是创建了一个HashMap对象。



2️⃣ 执行add方法时,底层会调用HashMap对象的put方法。put方法的key就是传入的值e,类型为泛型E,而value是常量PRESENT。



因为Map集合是以 key | value 的形式存储的,这里的value,主要起占位的作用,是为了让HashSet使用到HashMap,没有实际特殊意义。PRESENT的声明如下,该属性为静态常量,也就是在每次put时,key可能不同,但是充当占位符的PRESENT不变:



3️⃣ 继续探讨hash()方法的执行逻辑,hash方法中会拿到传入对象的HashCode值,并进行方法中算法:如果key为0,则返回0;否则将h无符号右移16位并计算出key对应的hash值,返回key对应的hash值(不等价HashCode值)。为的是哈希值不一样,以免发生碰撞。



4️⃣ 重点来啦! 在计算完hash值后,接着就会执行putVal()方法,该方法是add方法的核心。具体解释已经在源码中给出了注释:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // 1. 定义辅助变量
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 2. table是HashMap的一个属性,是一个Node类型的数组,类似于上面实现“链表+数组”结构的table
    // 3. 在执行第一个add方法时,table还没有初始化,所以table的值为null,会进入第一个if中
    if ((tab = table) == null || (n = tab.length) == 0)
      // 4. 走到这里,会执行一个resize()方法,介绍在补充里
      // 将得到的数组对象赋值给tab,并且将数组的长度赋值给n
        n = (tab = resize()).length;
    // 5. 根据key得到的hash值,计算key应该存放到table表的哪个索引位置
    // 并把这个位置的对象赋值给p,然后判断p是不是为null
    if ((p = tab[i = (n - 1) & hash]) == null)
      // 5.1 如果p为空,说明table的该索引位置没有元素,直接存入该索引位置即可
      // key就是要存入的元素,value就是占位的Object对象,
      // 存hash的目的是为了进行后续存入的比较,最后一个null值,是下一个节点引用,现在还没有,所以为null
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> 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<K,V>)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;
        }
    }
    // 6. 表示修改次数+1
    ++modCount;
    // 7. 如果加入后的元素是否大于临界值,如果大于,进行扩容
    if (++size > threshold)
        resize();
    // 8. 这个方法是留给HashMap子类实现的,比如LinkedHashMap,但是对于HashMap来说是一个空方法
    afterNodeInsertion(evict);
    // 9. 返回null,表示添加成功,如果不成功,返回的是旧的值(已经加进来的对象)
    return null;
}

这里补充上述源码使用到的 resize() 方法的解读,总的来说第一次执行完该方法后,tab就变成了16大小:

final Node<K,V>[] resize() {
  // 1. 因为是第一次调用add方法添加元素,所以table还是null
    Node<K,V>[] oldTab = table;
    // 2. 所以这里oldCap的值为0 
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;
    }
    else if (oldThr > 0)
        newCap = oldThr;
    else {
      // 3. oldCap 值为0时,会进入这个else中,
      // 而 DEFAULT_INITIAL_CAPACITY 的值为16(1<<4)
        newCap = DEFAULT_INITIAL_CAPACITY;
        // newThr是临界值,加载因子 DEFAULT_LOAD_FACTOR 的值为0.75
        // 所以这里临界值的值为12,当table现在16的空间,用到12时,就准备扩容table的空间。防止操作量大的时候,没有缓冲。
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // 4. 根据得到的新空间,new一个对应空间的Node数组,并将对象赋值给属性table
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    // 5. 然后返回创建的数组对象
    return newTab;
}



相关文章
|
1月前
|
存储 Java 测试技术
滚雪球学Java(61):从源码角度解读Java Set接口底层实现原理
【6月更文挑战第15天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
30 1
滚雪球学Java(61):从源码角度解读Java Set接口底层实现原理
|
18天前
|
存储 安全 Java
详解Java中集合的List接口实现的ArrayList方法 | Set接口实现的HashSet方法
详解Java中集合的List接口实现的ArrayList方法 | Set接口实现的HashSet方法
|
1月前
|
存储 Java 索引
JavaSE——集合框架一(6/7)-Set系列集合:LinkedHashSet的底层原理、TreeSet集合(介绍,自定义排序规则,排序示例)
JavaSE——集合框架一(6/7)-Set系列集合:LinkedHashSet的底层原理、TreeSet集合(介绍,自定义排序规则,排序示例)
25 1
|
1月前
|
存储 Java 索引
JavaSE——集合框架一(5/7)-Set系列集合:Set集合的特点、底层原理、哈希表、去重复原理
JavaSE——集合框架一(5/7)-Set系列集合:Set集合的特点、底层原理、哈希表、去重复原理
34 1
|
2月前
|
存储 安全 Java
Java的List、Set、Queue等接口及其实现类的技术性文章
Java的List、Set、Queue等接口及其实现类的技术性文章
13 1
|
2月前
|
存储 安全 Java
Java list set map等接口及其实现类
Java list set map等接口及其实现类
|
2月前
|
存储 安全 Java
Java一分钟之-集合框架进阶:Set接口与HashSet
【5月更文挑战第10天】本文介绍了Java集合框架中的`Set`接口和`HashSet`类。`Set`接口继承自`Collection`,特征是不允许重复元素,顺序不确定。`HashSet`是`Set`的实现,基于哈希表,提供快速添加、删除和查找操作,但无序且非线程安全。文章讨论了`HashSet`的特性、常见问题(如元素比较规则、非唯一性和线程安全性)以及如何避免这些问题,并提供了代码示例展示基本操作和自定义对象的使用。理解这些概念和注意事项能提升代码效率和可维护性。
29 0
|
2月前
|
存储 安全 Java
Java集合篇之set,面试官:请说一说HashSet、LinkedHashSet、TreeSet的区别?
Java集合篇之set,面试官:请说一说HashSet、LinkedHashSet、TreeSet的区别?
23 0
|
2月前
|
存储 Java 索引
Java Set接口及其常用实现类详解
Java Set接口及其常用实现类详解
123 2
|
2月前
|
存储 安全 索引
容器【容器介绍、Set接口介绍、 HashSet容器的使用、TreeSet容器的使用】(三)-全面详解(学习总结---从入门到深化)
容器【容器介绍、Set接口介绍、 HashSet容器的使用、TreeSet容器的使用】(三)-全面详解(学习总结---从入门到深化)
22 0