欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

品HashMap(java8)

程序员文章站 2022-04-14 19:41:58
前言 作为java开发人员,HashMap可谓是业务中的一把利器,9龙再次捡起这老生常谈的知识点,深入源码,细细品味。 首先,我们抛出几个关于HashMap的问题,带着问题去学习,就像捉迷藏一样有意思。 1、为什么要使用HashMap?HashMap有什么特性? 2、HashMap的主要参数有哪些? ......

前言

作为java开发人员,hashmap可谓是业务中的一把利器,9龙再次捡起这老生常谈的知识点,深入源码,细细品味。

首先,我们抛出几个关于hashmap的问题,带着问题去学习,就像捉迷藏一样有意思。

1、为什么要使用hashmap?hashmap有什么特性?

2、hashmap的主要参数有哪些?都有什么作用?

3、hashmap是基于什么数据结构实现的?

4、构造hashmap时传入的初始容量是如何处理的?为什么要这样做?

5、hashmap在什么时候扩容?扩容的时候都做了什么事?hash碰撞8次一定会转换为红黑树吗?

6、在foreach时对hashmap进行增删操作会发生什么?

1、为什么要使用hashmap?

我们在使用一种工具的时候,肯定是因为其的某种特性很符合我们的需求,能够快速准确的解决我们的问题。那我们为什么要使用hashmap呢?

this implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.

源码注释里有这样一句话,这就是我们使用hashmap的原因。

意为:hashmap为基本操作(get和put)提供了常数时间性能(即o(1)),假设散列函数将元素适当地分散到各个bucket中。

我们可以这样理解,如果当你需要快速存储并查询值,可以使用hashmap,它可以保证在o(1)的时间复杂度完成。前提是你键的hashcode要足够不同

map还有一个特性就是key不允许重复。下面我们就来看看hashmap如何保证o(1)进行get和put。

2、细嚼hashmap主要参数

2.1、静态常量

    //默认的初始化桶容量,必须是2的幂次方(后面会说为什么)
    static final int default_initial_capacity = 1 << 4;
    //最大桶容量
    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;
    //判断是否可以执行将链表转化为树,如果当前桶的容量小于此值,则进行resize()。避免表容量过小,较容易产生hash碰撞。
    static final int min_treeify_capacity = 64;

2.2、字段

    //hash表
    transient node<k,v>[] table;
    //缓存的entryset,便与迭代使用
    transient set<map.entry<k,v>> entryset;
    //记录hashmap中键值对的数量
    transient int size;
    //当对hashmap进行一次结构上的变更,会进行加1。结构变更指的是对hash表的增删操作。
    transient int modcount;
    //判断是否扩容的阈值。threshold = capacity * load factor
    int threshold;
    //负载因子,用于计算threshold,可以在构造函数时指定。
    final float loadfactor;

3、嗅探hashmap数据结构

上面我们看到一个node<k,v>[] table的node数组。

为什么要使用数组呢?

答:为了能快速访问元素。哦,说的什么鬼,那我得追问,为什么数组能快速访问元素了?

  1. 数组只需对 [首地址+元素大小*k] 就能找到第k个元素的地址,对其取地址就能获得该元素。
  2. cpu缓存会把一片连续的内存空间读入,因为数组结构是连续的内存地址,所以数组全部或者部分元素被连续存在cpu缓存里面。

