Java笔记(16) Collection集合-->Set集合-->HashSet

1. Set接口基本介绍

  1. Set是无序集合(添加和取出的顺序不一致,但取出的顺序是固定的),没有索引
  2. 不允许重复元素,所以最多包含一个null
  3. JDK API中Set接口的实现类有:
    Abstract, ConcurrentHashMap.KeySetView, ConcurrentSkipListSet, CopyOnWriteArraySet, EnumSet, HashSet, JobStateReasons, LinkedHashSet, TreeSet

1.1 Set接口的常用方法

Set接口和List接口一样,都是Collection的子接口,因此常用方法和Collection接口一样

1.2 Set接口的遍历方法

同Collection的遍历方式一样,因为Set接口是Collection接口的子接口。

  1. 可以使用迭代器
  2. 增强for循环
  3. 不能使用索引的方式来获取

2 HashSet

2.1 HashSet的全面说明

  1. HashSet实现了Set接口,类定义如下:
public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
  1. HashSet实际上是HashMap,HashSet的无参构造函数如下:
public HashSet() {
    map = new HashMap<>();
}
  1. 可以存放null值,但因为不能重复,所以只能存放一个null
  2. HashSet不保证元素是有序的,取决于hash之后,在确定索引的结果,也因此取出顺序是固定的
  3. 不能有重复元素/对象。

2.2 有关重复元素的经典问题

//定义一个类
class Dog{
    private String name;
    public Dog(String name){
        this.name = name;
    }
}
//定义一个HashSet
Set<Object> set = new HashSet<>();
set.add(new Dog("dog"));
set.add(new Dog("dog"));
System.out.println(set);


两个dog都能添加成功!前面不是说不能有重复元素吗?事实上,HashSet判断元素是否重复依靠的是HashCode,而上面的代码并没有重写HashCode和equals方法,导致HashSet在判断两个Dog对象是否重复时,是以地址为依据判断的,而两个对象实例其在堆上的内存必然是不一样的,因此他们两个被认为是不同的实例。
相同的问题使用String再来验证一下:

set.add("john");
set.add("john");
System.out.println(set);


毫无疑问地添加失败了,这是因为"john"被放在了常量池中,地址不变了吗?

set.add(new String("john"));
set.add(new String("john"));
System.out.println(set);


结果仍然添加失败,这两个String对象的内存地址不同,却仍被准确识别为重复元素,是因为String类重写了HashCode和equals方法,HashSet在判断过程中比较的是二者的内容是否一致,而不再是地址了

2.3 HashSet底层机制说明

HashSet底层是HashMap,HashMap底层是(数组+链表+红黑树)
HashSet添加元素的操作(hash()+equals()):

  1. HashSet底层是HashMap
  2. 添加一个元素是,先得到hash值,会转成索引值
  3. 找到存储数据表table,看这个索引位置是否已经存放的有元素
  4. 如果没有,直接加入
  5. 如果有,调用equals比较内容,如果相同,就放弃添加,如果不相同,则添加到最后,形成链表
  6. 在Java8中,如果一条链表的元素个数超过TREEIFY_THRESHOLD(默认是8),并且table的大小 >= MIN_TRESHOLD_CAPACITY(默认是64),就会进行树化(红黑树)
  7. HashSet底层的HashMap,第一次添加时,table数组扩容到16,临界值(threshold)是16*0.75(加载因子, loadFactor) = 12;
  8. 如果table数组使用到了临界值12,或者某条单链长度超过8,就会扩容到16*2 = 32,新的临界值就是32*0.75 = 24。以此类推
  9. 在Java8中,如果一条链表的元素个数达到TREE_THRESHOLD(默认是8),并且table的大小>=MIN_TREEIFY_CAPACITY(默认是64),就会进行树化(红黑树),否则仍然采用数组扩容机制
  10. 临界值比较的是table中的所有节点个数,不论这个节点是直接存储在table中,还是附加在某一条链表后
  11. 如果table没有达到64,而单链长度超过8,会立即触发扩容,并且每次检测到超长都会触发一次扩容,即使没有达到threshold,直到table长度达到64后,触发树化

