1. Set 接口和 Colleection 接口一样
2. 元素无序，不可重复， 可以包含但只能包含一个null，
2.1 虽然添加和取出的顺序不一致，但是取出的顺序是恒定不变的
3. 遍历： 不能用普通for循环，因为无序
1. Iterator
2. 增强for
二、HashSet
1. 重复元素
是通过元素的hashcode和equals方法共同决定的
package com.erick.feature.collection.d02;
import java.util.HashSet;
import java.util.Set;
public class Demo02 {
public static void main(String[] args) {
Set set = new HashSet();
System.out.println(set.add(new Dog("tom")));//ok
System.out.println(set.add(new Dog("tom")));//ok
System.out.println(set.add("tom"));//ok
System.out.println(set.add("tom"));//no
System.out.println(set.add(new String("jack")));//ok
System.out.println(set.add(new String("jack")));//no
}
}
class Dog {
public Dog(String name) {
this.name = name;
}
private String name;
}
2. 模拟数组+双向链表
HashSet底层是HashMapHashMap底层是数组+链表或红黑树，数组类型是链表或红黑树达到一定的界限，就会将链表树化成红黑树
// 底层结构是HashMap
public HashSet() {
map = new HashMap<>();
}
package com.erick.feature.collection.d02;
import lombok.Setter;
public class Demo03 {
public static void main(String[] args) {
// 数组长度为16个
Node[] table = new Node[16];
Node first = new Node(null, "erick");
Node second = new Node(null, "jack");
Node third = new Node(null, "tom");
// 挂载
first.setNext(second);
second.setNext(third);
table[2] = first;
table[3] = new Node(null, "cat");
}
}
class Node {
public Node(Node next, String item) {
this.next = next;
this.item = item;
}
@Setter
private Node next;
private String item;
}
3. HashSet添加元素
- HashSet底层是 HashMap
1. 添加一个元素时，先通过元素的hashCode得到元素hash值，转换成索引值(索引值和hash值是不同的)
索引值会决定该元素存放在数组中的哪个位置
2. 找到存储数据的table数组，看该索引位置是否已经存放了元素
2.1 如果没有，则直接加入
2.2 如果有，则用添加元素对象的equals方法和已经存在的，链表的前面的元素依次比较
相同，则放弃添加
不同，则该新元素就会添加在table表该索引除后面（链表）
# 1. 添加方法
添加的所有的元素，如果hash值相同，但是equals不同，就会放在数组的同一个索引位置
通过链表的方式来添加
获取元素的时候，也会从链表中去取数据
# 2. Java8 扩容机制
- 一条链表的元素个数 >= TREEIFY_THRESHOLD(默认是8),并且
table的大小>= MIN_TREEIFY_CAPACITY(默认是64)，链表为了增加性能，
就会树化成红黑树
- 如果链表个数达到了，但是table长度没达到，table就会先进行扩容
- table数组长度默认是16，通过0.75的加载因子，当数组长度到达16*0.75
的时候，就会进行2倍扩容，后续继续按照24*0.75进行扩容
4. HashSet源码解读
4.1 add初步
1. 底层是hashmap
public HashSet() {
map = new HashMap<>();
}
2. dummy值填充key，所有的value都是这个dummy值
private static final Object PRESENT = new Object();
public boolean add(E e) {
// 返回结果为空，代表添加成功
return map.put(e, PRESENT)==null;
}
3. 加入到map中
3.1 添加元素
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
3.2 hash的时候，如果key为null，则hash为0
- 否则就会用对象的hashcode加上无符号右移16位，避免hash碰撞几率
- hash并不等于hashcode，hash决定元素放在数组的哪个索引位子
- null元素就会放在第一位
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
4.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 {
// 暂时忽略
// 如果添加失败，则返回一个oldvalue，下面的都不会执行
}
// 修改次数加1，防止并发修噶
++modCount;
if (++size > threshold)
resize();
// 空方法，来让HashMap的子类实现，比如有序
// 模版方法模式
afterNodeInsertion(evict);
// 添加成功后，返回null
return null;
}
4.2 添加第二个能添加进去的元素
如果hascode的索引值和之前元素重复，但是equals不同，就会在该索引的后续链表继续加如果hascode的索引值和之前元素不重复，就会在新索引的位置添加 4.3 添加hashcode和equals相同的元素
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;
// 如果满足下面的两个条件，就不会添加
// 1. 当前索引位子的hash和新添加元素的hash相同
// 2. 当前索引位子的key和新添加元素的key相同，或者key通过equals相同
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 {
// table对应的索引位置，已经是一个链表，使用for循环比较
* 1. 依次和该链表的每一个元素比较，都不相同，则加入到链表的最后
* 如果相同了，就break
*
* 2. 在链表的最后，如果节点个数超过了8个，就会对该链表进行红黑树树化
* 2.1 树化的条件：该链表个数达到8个，并且table表超过64个，
* 2.2 如果table表没有超过64，则先对table表进行扩容
* 2.3 table表一般默认是16个，由HashMap无参构造器来完成
* 2.4 扩容的时候，是按照16*加载因子来扩容
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;
}
5. HashSet扩容机制
1. HashSet底层是 HashMap 2. 第一次添加时候，table数组扩容到16，临界值是16*0.75（加载因子） 3. 后续如果达到临界值(该table的所有的节点的元素个数总和)，就会扩容 # 扩容场景一 - 如果table数组使用到了12，就会扩容到16*2=32，新的临界值就是32*0.75 # 扩容场景二 - java8中，如果一条链表的元素个数达到8个，并且table大小达到64个 就会对该链表进行树化(红黑树)， 《否则仍然采取数组扩容机制》 16*2 # 1.刚开始数组长度为16， # 2. 在数组某个索引上，先添加7个元素，到达第八个时候，数组扩容为32， # 3. 添加第9个的时候，数组扩容为64， # 4. 添加第10个的时候，就会将该链表 进行树化 # 扩容场景三 - table数组的所有节点的元素数量总和达到12， 就会扩容6. HashSet最佳实践
对象如果要在HashSet或者HashMap中存储时，一定要重写hashcode和equals方法 7. Hash碰撞问题
一个对象，如果不同，最好落在不同的table的数组里面所以尽可能的不要让多个对象出现在一个链表避免过热或者过冷的问题 7.1 对象自定义hashcode的时候 7.2 HashSet在算hash值的时候
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
三、linkedHashSet
