HashSet & HashMap详解

HashSet底层是HashMap，因此本文重点分析HashMap。

基本介绍

1. HashMap是Map接口使用频率最高的实现类。
2. HashMap是以key-val对的方式来存储数据
3. key不能重复，但是值可以重复，允许使用null键和null值。
4. 如果添加相同的key,则会覆盖原来的key-val,等同于修改。(key不会替换，val会替换)
5. 与HashSet一样，不保证映射的顺序，因为底层是以hash表的方式来存储的。（jdk1.8的HashMap底层数组+链表+红黑树）
6. HashMap没有实现同步，因此是线程不安全的，方法没有做同步互斥的操作，没有synchronized。

put操作

1. 添加一个元素时，先得到hash值-会转成->索引值
2. 找到存储数据表table,看这个索引位置是否已经存放的有元素
3. 如果没有，直接加入
4. 如果有，调用equals比较，如果相同，就放弃添加，如果不相同，则添加到最后
5. 在Java8中，如果一条链表的元素个数到达TREEIFY THRESHOLD(默认是8)，并且table的大小>=MIN TREEIFY CAPACITY(默认64)，就会进行树化（红黑树）

源码分析

hash(key)：得到key对应的hash值， h = key.hashCode()) ^ (h >>> 16)

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    HashMap.Node<K,V>[] tab;  
    HashMap.Node<K,V> p; 
    int n, i;
    //table HashMap的一个数组，类型是Node
    if ((tab = table) == null || (n = tab.length) == 0)//如果当前table是null,或者大小=0 进行第一次扩容 默认16
        n = (tab = resize()).length;
    //根据key的hash值，判断key应该在table中存放的位置，并把该位置对象赋值给p
    //判断p是否为null,如果p是null,表示该没有存放元素，就创建一个元素newNode
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {//如果有值
        //如果当前所有位置的链表的第一个元素和准备添加的key的hash值一样
        //并且准备添加的节点和p节点相等（key value都相同），则不可以添加。 注：这里的equals可以被重写
        HashMap.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 HashMap.TreeNode)
            e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //到这里说明数组该位置上是一个链表
            //依次和链表的每个元素比较，都不相同，则加入链表的最后
            //把元素添加到链表后，立即判断，该链表是否已经达到8个节点
            //如果达到，调用treeifyBin，将链表转换为红黑树
            //注：调用treeifyBin 方法会先判断tab<64 ，即先判断是否需要tab扩容，再进行转换红黑树
            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;
            }
        }
        // e!=null 说明存在旧值的key与要插入的key"相等"
        // 对于我们分析的put操作，下面这个 if 其实就是进行 "值覆盖"，然后返回旧值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 如果 HashMap 由于新插入这个值导致 size 已经超过了阈值，需要进行扩容
    //注：这里的size是整个hashMap的size。
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

关于扩容

1. HashMap第一次添加时，table数组扩容到16，临界值(threshold)是16*加载因子(loadFactor)0.75 =12
2. 如果table数组使用到了临界值12，就会扩容到16*2=32，新的临界值就是32*0.75=24,依次类推
3. 在Java8中，如果一条链表的元素个数到达TREEIFY THRESHOLD(默认是8)，并且table的大小>=MIN TREEIFY CAPACITY(默认64)，就会进行树化（红黑树），否则仍然采用数组扩容机制

get操作

1. 计算 key 的 hash 值，根据 hash 值找到对应数组下标: hash & (length-1)
2. 判断数组该位置处的元素是否刚好就是我们要找的，如果不是，走第三步
3. 判断该元素类型是否是 TreeNode，如果是，用红黑树的方法取数据，如果不是，走第四步
4. 遍历链表，直到找到相等(==或equals)的 key

public V get(Object key) {
    Node<K,V> e;
    //计算hash值
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //判断第一个节点是否是需要的
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            //判断是否是红黑树
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //遍历链表，寻找对应key
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

HashSet

1. HashSet底层就是HashMap
2. 可以存放nulI值，但是只能有一个null
3. HashSet不保证元素是有序的，取决于hash后，再确定索引的结果.（即，不保证存放元素的顺序和取出顺序一致)
4. 不能有重复元素/对象

//HashSet是对HashMap的简单包装
public class HashSet<E>
{
	......
	private transient HashMap<E,Object> map;//HashSet里面有一个HashMap
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    public HashSet() {
        map = new HashMap<>();
    }
    ......
    public boolean add(E e) {//简单的方法转换
        return map.put(e, PRESENT)==null;
    }
    ......
}

参考

• https://www.bilibili.com/video/BV1YA411T76k?p=39

• https://www.pdai.tech/md/java/collection/java-map-HashMap&HashSet.html