美文网首页
解剖HashMap

解剖HashMap

作者: 我要做大牛23333 | 来源:发表于2019-02-04 16:42 被阅读0次

    HashMap是Java里使用频率非常高的集合类型,基本的组成元素为Bin

    public class HashMap<K,V> extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable
    

    先看签名,HashMap继承自AbstractMap,实现Map接口,可被序列/反序列化。

        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
        static final int MAXIMUM_CAPACITY = 1 << 30;
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
        static final int TREEIFY_THRESHOLD = 8;
        static final int UNTREEIFY_THRESHOLD = 6;
        static final int MIN_TREEIFY_CAPACITY = 64;
    
    • DEFAULT_INITIAL_CAPACITY: 默认初始化大小是16
    • MAXIMUM_CAPACITY:最大容量是2的30次幂
    • DEFAULT_LOAD_FACTOR:默认负载因子是0.75,代表如果容量如果超过最大容量的百分之75就会进行resize,对当前HashMap实例进行扩容
    • TREEIFY_THRESHOLD:顾名思义,在一个桶中大于8个Bin后从List类型转变为Tree类型,推测为自动平衡二叉树,即,红黑树
    • UNTREEIFY_THRESHOLD:这里考虑到在8这个临界点之间来回变动会有很大的性能开销,所以设置了这个参数,默认为6,在小于这个值的时候才会将Tree转为List
    • MIN_TREEIFY_CAPACITY: 桶中最小Bin容量,如果大于这个值会进行扩容,这个值最少为TREEIFY_THRESHOLD的4倍,即32

    在初始化HashMap的时候,有两个因子对性能影响非常大,一个是初始化的大小,另一个是load factor,负载因子,其中0.75是一个权宜之值,即考虑了查找时间成本也照顾了空间成本。如果有很多不同的keys映射到了相同的hashcode上,那么java 1.8以前会讲这些entry全部放到同一个bucket桶下,按照链表结构来排序,1.8以后做了优化,会采用红黑树的结构在动态平衡查找效率,这里有个小知识点,就是如果这些keys是Comparable的,那么在同一个bucket下会按照排序大小来进行排序。

    絮叨完后,我们先简单总结下,HashMap有这么几个很重要的概念:

    1. Node:内部类,用于保存Entry的
    2. Entry:一个由<key,value>组成的对象,value就是具体的数据,可能是基础类型,也可能是一种对象
    3. Bucket/Bin:中文翻译过来叫桶,桶是用来存储具体Entry的容器,可以把它理解为一个List链表,具体实现在1.7以前就是单纯的以Node为节点的单向链表,1.8以后为了更好的查找性能引入了红黑树,如果链表的长度过长,如上文提到的TREEIFY_THRESHOLD就会自动把这个桶改变成红黑树结构,如果元素被删除过多比如低于UNTREEIFY_THRESHOLD,那么就没有必要保留这种结构,因为红黑树带来的不好的地方是,除了查找效率高,插入删除有可能每次都会做左旋右旋等平衡操作,个数少的时候还是链表比较方便。
    4. Hashcode:哈希码,有两个哈希码,一定要区分,一个是要保存或插入对象本身的hashcode,还有一个是对象要插入到HashMap中计算后得到的hashcode,下面我们通过put,get,remove等增删查操作细细地说。

    好,说完HashMap的元素及类型,现在说说它的常规操作:

    put 添加记录操作

    签名为:

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

    调用的putVal,倒数第二个false代表着如果插入的key一样,则直接替换,最后一个true代表如果是false,则开启创建模式。

    在插入的时候,先根据key计算出key的hash,计算方式是:

    static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
    

    把key的hashcode的低16位与自己的高16位做异或操作返回一个int值。

    然后用长度下标和这个hash值做与(&)操作,这样的话就相当于每次对桶做查找操作的时间复杂度始终是O(1),听我细细来讲,这里是HashMap的一个精髓的地方:
    首先HashMap的长度永远都是2的指数倍,这么做的道理就来源于二进制,只有这样,在与key的hash结果做与操作的时候才可能立刻得到一个确定的数,这个数就是桶的编号,比如,长度为16,二进制表示为10000,它再减一就是1111,那么它在和一个int类型的数字&的时候,会把所有为0的位数置为0,1则不动,从而得到一个在0~16之间的数字。看代码:

    if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
    

    tab就是Node组成的数组,n就是数组的长度(永远为2的倍数),如果这里返回null证明该Node还没被人使用,可以创建新Node。

    如果这里p不为空,证明该桶已经被人占了,hashcode出现了冲突,注意这里是put的key的hash,而不是value的hash,那么如果有冲突我们怎么解决冲突呢?常见的做法就是把这个桶变成一个链表,我们看下Node的结构就不难发现,它是内部类,并且有一个变量是next,就是用来做链表指向下一个的。
    我们接着看代码:

    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 {
        ...
    }
    

    首先判断当前这个桶中第一个节点,即表头的hash和要插入的key的hash一样不一样,如果一样并且两个key相等,就先暂时保留为变量e
    接下来如果发现这个桶是个红黑树结构,则进行红黑树的值插入操作,这里先暂不展开。
    最后如果以上都不满足,那么会遍历这个链表,如果遇到相同的key的就做值替换,如果没有就在尾部插入一个新节点(如果超过TREEIFY_THRESHOLD则把链表转变为红黑树)。
    这里有个点需要提一下,就是
    p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
    除了先判断两个hash相等外,还要判断这两个key到底是不是相等,这么做的目的应该就是先做粗略比较,两个key的摘要一样吗,如果一样说明要么哈希算法冲突,要么这俩就是一模一样,所以才有后续继续比较值的操作。

    最后的最后:

    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);
            return null;
    

    判断这个e是不是不为null,不为空那么就意味着key相等,那么就可以根据参数做替换value的操作了。

    ++modCount,如果这个值变了会导致对map做遍历的时候fast-fail,立刻抛出ConcurrentModificationException异常
    threshold就是一个阈值,大于它则需要做resize操作,即扩容。关于扩容以及扩容导致的死锁我们在下文讲。

    resize()

    /**
         * Initializes or doubles table size.  If null, allocates in
         * accord with initial capacity target held in field threshold.
         * Otherwise, because we are using power-of-two expansion, the
         * elements from each bin must either stay at same index, or move
         * with a power of two offset in the new table.
         *
         * @return the table
         */
    

    resize用来初始化或者double表的大小,此处的table就是前文提到桶的引用,即那个Node数组。如果为空的话则按照指定的容量进行初始化,否则就扩容到之前的两倍,并且原有HashMap中的元素还要保留在原有的index,或者移动到2的指数倍的偏移位置。先上流程图,我们再细细讲里面的难点。

    hashmap_resize.png
    其中在对老的数据做迁移的时候有一些技术点需要注意,就是怎么迁移过去。
    1. 如果这个桶中只有一个元素,不是一个链表或者红黑树的话,最简单,用这个元素的hash值和新大小减一做与&操作,得到一个数据下标index,直接放入即可。
    2. 如果这个桶下面挂的是一个树,那么把树做拆分,由于这是1.8新引入的改进,是一个优化手段,所以这里先暂不讨论。
    3. 如果桶下面是一个链表,那么由于新的容量是老的容量的两倍,先把新HashMap的桶数据,分成两半,一个叫high,高位区,另一个叫low,低位区。再用循环遍历这个桶下的每个元素,如果遍历到的元素的hash哈希值对老的容量oldCap做与&操作得到0,则证明这个元素的哈希值不需要移位,直接放入低位区即可,否则放入高位区。这里需要举个例子,假如之前a值是17,b的值是1,这两个数在容量为16的HashMap中的哈希值都是1,都会被安排到index为1的这个桶中,而在扩容到32的时候,则会把17放到高位区。
      直接看核心代码:
    Node<K,V> loHead = null, loTail = null;
                            Node<K,V> hiHead = null, hiTail = null;
                            Node<K,V> next;
                            do {
                                next = e.next;
                                if ((e.hash & oldCap) == 0) {
                                    if (loTail == null)
                                        loHead = e;
                                    else
                                        loTail.next = e;
                                    loTail = e;
                                }
                                else {
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.next = e;
                                    hiTail = e;
                                }
                            } while ((e = next) != null);
                            if (loTail != null) {
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            if (hiTail != null) {
                                hiTail.next = null;
                                newTab[j + oldCap] = hiHead;
                            }
    

    最后有一个小知识点就是,HashMap在resize的时候可能会出现死循环,这个很好理解,比如之前桶1下的节点本来是A -> B -> C,一个并发的resize就很有可能导致死循环,比如可能会变为A -> B 而resize过程中B被移到了另一个桶并指向了C,而原来的C也做了resize操作并且指向了B,这样遍历的时候就变成了死循环。

    get 查看记录

    HashMap的get返回是有可能为null的,而这个null,可能代表这个key没有找到,也可能代表这个key对应的就是null,为了区分这俩可以用containsKey

    1. 首先计算key的hash值,按照HashMap中的老办法,高位下移,与低位异或得到hash值。
    2. 做null值判断,如果匹配到了桶再做处理
    (tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null
    

    table,即HashMap内部桶数组不为空,并且长度大于0,并且tab[(n - 1) & hash]是有值的,就是说这个hash对应的桶里是有货的,至于是一个还是多个,还得接着走。

    1. 这不接着就来了个是否为多个的判断(e = first.next) != null,如果多个就遍历,最后判断是否为要取的对象还是通过e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))),即要找的key的hash值和当前的hash值一样,到这步了,那么肯定是一样的,再判断key的值是一样或者一模一样的引用,比如都是"AAA"或指向同一个实例之类的。

    remove() 删除节点

    这里就不再赘述了,有了put和resize的功底,再理解remove就不再难了,无非就是找到这个节点,如果是单个,就直接删除,如果是链表或者树,就利用树的删除节点操作和链表的删除节点操作,干点这个节点即可。最后modCountsize都要相应的变化。如果找到并删除了则返回这个节点,如果没有则返回null

    这里最后留几个问题给自己:
    1. 为什么hash的算法是这样的,要对高位做移位操作然后XOR异或?
    2. 为什么再resize后,有些节点会被移到高位区,而有些节点会保留原有的位置?
    下篇回答这个问题!

    相关文章

      网友评论

          本文标题:解剖HashMap

          本文链接:https://www.haomeiwen.com/subject/xwncfqtx.html