Java教程

HashSet源码

本文主要是介绍HashSet源码,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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;
    }
}

在这里插入图片描述

这篇关于HashSet源码的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!