Java 集合HashSet 源码解析

Java 集合 HashSet 源码解析 HashSet 介绍

HashSet实现了Set接口

HashSet实际上是HashMap

public HashSet(){
    map = new HashMap<>();
}

可以存放null值，但是只能有一个null
HashSet不保证元素是有序的，取决于hash后，再确定索引的结果
不能有重复元素/对象

构造方法

HashSet() 构造一个新的空集合; 背景HashMap实例具有默认初始容量（16）和负载因子（0.75）。
HashSet(Collection c) 构造一个包含指定集合中的元素的新集合。
HashSet(int initialCapacity) 构造一个新的空集合; 背景HashMap实例具有指定的初始容量和默认负载因子（0.75）。
HashSet(int initialCapacity, float loadFactor) 构造一个新的空集合; 背景HashMap实例具有指定的初始容量和指定的负载因子。

方法

boolean	add(E e) 将指定的元素添加到此集合（如果尚未存在）。
void	clear() 从此集合中删除所有元素。
Object	clone() 返回此 HashSet实例的浅层副本：元素本身不被克隆。
boolean	contains(Object o) 如果此集合包含指定的元素，则返回 true 。
boolean	isEmpty() 如果此集合不包含元素，则返回 true 。
Iterator	iterator() 返回此集合中元素的迭代器。
boolean	remove(Object o) 如果存在，则从该集合中删除指定的元素。
int	size() 返回此集合中的元素数（其基数）。

底层机制添加元素的底层实现(hash()+equals())

先获取元素的哈希值(hashCode())
对哈希值进行运算，得出一个索引值，即要存放在哈希表中的位置下标
如果该位置上没有其他元素，则直接存放，如果已经有元素，则元素要进行equls判断，如果相等不再添加，不相等则以链表方式添加
在Java8中，如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认8),且table的大小>=MIN_TREEIFY_CAPACITY(默认64)，就会进行树化(红黑树)
当 HashMap 中的 size >= threshold 时或单条链表长度超过8且table.size<64，HashMap 就要扩容。

执行过程（插入多个数据）

add(“java”) 第一次添加元素

//1 初始化 HashSet()
public HashSet() {
    map = new HashMap<>();
}
//2 执行 add()
public boolean add(E e) {
    return map.put(e, PRESENT)==null;//put返回的为空代表成功
}
//3 执行HashMap的 put()
private static final Object PRESENT = new Object();//PRESENT只是随意的一个对象 HashSet所有键值对的值都指向它
public V put(K key, V value) {//HashMap的put
    return putVal(hash(key), key, value, false, true);
}
    //3.1 执行HashMap的 hash(key) 得到hash值 算法 (h = key.hashCode()) ^ (h >>> 16)
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//>>>无符号右移16位
    }
//4 执行HashMap的 putVal()
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node[] tab; Node p; int n, i;//定义了辅助变量
    //如果当前table为空，则第一次扩容，扩容到16
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;//-------->5.1 resize()
    //(1)根据key得到hash 去计算该key一个 存放到table表的哪个索引位置 (3)
    //并把这个位置的对象 赋给 p
    //(2)判断p 是否为null
    //(2.1) 如果p为null 表示还没有存放过元素 就创建一个Node (key="java",value=PRESENT)
    //(2.2) 就放在该位置 tab[i] = newNode(hash,key,value,null)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
  	
    ++modCount;//修改了一次
    if (++size > threshold)//如果当前数据总数超过 扩容因子数12 则扩容
        
    afterNodeInsertion(evict);//void afterNodeInsertion(boolean evict) { } 空的，啥也不干
    return null;//返回null表示成功
}
    //4.1 执行HashMap的 resize()
	final Node[] resize() {
        Node[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
     	
        else {               //走这里
            newCap = DEFAULT_INITIAL_CAPACITY;//1 << 4 = 16 默认16
            //临界因子*默认大小 = 0.75*16 = 12 16个使用了12个就需要扩容了
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//12
        }
        
        threshold = newThr;//12
        @SuppressWarnings({"rawtypes","unchecked"})
        Node[] newTab = (Node[])new Node[newCap];
        table = newTab;//16大小的空数组
      
        return newTab;
    }

add(“php”) 第二次添加元素

//1 执行 add()
public boolean add(E e) {
    return map.put(e, PRESENT)==null;//put返回的为空代表成功
}
//2 执行HashMap的 put()
private static final Object PRESENT = new Object();//PRESENT只是随意的一个对象 HashSet所有键值对的值都指向它
public V put(K key, V value) {//HashMap的put
    return putVal(hash(key), key, value, false, true);
}
    //2.1 执行HashMap的 hash(key) 得到hash值 算法 (h = key.hashCode()) ^ (h >>> 16)
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//>>>无符号右移16位
    }
//3 执行HashMap的 putVal()
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node[] tab; Node p; int n, i;//定义了辅助变量
    
    //(1)根据key得到hash 去计算该key一个 存放到table表的哪个索引位置 (9)
    //并把这个位置的对象 赋给 p
    //(2)判断p 是否为null
    //(2.1) 如果p为null 表示还没有存放过元素 就创建一个Node (key="php",value=PRESENT)
    //(2.2) 就放在该位置 tab[i] = newNode(hash,key,value,null)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
  
    ++modCount;//修改了一次
    
    return null;//返回null表示成功
}

add(“java”)第三次添加元素（重复元素）

// 执行HashMap的 putVal()
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node[] tab; Node p; int n, i;//定义了辅助变量
  	 //p是tab[3]!=nll
    else {
            Node e; K k;
        	
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
        	//判断p是不是一颗红黑树
        	//如果是红黑树 则调用 putTreeval 来添加
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
            else {//如果table对应索引位置 已经是一个链表 就使用for循环比较
                
                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)//如果当前数据总数超过 扩容因子数12 则扩容
        
    afterNodeInsertion(evict);//void afterNodeInsertion(boolean evict) { } 空的，啥也不干
    return null;//返回null表示成功
}
    //treeifyBin
	final void treeifyBin(Node[] tab, int hash) {
        int n, index; Node e;
        //转换红黑树要求：table表大小要大于等于64
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();//table表大小不够 则先扩容table表
        
    }

Java 集合HashSet 源码解析

Java相关栏目本月热门文章