2.4 set.add()调用过程

    HashSet<Object> set = new HashSet<>();
    set.add("john");

以上代码的调用过程如下图:

2.4 set.add()调用过程

    HashSet<Object> set = new HashSet<>();
    set.add("john");

以上代码的调用过程如下图:


图中标注了调用顺序和返回顺序
其中,最关键的方法:final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)详细分解如下:

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        //定义了一些辅助变量,table就是HashMap的一个数组,类型是Node[]
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //if语句表示如果当前table是null,或者length==0,就第一次扩容到16
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //(1) 根据key得到Hash,去计算该key应该存放到table的那个索引位置,并把这个位置的对象赋给p
        //(2) 判断p是否为null
        //(2.1) 如果p为null,表示该位置还没有存放过元素,即没有发生哈希冲突,就创建一个Node(key="java",value=PRESENT),
        //      就放在该位置 tab[i] = new Node(hash,key,value,null);
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

            //(2.2) 如果p不为null,表示该位置已经存放过元素,即发生了哈希碰撞,
        else {
            //定义了一些辅助变量。一个开发技巧的提示:在需要的局部变量(辅助变量)时再创建
            Node<K,V> e; K k;
            //(2.2.1) 如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样,并且满足下面两个条件之一,就认为传入了重复元素,不能加入
            // 条件一: 准备加入的key和 p指向的Node节点的key是同一个对象
            // 条件二: 调用equals()方法比较二者,结果为ture,即认为他们内容相同,注意,这里的equals()方法是程序员定义的,不是单纯的比较内容
            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) {
                    //(1) 依次和链表的每一个元素比较后,都不相同,将该元素添加至该链表最后
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //在把元素添加到链表后,立即判断该链表长度是否超过8个节点,如果是,就尝试将该链表转化为红黑树
                        //在进行树化时,还有一层判断:if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize();
                        //如果if条件成立,就会先对table扩容;如果不成立,在转化成红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //(2) 如果比较过程中发现重复元素,退出返回
                    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);//该方法是HashMap留给子类实现的方法,对于HashMap来说,是一个空方法
        return null;//返回null代表成功,否则会在前面的return语句中返回当前索引指向的对象
    }

其中,最关键的方法:final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)详细分解如下:

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        //定义了一些辅助变量,table就是HashMap的一个数组,类型是Node[]
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //if语句表示如果当前table是null,或者length==0,就第一次扩容到16
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //(1) 根据key得到Hash,去计算该key应该存放到table的那个索引位置,并把这个位置的对象赋给p
        //(2) 判断p是否为null
        //(2.1) 如果p为null,表示该位置还没有存放过元素,即没有发生哈希冲突,就创建一个Node(key="java",value=PRESENT),
        //      就放在该位置 tab[i] = new Node(hash,key,value,null);
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

            //(2.2) 如果p不为null,表示该位置已经存放过元素,即发生了哈希碰撞,
        else {
            //定义了一些辅助变量。一个开发技巧的提示:在需要的局部变量(辅助变量)时再创建
            Node<K,V> e; K k;

            //(2.2.1) 如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样
            // 并且满足下面两个条件之一,就认为传入了重复元素,不能加入
            // 条件一: 准备加入的key和 p指向的Node节点的key是同一个对象
            // 条件二: 调用equals()方法比较二者,结果为ture,即认为他们内容相同,注意,这里的equals()方法是程序员定义的,不是单纯的比较内容
            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) {
                    //(1) 依次和链表的每一个元素比较后,都不相同,将该元素添加至该链表最后
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //在把元素添加到链表后,立即判断该链表长度是否超过8个节点,如果是,就尝试将该链表转化为红黑树
                        //在进行树化时,还有一层判断:if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize();
                        //如果if条件成立,就会先对table扩容,知道64;如果不成立,在转化成红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //(2) 如果比较过程中发现重复元素,退出返回
                    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);//该方法是HashMap留给子类实现的方法,对于HashMap来说,是一个空方法
        return null;//返回null代表成功
    }

热门相关:斗神战帝   仗剑高歌   薄先生,情不由己   寂静王冠   寂静王冠