set接口基本介绍
- 无序(添加和取出的顺序不一致),没有索引
- 不允许重复元素,所有最多包含一个null
HashSet
- HashSet实现了Set接口
- HashSet实际上是HashMap
HashSet细节
set.add("jack"); true
set.add("jack"); false
set.add(new Cat("tom")); true
set.add(new Cat("tom")); true
//重点
set.add(new String("hello")); true
set.add(new String("hello")); false
HashSet底层是HashMap,添加一个元素时,先得到hash值,会转成索引值,找到存储数据表table,看这个索引的位置是否已经存放有元素,如果没有就直接加入,如果有,就调用equals比较,如果相同就放弃添加,如果不同就添加到此链表后面,在Java8中如果一条连链表个数等于默认值8,并且table>=64 就转换成红黑树
执行过程:
- 执行 HashSet()
public HashSet() {
map = new HashMap<>();
}
- 执行 add()
public boolean add(E e) {
return map.put(e, PRESENT)==null;
//private static final Object PRESENT = new Object();
}
- 执行 put(),该方法会执行hash(key) 得到key对应的hash值(h = key.hashCode()) ^ (h >>> 16)
public V put(K key, V value) { //key="java" value = PRESENT
return putVal(hash(key), key, value, false, true);
}
- 执行 putVal()
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0) //table就是存放节点的数组
n = (tab = resize()).length;
//根据key,得到hash去计算该key应该存到table表的哪个索引位置
//并把这个位置的对象赋给p
//判断p是否为null,如果为空表示还没有存放元素,就创建一个node放在末尾
if ((p = tab[i = (n - 1) & hash]) == 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)))) //如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样 ,准备加入的key和p指向的Node节点是同一个对象,或者不是同一个对象,但是内容相同
e = p;
//再判断 p 是不是一颗红黑树,
//如果是一颗红黑树,就调用 putTreeVal,来进行添加
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { //如果table对应索引位置,已经是一个链表,就依次比较
//(1)依次和该链表的每个元素比较后,都不相同,就使用for循环比较,把元素添加到链表后,立即判断是否达到8个节点,如果达到就调用treeifyBin()对当前列表进行树化(红黑树)。在转成红黑树时,还进行判断,如果该table数组大小 小于64先扩容,否则转成红黑树
//(2)在比较的过程中,有相同情况就break
//
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;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
HashSet的扩容
- 底层的HashMap,第一次添加时,table数组扩容到16,临界值(threshold)是16 * 加载因子 (loadFactor)是0.75 = 12
- 如果table数组使用到了临界值12,就会扩容到16 * 2 = 32,新的临界值就是32 * 0.75 = 24,依次类推
- 在java8中,如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8),并且table的大小>=MIN_TREEIFY_CAPACITY(模拟64),就会进行树化(红黑树),否则仍然采用数组进行扩容机制