HashSet源码
add（）方法第一次添加元素分析
package com.JiHe_.Set_;
import java.util.HashSet;
public class Demo {
public static void main(String[] args) {
HashSet<Object> hashSet = new HashSet<>();
hashSet.add("java");
hashSet.add("lyc");
hashSet.add("java");
System.out.println("hashSet"+hashSet);
/*
源码解读
1.执行HashSet
public HashSet() {
map = new HashMap<>();
}
2.执行一个add方法
public boolean add(E e) {//这里的e是字符串常量（java）
return map.put(e, PRESENT)==null; // static PRESENT = new Object();
//若为true则添加成功
}
3.put方法，该方法会执行hash(key)方法
public V put(K key, V value) {//key=“java”,value=PRESENT，无实际意义，起到占位的作用
return putVal(hash(key), key, value, false, true);
}
4.hash(key)会得到key对应的hash值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//无符号右移16位，是降低hash冲突几率
}
5.执行putVal(hash(key),
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;//定义了辅助变量
//这里的table，就是HashMap的一个数组，类型是Node[]数组
//if语句表示，如果table为空，或者数组长度为0，就第一次扩容table的空间到16
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//执行完本语句，table已获得16的大小
//（1）根据传入key的hash值，去计算key应该存放在table标的哪个索引位置，
//并把这个位置的对象赋给p
//（2）继续判断p是否为空
（2.1），如果p为空表示，还没有存放元素，就创建一个Node，key是真正存放的对象，value就是占位的PRESENT，hash的作用是用来判断下一个进来的值，如果下一个元素的
hash值不相等，就会在该元素的后面添加。
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))))
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;//若下方返回不为null，则返回旧的值
}
}
++modCount;
//判断大小是否已经超过12，
if (++size > threshold)
resize();//扩容
afterNodeInsertion(evict);//这个方法是，留给HashMap子类来实现的，对HashMao自己来说，它就是个空方法
return null;//返回空，代表成功
}
*/
}
}
当add方法继续添加元素时
package com.JiHe_.Set_;
import java.util.HashSet;
public class Demo03 {
public static void main(String[] args) {
HashSet<Object> hashSet = new HashSet<>();
hashSet.add("java");
hashSet.add("lyc");
hashSet.add("java");
System.out.println("hashSet"+hashSet);
/*
1.第二次添加时
//此时hash经过运算=7，所以这个数据会放在7的位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
3.第三次添加时
//此时hash还是等于3，而3的位置上已经有元素，不等于空，所以执行else内的语句
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//一个开发技巧提示：在需要局部变（辅助变量）时再创建，
Node<K,V> e; K k;
//如果当前索引位置对应的链表的第一个元素，和准备添加的key的hash值一样
//并且满足下面两个条件之一：就不能加入
//（1）准备加入的 key 和 p指向的Node结点的key是同一个对象
//（2）p指向Node结点的key的equals( )方法和准备加入的key比较后相同
//理解：第一种比较字符串。第二种比较对象
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判断p是不是一颗红黑树，如果是：就调用putTreeVal方法进行添加
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//只有数组里的索引位置被占用了才开始比较，不然索引位置可以放的。
//如果当前索引位置对应的链表的第一个元素
//如果当前table对应的索引位置已经是一个链表了，就使用for循环依次和该链表中的所有元素一一比较后
//都不相同说明添加的元素，没有重复，则添加到最后
//如果有一个相同，则直接退出
for (int binCount = 0; ; ++binCount) {//死循环
if ((e = p.next) == null) {
//比较的过程中没有相同元素，则把该元素，放在链表的末尾，然后break
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//注意把元素添加到链表后，立即判断该链表是否已经有8个结点，如果是则，直接对当前链表进行树化（转成红黑树）
//但是在要进行树化时还要进行判断if (tab == null || (ntab.length)MIN_TREEIFY_CAPACITY)
//如果table数组不大于64，则进行扩容。
treeifyBin(tab, hash);
break;
}
//比较的过程中有相同元素，直接break
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
//每比一次p指向一个新的结点，e又指向新的p的后一个结点，双指针法的精髓，妙蛙种子，进米奇妙妙屋，妙到家了
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
*/
}
}
equals方法
Object的equals（）方法源码
- Object的equals方法，此时两个引用类型进行比较：比较的默认为地址，或者对象
- 也就是判断两个对象是否是同一个对象
public boolean equals(Object obj) {
return (this == obj);
}
String的equals方法源码
- 重写了Object中的eqyals（）方法，方法功能为，一个字符一个字符的比较字符串的内容
public boolean equals(Object anObject) {
if (this == anObject) {
return true;
}
if (anObject instanceof String) {
String anotherString = (String)anObject;
int n = value.length;
if (n == anotherString.value.length) {
char v1[] = value;
char v2[] = anotherString.value;
int i = 0;
while (n-- != 0) {
if (v1[i] != v2[i])
return false;
i++;
}
return true;
}
}
return false;
}
HashSet的扩容机制
1.HashSet底层是HashMap，第一次添加时，table数组扩容到16，
临界值是（threshold）是16*加载因子（loadFactor）是0.75 =12，
2.如果table数组使用到了加载因子12，那么数组就会扩容到162=32，
新的临界值也就是32*0.75=24，以此类推，
3.可以通过一下小程序Debug，一步一步查看扩容的过程
package com.JiHe_.Set_;
import java.util.HashSet;
public class Demo04 {
public static void main(String[] args) {
/*
1.HashSet底层是HashMap，第一次添加时，table数组扩容到16，
临界值是（threshold）是16*加载因子（loadFactor）是0.75 =12，
2.如果table数组使用到了加载因子12，那么数组就会扩容到16*2=32，
新的临界值也就是32*0.75=24，以此类推，
*/
HashSet hashSet = new HashSet();
for (int i = 0; i <100 ; i++) {
hashSet.add(i);//1,2,3,4,5.....100；
}
}
}
树化机制
- 在java8中，如果有一条链表的元素个数到达(TREEIFY_THRESHOLD)默认是8，并且table的大小>=MIN_CAPACITY(默认为64)
- 就会进行树化，（红黑树），若链表元素已经到达8，而table不足64，则进行扩容一次，链表添加一个元素，数组扩容一次，
- 直到table大于等于64，进行树化
package com.JiHe_.Set_;
import java.util.HashSet;
public class Demo05 {
public static void main(String[] args) {
HashSet hashSet = new HashSet();
for (int i = 1; i <=12 ; i++) {
hashSet.add(new A1(i));
}
System.out.println("hashSet="+hashSet);
}
}
class A1{
private int n;
public A1(int n){
this.n=n;
}
//重写HashCod，使所有的元素的hash值一样，这样就会使这些元素加入同一个链表中
@Override
public int hashCode() {
return 100;
}
}