Set集合源码解析 Set集合源码解析

HashSet
特点

允许元素为null
元素不可重复
hashmap(数组+链表+红黑树)
不安全

扩容机制 hashset本质就是使用hashmap作为底层的结构，这里就直接介绍hashmap扩容机制

如果使用无参构造创建hashset，则第一次执行add操作，会直接初始化一个长度为16的数组，且根据16x0.75的加载因子，会得到一个临界值12，也就是说，这个临界值在后面是真正触发扩容的值，我不等到你满了才扩容，而是当集合元素达到-当前容量*0.75=临界值，去触发扩容，且每次扩容是以2倍的增长,并且计算出临界值。
临界值=当前容量*0.75，这个临界值，不是指的hashmap数组的大小，而是这个集合的大小，hashmap内有一个table数组，而这个数组内的每个下标（索引/元素与）都可能存在链式节点，如果每个链式节点元素/数组的长度大于12，就会触发扩容。
当集合内的元素未达到临界值时，如果这个数组中的某一个节点的链式节点元素>=7时，则会触发转换成红黑树，前提是，如果这个数组的长度达到64个长度，如果未到64个长度，则会再次扩容，扩容机制为--当前数组长度的二倍，并且计算出临界值，当临界值被触发，一样会触发扩容机制，如果这个链式节点>=7,且数组的长度达到64，则会将这一个节点转化为红黑树
解析1.初始化HashSet
1.1 从源码得知，hashset进行初始化，实际上是初始化了一个hashMap。

/** * Constructs a new, empty set; the backing HashMap instance has * default initial capacity (16) and load factor (0.75). */ public HashSet() { map = new HashMap<>(); }

2.初始化集合后，进行第一次add操作。

public boolean add(E e) { // 此时，则调用hashmap的put,进行put操作 // 而PRESENT为全局共享的最终的常量，所以，hashset每次的add，都是进行put操作，key为新增元素的值，value始终是PRESENT // private static final Object PRESENT = new Object(); return map.put(e, PRESENT)==null; }

2.1 根据元素的hash后的值，获得数组的索引

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

【Set集合源码解析】2.2 判断元素是否已经存在，是否需要进行扩容，是否是红黑树结构，是否是链表。

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 = https://www.it610.com/article/e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size> threshold) resize(); afterNodeInsertion(evict); return null; }