让我们看看node的结构。

 static class node<k,v> implements map.entry<k,v> {
        final int hash; //key 的hash
        final k key;    //key对象
        v value;        //value对象
        node<k,v> next; //链接的下一个节点

        node(int hash, k key, v value, node<k,v> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
 }

我们看到,node节点内部保留了一个next节点的引用,太熟悉了,这不就是链表嘛。

到这,我们知道了hashmap的底层数据结构是基于数组+链表。但是,这就完了吗?在jdk1.7确实只是这样,jdk1.8为了提高hash碰撞时链表查询效率低的问题,在hash碰撞达到8次之后会将链表转化为红黑树,以至于将链表查询的时间复杂度从o(n)提高到o(logn)。

品HashMap(java8)

到这我们就可以明白,hashmap如果能够均匀的将node节点放置到table数组中,我们只要能够通过某种方式知道指定key的node所在数组中的索引,基于数组,我们就可以很快查找到所需的值。

接着我们就要看看如何定位到table数组中。

4、走进hashmap构造函数

有了上面的基础知识,知道字段含义及数据结构,我们就有一点信心可以正式进入源码阅读。我觉得了解一个类,得从构造函数入手,知道构造对象的时候做了哪些初始化工作,其次再深入常用的方法,抽丝剥茧。

    public hashmap(int initialcapacity) {
        //如果只传入初始值,则负载因子使用默认的0.75
        this(initialcapacity, default_load_factor);
    }

   public hashmap(int initialcapacity, float loadfactor) {
        if (initialcapacity < 0)
            throw new illegalargumentexception("illegal initial capacity: " +
                                               initialcapacity);
       //保证初始容量最大为2^30
        if (initialcapacity > maximum_capacity)
            initialcapacity = maximum_capacity;
        if (loadfactor <= 0 || float.isnan(loadfactor))
            throw new illegalargumentexception("illegal load factor: " +
                                               loadfactor);
       //使用指定的值初始化负载因子及判断是否扩容的阈值。
        this.loadfactor = loadfactor;
        this.threshold = tablesizefor(initialcapacity);
    }

我们可以看到,构造函数主要是为了初始化负载因子及hash表的容量。可能大家会疑问,这不是初始化的是threshold吗?不要被表面所欺骗,这只是临时将hash表的容量存储在threshold上,我想是因为hashmap不想增加多余的字段来保存hash表的容量,因为数组的length就可以表示,只是暂时数组还未初始化,所以容量暂先保存在threshold。

我们看到将用户指定的initialcapacity传入tablesizefor方法返回了一个值,返回的值才是真正初始化的容量。???搞毛子这是?然我们揭开它神秘的面纱。

/**
 * returns a power of two size for the given target capacity.
 */
static final int tablesizefor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= maximum_capacity) ? maximum_capacity : n + 1;
    }

好吧, 我们还是把它盖上吧,9龙也没去推算过。我们从jdk给的方法注释看出,该方法返回一个目标值的2的幂次方,进一步9龙翻译为:返回大于或等于目标值的第一个数,该数必须是2的幂次方。

举例说一下:

如果输入10,大于等于10的第一个数,又是2的幂次方的数是16;

如果输入7,大于等于7的第一个数,又是2的幂次方的数是8;

如果输入20;大于等于20的第一个数,又是2的幂次方的是32;

到这我们又得问自己,为什么hash表的容量必须是2的幂次方呢?

5、解剖hashmap主要方法

5.1、put

当我们new出hashma的对象,都会调用put方法进行添加键值对。我跟那些直接贴代码的能一样吗?有啥不一样,哈哈哈。9龙会先读源码,再贴流程图,这样大家会更理解一点。

public v put(k key, v value) {
    return putval(hash(key), key, value, false, true);
}

static final int hash(object key) {
        int h;
    //将key的高16位与低16位异或,减小hash碰撞的机率
        return (key == null) ? 0 : (h = key.hashcode()) ^ (h >>> 16);
    }

让我们看看putval干了什么。

    /**
     * 此方法用于将(k,v)键值对存储到hashmap中
     *
     * @param hash key的hash
     * @param key key对象
     * @param value key对应的value对象
     * @param onlyifabsent 如果是true,则不覆盖原值。
     * @param evict if false, the table is in creation mode.
     * @return 返回旧值,如果没有,则返回null。
     */
    final v putval(int hash, k key, v value, boolean onlyifabsent,
                   boolean evict) {
        node<k,v>[] tab; node<k,v> p; int n, i;
        //在第一次put的时候,此时node表还未初始化,上面我们已经知道,构造hashmap对象时只是初始化了负载因子及初始容量,但并没有初始化hash表。在这里会进行第一次的初始化操作。
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //如果得到了一个hash值,并且hash值在很少相同的情况下,如何均匀的分布到table数组里呢?最容易想到的就是用hash%n,n为table数组的长度。但是%运算是很慢的,我们知道位运算才是最快的,计算机识别的都是二进制。所以如果保证n为2的幂次方,hash%n 与 hash&(n-1)的结果就是相同的。这就是为什么初始容量要是2的幂次方的原因。
        //当找到的hash桶位没有值时,直接构建一个node进行插入
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newnode(hash, key, value, null);
        else {
            //否则,表明hash碰撞产生。
            node<k,v> e; k k;
            //判断hash是否与桶槽的节点hash是否相同并且key的equals方法也为true,表明是重复的key,则记录下当前节点
            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) {
                    //如果节点的next索引是null,表明后面没有节点,则使用尾插法进行插入
                    if ((e = p.next) == null) {
                        p.next = newnode(hash, key, value, null);
                        //此时链表长度为9,即hash碰撞8次,会将链表转化为红黑树
                        if (bincount >= treeify_threshold - 1) // -1 for 1st
                            treeifybin(tab, hash);
                        break;
                    }
                    //如果key是同一个key,则跳出循环链表
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //判断是否是重复的key
            if (e != null) { // existing mapping for key
                //拿到旧值
                v oldvalue = e.value;
                //因为put操作默认的onlyifabsent为false,所以,默认都是使用新值覆盖旧值
                if (!onlyifabsent || oldvalue == null)
                    e.value = value;
                afternodeaccess(e);
                //返回旧值
                return oldvalue;
            }
        }
        //到这里,表明有新数据插入到hash表中,则将modcount进行自增
        ++modcount;
        //判断当前键值对容量是否满足扩容条件,满足则进行扩容
        if (++size > threshold)
            resize();
        afternodeinsertion(evict);
        return null;
    }

