-
【JavaSE】Set接口--深入源码解读HashSet与LinkedHashSet
💁 个人主页：黄小黄的博客主页
❤️ 支持我：👍 点赞 🌷 收藏 🤘关注
🎏 格言：All miracles start from sometime somewhere, make it right now.
本文来自专栏：JavaSE从入门到精通
写在前面
Hello，我是黄小黄同学！今天继续JavaSE的学习。本篇内容为单列集合中的
HashSet与LinkedHashSet。实验环境为 jdk-1.8。
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); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
需要注意的是，虽然添加的顺序是无序的，但是取出的顺序始终是一致的，比如我们尝试取出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; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
发现，由于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; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
对代码进行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
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
步骤详解：
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; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
这里补充上述源码使用到的
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
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
5️⃣ 第二次执行
add方法时，得到哈希值后还是执行的putVal()方法。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不是null，所以这里的if不会进去 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 3. 根据key得到的hash值，计算key应该存放到table表的哪个索引位置 // 并把这个位置的对象赋值给p，然后判断p是不是为null if ((p = tab[i = (n - 1) & hash]) == null) // 3.1 第二次执行add方法，因为传入的值和第一次不一样，并且hash计算后 // 存放第二次传入的值是table中的另一个索引值，所以也会走这一步 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; } } // 4. 表示修改次数+1 ++modCount; // 5. 如果加入后的元素是否大于临界值，如果大于，进行扩容 if (++size > threshold) resize(); // 6. 这个方法是留给HashMap子类实现的，比如LinkedHashMap，但是对于HashMap来说是一个空方法 afterNodeInsertion(evict); // 7. 返回null，表示添加成功，如果不成功，返回的是旧的值(已经加进来的对象) return null; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
6️⃣ 重点又来啦！ 当第三次执行
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不是null，所以这里的if不会进去 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 3. 根据key得到的hash值，计算key应该存放到table表的哪个索引位置 // 并把这个位置的对象赋值给p，然后判断p是不是为null // 因为存入的是同一个对象，所以算出的hash值和索引值也是一样的， // 因此这里的p不为null if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; // 如果当前索引位置对应的链表的第一个元素和准备添加的 key 的 hash值 一样 // 并且满足以下两点之一，则不会添加： // (1)准备加入的 key 和 p 指向的Node结点的 key 是同一对象； // (2)p 指向的Node结点的 key 的equals() 和准备加入的key进行比较相同。 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 如果不相等的话，判断p是不是一颗红黑树，如果是的话将此节点添加到树里 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 如果table对应的索引已经是一个链表 // 使用for循环遍历链表，并且与传入的对象比较，如果发现相等，立刻跳出循环。 // 如果都不相等，将该对象放在链表的末尾，然后跳出循环 else { for (int binCount = 0; ; ++binCount) { // 判断当前节点的下一个节点是否有指向，没有的话创建对象，并存入 // 这里 e 就是下一个节点对象(第一次循环指向第二个节点，第二次指向第三个节点) if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 加入后 判断链表的节点是否大于等于成为红黑树的临界点 // TREEIFY_THRESHOLD的值是8，也就是说当前链表节点有八个 // 达到八个时，就将当前链表进行树化，当前链表，不是所有 // 在转成红黑树时，会再进行一个判断：table的长度要等于64时 // 这个判断是在treeifyBin(tab, hash);方法中判断的 // 如果不等于64，会先扩容，所以，转成红黑树有两个条件：table长度等于64，当前链表节点数大于等于8 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 如果不为null，则比较两个对象是否相等，相等的话直接跳出 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; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } // 4. 表示修改次数+1 ++modCount; // 5. 如果加入后的元素是否大于临界值，如果大于，进行扩容 if (++size > threshold) resize(); // 6. 这个方法是留给HashMap子类实现的，比如LinkedHashMap，但是对于HashMap来说是一个空方法 afterNodeInsertion(evict); // 7. 返回null，表示添加成功，如果不成功，返回的是旧的值(已经加进来的对象) return null; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
🅰️ 小结：
① HashSet底层是HashMap，第一次添加时，table数组扩容至16，临界值(threshold)是 16 * 加载因子(loadFactor)是 0.75 = 12
② 如果table数组使用到了临界值(12)，就会扩容到16 * 2 = 32，新的临界值就是 32 * 0.75 = 24，以此类推
③ table扩容是根据size的大小扩容的，不是链表的个数。该size可以认为是成功添加到set中的元素个数；
④ 在Java8中，如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8)，并且table的大小 >= MIN_TREEIFY_CAPACITY(默认是64)，就进行树化(红黑树)，否则仍然采用数组扩容机制。
3 LinkedHashSet解读
3.1 LinkedHashSet说明
在HashSet下面有一个子类
java.util.LinkedHashSet，LinkedHashSet底层是LinkedHashMap，它是 双向链表和数组 组合的一个数据存储结构。
LinkedHashSet根据元素的hashCode值来决定元素的存储位置，同时使用链表维护元素的次序，所以使得元素看起来是有序保存的（插入顺序）。3.2 双向链表+数组的数据结构
🐱 示例代码如下：
import java.util.LinkedHashSet; import java.util.Set; /** 1. @author 小黄小黄不再迷茫 2. @version 1.0 */ public class LinkedHashSetTest { public static void main(String[] args) { Set set = new LinkedHashSet(); set.add(new String("AA")); set.add(1); set.add(2); set.add(3); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
🦁 维护的数据结构示意图：
说明：- 在 LinkedHashSet 中维护了一个 hash表 和 双向链表（有head和tail）；
- 每个结点都有 before 和 after 属性，用于构成双向链表；
- 在添加一个元素时，先求 hash值 ，再求索引。确定该元素在 hashtable 中的位置，然后将添加的元素加入到双向链表(重复则不添加，规则与hashset一样)；
- 遍历LinkedHashSet能保证插入顺序和遍历顺序一样。
3.3 LinkedHashSet底层创建扩容机制源码解读
-
LinkedHashSet 加入顺序和取出元素/数据的顺序一致；
-
LinkedHashSet 底层维护的是一个LinkedHashMap(是HashMap的子类)，底层结构 (数组table+双向链表)；
-
添加第一次时，直接将 数组table 扩容到 16 , 存放的结点类型是
LinkedHashMap$Entry；
-
数组是
HashMap$Node[]存放的元素/数据是LinkedHashMap$Entry类型; -
继承关系是在内部类完成的，源码如下图：
🅰️小结：
① LinkedHashSet加入顺序和取出顺序是一致的
② LinkedHashSet底层维护的是LinkedHashMap(是HashMap的子类)
③ LinkedHashSet底层是 数组table+双向链表
④ 当第一次添加元素时，会直接将数组(table)扩容到16，存放的节点类型是LinkedHashMap$Entry
⑤ 底层的数组(table)是HashMap$Node类型的，LinkedHashMap$Entry是HashMap$Node的子类。
⑥ 当调用LinkedHashSet的add方法时，执行的是父类的HashSet的add方法，而HashSet的add方法执行的是HashMap的put方法。
写在最后
🌟以上便是本文的全部内容啦，后续内容将会持续免费更新，如果文章对你有所帮助，麻烦动动小手点个赞 + 关注，非常感谢 ❤️ ❤️ ❤️ !
如果有问题，欢迎私信或者评论区！
共勉：“你间歇性的努力和蒙混过日子，都是对之前努力的清零。”
-
相关阅读:
K8S访问控制------认证（authentication ）、授权（authorization ）体系
FreeRTOS基础（如何学好FreeRTOS？）
C++ 纯虚类实例化中对于引用成员的使用
✔ ★ 算法基础笔记（Acwing）（三）—— 搜索与图论（17道题）【java版本】
Pigsty：开箱即用的数据库发行版
为什么越来越多的人喜欢从事软件测试行业？
Spring Cloud Gateway 中文文档
整理Ubuntu深度学习服务器初始化操作
第4讲：vue内置命令（文本插值，属性绑定，v-text,v-html）
洛谷 P2486 [SDOI2011]染色
- 原文地址：https://blog.csdn.net/m0_60353039/article/details/125940395
