Set接口常用方法
- 无序（即取出的顺序添加的顺序是不一致的，但是每次取出的顺序是一样的）底层是什么算法实现的这个功能呢？？？
- 没有索引
- 不允许重复元素
- 可以使用增强for和迭代器遍历
HashSet
怎么理解HashSet不能加入重复对象？？？
java
HashSet的底层实现其实是HashMap
//todo 调用的是HashMap的构造器
public HashSet() {
map = new HashMap<>();
}
可以放入null值，但是只能存放一个空值，元素不能重复案例一
结论：HashSet可以放入null值，不可以放重复元素
疑问：那么放入重复元素的时候，我们是用重复的新值覆盖掉原来的，还是直接舍弃新的重复元素呢？
java
//案例1
HashSet set=new HashSet();
set.add(null);
set.add(null);
set.add("");
set.add("");
set.add('a');
set.add('a');
/**
* [null, , a]
* [null, , a]
*/
System.out.println(set);
System.out.println(set);案例2
结论：加入的是两个对象，他们在HashSet眼里是不同的值
java
//案例2
set=new HashSet();
set.add(new Person("黎旭"));//T
set.add(new Person("黎旭"));//T
System.out.println(set);
System.out.println(set);//[Person{name='黎旭'}, Person{name='黎旭'}]案例3
疑问：为什么创建两个值相同的String对象，他们为什么又不能都添加进HashSet中呢？
java
//案例3
//为什么这里添加第二次添加String不成功呢？
set=new HashSet();
set.add(new String("lx"));//T
set.add(new String("lx"));//F
System.out.println(set);//[lx]HashSet底层结构
- hash值是怎么计算出来的呢？不同对象的hash值是不同，那为什么转化成索引的时候会出现hash冲突呢，hash值是怎么转换为索引值的？
java
//分析案例：
HashSet hashSet = new HashSet();
hashSet.add("java");
hashSet.add("php");
hashSet.add("java");
System.out.println(hashSet);//[java, php]源码分析：
java
1.调用HashMap的构造器(证实HashSet的底层实现就是HashMap)
// todo
public HashSet() {
map = new HashMap<>();
}java
2.调用add方法
//todo
public boolean add(E e) {//e:"java"
return map.put(e, PRESENT)==null;//PRESENT用来占位
}
//PRESENT是hashMap中的一个静态共享常量 private static final Object PRESENT = new Object();
- (1)如果返回值为空说明添加成功
- (2)返回值若为一个查询到的对象，说明添加失败java
3.执行put方法
这里调用了hash(key)函数,目的是求出key的hash值
//todo
public V put(K key, V value) {//k:"java" value:
return putVal(hash(key), key, value, false, true);
}java
4.进入hash函数 为非空对象计算出一个hash值，key与hash值对应
//hash值并不等价于hashCode
//算法 (h = key.hashCode()) ^ (h >>> 16)
//按位异或 无符号右移16位（避免冲突）
//todo
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}java
5.putVal方法
// todo
@para hash 根据key值计算出来的hash值
@para key 需要存放的key值 key:"java"
@para value 等于HashMap中的共享静态常量 value=PRESENT 用来占位
@para onlyIfAbsent false
@para evict true
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//临时变量
Node<K,V>[] tab; Node<K,V> p; int n, i;
//transient Node<K,V>[] table;table是HashMap中的一个Node数组
if ((tab = table) == null || (n = tab.length) == 0)
//(1)第一次扩容，调用的是resize方法 第一次扩容为 16 并且有一个加载因子0.75*16=12
//(2)当table已经添加了12个元素就会触发扩容
//(3)最后返回值resize的返回值是一个大小为16的Node数组
//(4)然后赋值给tab
n = (tab = resize()).length;
//(1)根据key计算出来的hash值去计算，此key应该存放在table表的哪个索引位置
//(2)并把这个位置的Node对象赋值给 p(Node类型)
// (2.1) 如果p=null 说明这个索引位置还没有放过任何元素
//
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//这个else里的代码是存在冲突时的代码逻辑，稍后再分析
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;
}
}
++modCount;
//判断此时table的数据量是不是大于扩容临界值
//大于临界值了就需要扩容了，那么就调用resize()
if (++size > threshold)
resize();
//此方法是HashMap中的空方法，用于给给子类实现
afterNodeInsertion(evict);//evict:true传进来的时候是true
return null;
}第一次添加数据到HashMap中
第二次添加数据，根据hash值算出的索引得到的对象也为null
，说明没有冲突
第三次添加数据“java"，发生冲突
这一次e不再为空，这里很复杂（看源码）
......前面的代码分析过程与没有发生冲突是一样的，这里主要看else{}里的代码逻辑 看看是如何处理冲突的
java
//(1)根据key计算出来的hash值去计算，此key应该存放在table表的哪个索引位置
//(2)并把这个位置的Node对象赋值给 p(Node类型)
// (2.1) 如果p=null 说明这个索引位置还没有放过任何元素
// (2.2) 如果不为空，说明这个索引位置有对象了，返回这个对象给 p
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//当前位置的对象 p 和准备新添加进来的对象的hash值相同
//&&并且
// (1) 当前位置的对象 p 和准备新添加进来的对象是同一个对象 == 比较的是地址
// (2) 当前位置的对象 p 和准备新添加进来的对象的值是一样的 equals比较的是值
// 先比较hash值，再比较是不是同一个对象，或者两个对象的值是否相等
// 因此其实思考一下可以发现不同的对象的hash值可能也会相同
// 而equals()常用于给程序员重写用来按不同的标准确定两个对象的等价关系
// 这也是为什么之前我们两次执行hashset.add(new String("lixu"))最终只添加了一次，这是因为String重写了equals
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 {
// 如果table对应的索引位置已经是一个链表，就for循环遍历每个节点
// (1)与每个节点对象比较都不同，则将此节点加入到链表尾部,break;
// (2)如果hash值相同，再比较是不是同一个对象，或者两个对象的值是否相等，就不添加，break;
//注意：
// - TREEIFY_THRESHOLD(8) 当前索引位置构成的链表长度已经达到8个就需要树化treeifyBin(tab, hash);
// - treeifyBin方法树化前会判断if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY
// MIN_TREEIFY_CAPACITY的值是(64) table数组的容量是否已经大于64了，大于64才会树化，否则就扩容resize();
// 所以并不是满足 链表长度已经达到8个就立马树化（并不是第九个）
for (int binCount = 0; ; ++binCount) {
//与每个节点对象比较都不同，则将此节点加入到链表尾部,break;
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果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的扩容机制
案例一：table的扩容机制
java
//案例1：查看扩容机制
for(int i=0;i<100;++i){
hashSet.add(i);
}java
//第一次添加数据扩容到 16
(1)调用resize方法，直接将预值 16 创建一个大小为16的table[Node]数组java
(2.1)当执行到添加第12个元素的时候会再次扩容，这是是在此处调用的resize()函数
//todo
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;java
(2.2)调用resize扩容，这次扩容是 将原来的table表空间进行2倍扩容
- (newCap = oldCap << 1) newCap是新的空间大小
- newThr = oldThr << 1; 同样的阈值也扩大为2倍java
(2.3)扩容之后底层创建了一个容量为之前两倍的newTab[Node]数组
并进行循环将之前的table数组中的数据赋值给新表
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];java
resize()源码
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
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; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
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"})
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;
}
}
}
}
}
return newTab;
}案例二：table树化
//案例2 链表化的table进化成树
/**
* 首先我们知道只有两个对象的hash值相同时，即发生了冲突
* 才会放在同一个索引下形成链表，所以我们自定义一个类并重写hashCode()
*/开始table为空
加入了第一个元素，扩容到16
一直添加到第七个元素，所有元素都添加在了第一个索引位置并构成了一个链表
再添加第8个元素，table扩容到了32，而且扩容后所有元素重新根据hash值算出一个索引
添加第九个元素，再次触发扩容，此时table的大小已经是64
再添加第10个元素，链表会进化成树，可以看到已经是一颗红黑树的结构了
LinkedHashSet
- LinkedHashSet是HashSet的子类
- LinkedHashSet底层是一个LinkedHashMap，底层维护了一个数组+双向链表，正是这个特点使得插入的元素是有序的。
- LinkedHashSet根据元素的hashCode值来决定元素的存储位置，同时使用链表维护元素的次序，所以元素的插入与取出顺序一致
- LinkedHashSet不允许添加重复元素
java
import java.util.LinkedHashSet;
public class LinkedHashSet_ {
public static void main(String[] args) {
LinkedHashSet linkedHashSet = new LinkedHashSet();
linkedHashSet.add("我");
linkedHashSet.add("是");
linkedHashSet.add("大");
linkedHashSet.add("帅哥");
linkedHashSet.add("帅哥");
linkedHashSet.add("帅哥");
System.out.println(linkedHashSet);
//[我, 是, 大, 帅哥]
}
}add源码分析
维护了一个散列表（hash表）
before,after维护双向链表的指向关系
next维护散列表中某一索引下的单向链表指向关系