品HashMap(java8)

总结一下:

  1. put方法先通过计算key的hash值;
  2. 如果hash表没有初始化,则进行初始化;
  3. 然后计算该hash应该处于hash桶的哪个位置;
  4. 如果该位置没有值,则直接插入;
  5. 如果有值,判断是否为树节点,是的话插入到红黑树中;
  6. 否则则是链表,使用尾插法进行插入,插入后判断hash碰撞是否满足8次,如果满足,则将链表转化为红黑树;
  7. 插入后判断key是否相同,相同则使用新值覆盖旧值;
  8. 进行++modcount,表明插入了新键值对;再判断是否进行扩容。

灵魂拷问:真的hash碰撞8次一定会转换为红黑树吗???

其实不然,在put中,如果hash碰撞8次会调用此方法将链表转换为红黑树,但不一定调用就会真正转换。需要tab.length大于等于64才会真正的执行转换操作。因为在表容量过小的时候,hash碰撞才会比较明显,但不是说表越大越好。

 final void treeifybin(node<k,v>[] tab, int hash) {
        int n, index; node<k,v> e;
     //如果表的长度小于64,是先扩容
        if (tab == null || (n = tab.length) < min_treeify_capacity)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            //只有大于等于64才会真正的转换
            treenode<k,v> hd = null, tl = null;
            do {
                treenode<k,v> p = replacementtreenode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

5.2、resize()

put方法中用到了两次resize()方法,现在让我们来品一品resize()的具体实现逻辑。

final node<k,v>[] resize() {
        node<k,v>[] oldtab = table;
        int oldcap = (oldtab == null) ? 0 : oldtab.length;
        int oldthr = threshold;
        int newcap, newthr = 0;
        //如果旧table中有数据
        if (oldcap > 0) {
            //当表的长度达到定义的最大值时,不再进行扩容,只是将判断扩容的阈值改为integer.max_value。
            if (oldcap >= maximum_capacity) {
                threshold = integer.max_value;
                return oldtab;
            }
            //先将新容量为原来的2倍,如果结果小于maximum_capacity并且旧的容量大于等于默认值16,则也将新的阈值为原来的2倍
            else if ((newcap = oldcap << 1) < maximum_capacity &&
                     oldcap >= default_initial_capacity)
                newthr = oldthr << 1; // double threshold
        }
    //oldcap等于0 如果旧阈值大于0,则将旧阈值赋值给新容量。这一步对应于指定的容量构造器,指定容量时,赋值给了阈值
        else if (oldthr > 0) // initial capacity was placed in threshold
            newcap = oldthr;
    //这一步对应于无参构造器,这时使用默认值
        else {               // zero initial threshold signifies using defaults
            newcap = default_initial_capacity;
            newthr = (int)(default_load_factor * default_initial_capacity);
        }
    //这里是因为在oldcap大于0但没有大于默认的16,不会更改newthr的值,还是0。这时候需要根据newcap的值计算newthr。
        if (newthr == 0) {
            float ft = (float)newcap * loadfactor;
            newthr = (newcap < maximum_capacity && ft < (float)maximum_capacity ?
                      (int)ft : integer.max_value);
        }
    //将新阈值覆盖threshold
        threshold = newthr;
        @suppresswarnings({"rawtypes","unchecked"})
    //使用newcap初始化新表。这里的newcap是oldcap的2倍
        node<k,v>[] newtab = (node<k,v>[])new node[newcap];
        table = newtab;
    //至此,完成了新表容量的计算及新阈值的计算,并且创建了新表。下面开始将旧表数据移至新表
        if (oldtab != null) {
            //从表的前往后迁移
            for (int j = 0; j < oldcap; ++j) {
                node<k,v> e;
                //如果下标j对应的位置有值,拿到引用赋值给e
                if ((e = oldtab[j]) != null) {
                    //因为已经有了引用e,可以将原数组的赋值为null, help gc
                    oldtab[j] = null;
                    //如果e.next没有指向,则证明当前槽位只有一个节点,直接计算在新表的位置赋值即可
                    if (e.next == null)
                        newtab[e.hash & (newcap - 1)] = e;
                    //证明当前槽位不止一个节点,判断e是否为treenode,如果是,则使用树的迁移方法
                    else if (e instanceof treenode)
                        ((treenode<k,v>)e).split(this, newtab, j, oldcap);
                    else { // preserve order
                        //因为扩容后的节点不是在j处,就在j + oldcap处。
                        //lohead节点记录了j处的链表的头指针,lotail记录j处尾指针
                        //hihead节点记录了j+oldcap处链表的头指针,hitail记录了j+oldcap处的尾指针
                        node<k,v> lohead = null, lotail = null;
                        node<k,v> hihead = null, hitail = null;
                        node<k,v> next;
                        do {
                            next = e.next;
                            //判断是否还处于j处(后面会详细解释)
                            if ((e.hash & oldcap) == 0) {
                                if (lotail == null)
                                    //记录j的头指针
                                    lohead = e;
                                else
                                    //链接节点
                                    lotail.next = e;
                                lotail = e;
                            }
                            //否则在[j+oldcap]处
                            else {
                                if (hitail == null)
                                    //记录j+oldcap的头指针
                                    hihead = e;
                                else
                                    //链接节点
                                    hitail.next = e;
                                hitail = e;
                            }
                        } while ((e = next) != null);
                        if (lotail != null) {
                            lotail.next = null;
                            //将位置没变的链表放在j处
                            newtab[j] = lohead;
                        }
                        if (hitail != null) {
                            hitail.next = null;
                            //将位置改变的链表放在[j+oldcap]处
                            newtab[j + oldcap] = hihead;
                        }
                    }
                }
            }
        }
    //返回新链表
        return newtab;
    }

现在我们仔细分析e.hash & oldcap。二话不说,直接上图。

品HashMap(java8)

如此详细,是不是不点赞都有点过分了。

resize()中我们看到如果是树节点,调用了((treenode<k,v>)e).split(this, newtab, j, oldcap)方法。有了上面的知识,其实这个方法干的事情是一样的。将红黑树拆分为两棵子树,还是分别放置于原来位置和原来位置+oldcap位置。但要注意,这个方法在树的节点小于等于6的时候会将红黑树转换回链表。

final void split(hashmap<k,v> map, node<k,v>[] tab, int index, int bit) {
            treenode<k,v> b = this;
            // relink into lo and hi lists, preserving order
            treenode<k,v> lohead = null, lotail = null;
            treenode<k,v> hihead = null, hitail = null;
            int lc = 0, hc = 0;
            for (treenode<k,v> e = b, next; e != null; e = next) {
                next = (treenode<k,v>)e.next;
                e.next = null;
                //判断位置是否更改
                if ((e.hash & bit) == 0) {
                    if ((e.prev = lotail) == null)
                        lohead = e;
                    else
                        lotail.next = e;
                    lotail = e;
                    ++lc;
                }
                else {
                    if ((e.prev = hitail) == null)
                        hihead = e;
                    else
                        hitail.next = e;
                    hitail = e;
                    ++hc;
                }
            }

            if (lohead != null) {
                //数量小于等于6,转换回链表
                if (lc <= untreeify_threshold)
                    tab[index] = lohead.untreeify(map);
                else {
                    tab[index] = lohead;
                    if (hihead != null) // (else is already treeified)
                        lohead.treeify(tab);
                }
            }
            if (hihead != null) {
                if (hc <= untreeify_threshold)
                    tab[index + bit] = hihead.untreeify(map);
                else {
                    tab[index + bit] = hihead;
                    if (lohead != null)
                        hihead.treeify(tab);
                }
            }
        }

到此,resize()方法9龙啃完了,牙好疼啊。

5.2、get

知道了hashmap的数据结构及如何以常数时间将键值对put保存管理的,那get这不是很容易吗?请大家尝尝这道小菜。我们保存的是键值对,存储的时候都是以key作为条件存储的,所以在我们取值的时候也是通过key获取值。

    public v get(object key) {
        node<k,v> e;
        //计算key的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;
         //如果hash桶有值,并且基于hash继续的桶位置也存在值
        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;
            //如果第一个不匹配,则判断next是否存在
            if ((e = first.next) != null) {
                //如果存在,判断桶节点是否为树节点,如果是树节点,则从红黑树查找返回
                if (first instanceof treenode)
                    return ((treenode<k,v>)first).gettreenode(hash, key);
                do {
                    //不是树节点,从链表的表头向表尾依次判断是否匹配
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        //找到则返回
                        return e;
                } while ((e = e.next) != null);
            }
        }
         //没有找到,则返回null
        return null;
    }

总结一下get流程:

  1. 更加key计算hash值
  2. 使用hash&(n-1)判断hash桶位是否有值,如果没有值,则返回null
  3. 如果有值,判断第一个是否匹配。(匹配指:hash值相同并且equals方法返回结果为true),匹配则返回
  4. 如果第一个不匹配,判断是否为树节点,是树节点则从红黑树查找
  5. 如果不是树节点,则是链表,则从表头到表尾依次查找。

6、简述modcount

这个字段并不是map独有的,collection集合(list、set)也有。此字段用于迭代时的快速失败,也就是在迭代的过程中,如果调用了put、clear、remove等会对容器内部数据的数量产生增加或减少的操作时,抛出concurrentmodificationexception异常。

hashmap有三个迭代器,分别是keyiterator、valueiterator、entryiterator,它们分别对应于keyset、values、entryset内部类中,当用户调用其对应的iterator()方法时都会new一个对应的迭代器。

这里我就不贴代码了,太多,有兴趣的可以去看一看。这里主要讲解为什么快速失败。

final class keyiterator extends hashiterator
        implements iterator<k> {
        public final k next() { return nextnode().key; }
    }

    final class valueiterator extends hashiterator
        implements iterator<v> {
        public final v next() { return nextnode().value; }
    }

    final class entryiterator extends hashiterator
        implements iterator<map.entry<k,v>> {
        public final map.entry<k,v> next() { return nextnode(); }
    }

使用者可以根据自己的需求选择使用的迭代器。每一个都继承自hashiterator,我们来看一看。

 abstract class hashiterator {
        node<k,v> next;        // next entry to return
        node<k,v> current;     // current entry
        int expectedmodcount;  // for fast-fail
        int index;             // current slot

        hashiterator() {
            //关键在这里,当每一次使用迭代器的时候,会将modcount赋值给内部类的expectedmodcount
            expectedmodcount = modcount;
            node<k,v>[] t = table;
            current = next = null;
            index = 0;
            if (t != null && size > 0) { // advance to first entry
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }

        public final boolean hasnext() {
            return next != null;
        }

        final node<k,v> nextnode() {
            node<k,v>[] t;
            node<k,v> e = next;
            //每次取值之前会判断modcount和expectedmodcount是否相等,如果不等则表明在迭代过程中有其他线程或当前线程调用了put、remove等方法。
            if (modcount != expectedmodcount)
                throw new concurrentmodificationexception();
            if (e == null)
                throw new nosuchelementexception();
            if ((next = (current = e).next) == null && (t = table) != null) {
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }

        //如果想删除,只能调用迭代器自己的remove方法,但是,它删除的是调用nextnode()拿到的节点
        public final void remove() {
            node<k,v> p = current;
            if (p == null)
                throw new illegalstateexception();
            //删除之前也会判断modcount是否被修改
            if (modcount != expectedmodcount)
                throw new concurrentmodificationexception();
            current = null;
            k key = p.key;
            removenode(hash(key), key, null, false, false);
            expectedmodcount = modcount;
        }
    }

所以,在迭代过程中对hashmap进行增删操作会抛出concurrentmodificationexception异常。还记得一开始提出的一个问题吗?对的,就是它。你可以去看看list等的源码,modcount也存在,而且实现都是一样的。

7、总结

楼主花了很大的精力与时间与大家细嚼慢咽hashmap,我想现在大家都知道了最开始的问题的答案了,包括过程中楼主提出的一些问题,也都一一进行了详解。9龙没去讨论并发条件出现的问题,也不讨论1.7并发扩容时链表死循环问题,网上太多了。更重要是,hashmap本身就不支持并发操作,那你想到了什么呢?

9龙才疏学浅,文中如有错误,敬请指出,也欢迎大家有疑问可以提出,一起探讨进步。

如果觉得9龙本文对你有帮助,请帮忙点赞、分享以示支持,如果转载请注明出处。话不多说,点关注,不迷路。