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; }
