关于java:HashMap底层实现机制及源码解析

HashMap简介

本篇文章是本人在学习HashMap的过程中本人的总结,并不一定完全正确,次要是记录本人的学习过程。

  • HashMap是一种映射关系,是hash值与理论存储对象之间的映射,也就是键值对的关系,通过关键字key找到理论存储的值value,是一种数据结构
  • 什么是hash:实质上是把任意长度的输出,通过算法变换成固定长度的输入
  • 在学习Java的过程中,最常见的两种数据结构是数组和链表,那么数组和链表各有什么优缺点?

    • 数组:数组在物理空间中是间断的,数组对象间接指向数组首地址,在查找的时候效率高,然而因为空间是间断的,所以当物理空间的碎片比拟多时,当咱们想存入比拟大的数组的时候,即便可能空间足够,但因为这些空间不是间断的,就无奈存入
    • 链表:链表在物理空间中不是间断的,在存放数据的同时还须要寄存下一个链节点的地址,相比于数组,不受空间是否是碎片化的影响,只有有空间,就能存储数据。然而查找效率没有数组高,插入和删除的效率比数组高
  • HashMap:HashMap将数组和链表联合起来,既可能进步查找效率,删除和插入的效率也进步了。

外部组成

  • HashMap的存储模式:键值对的存储模式
  • 数据结构:数组+链表+红黑树
  • 外部成员:

    • 默认初始容量DEFAULT_INITIAL_CAPACITY:16
    • 默认负载因子DEFAULT_LOAD_FACTOR:默认为0.75,示意整体上table被占用水平
    • TREEIFY_THRESHOLD:8,当数组中有某个索引地位上的链表长度大于该常量时,就将该链表转换成红黑树
    • UNTREEIFY_THRESHOLD:6,当链表的长度小于该常量时,就将红黑树转换成链表
    • 阈值threshold:当数组中键值对个数大于阈值时进行扩大,计算形式是hashmap长度*负载因子
    • Node<K,V>[] table:数组

构造方法

  • HashMap map = new HashMap();

    • 无参的构造方法,只初始化了负载因子,默认为0.75
  • HashMap map = new HashMap(int initialCapacity);

    • 参数为map的初始容量,负载因子为默认值0.75,底层实际上是调用了HashMap(int initialCapacity, float loadFactor)
  • HashMap map = new HashMap(int initialCapacity, float loadFactor)

    • 指定初始的容量以及负载因子
  • HashMap map = new HashMap(Map m);

    • 初始化负载因子,默认为0.75
    • 调用putMapEntries办法,将汇合m全副都装进新的map汇合里
    • 办法的执行步骤如下:

      • 获取m的理论判读,判断是否大于0,只有当大于0时才才执行
      • 判断map的table数组是否为空,如果为空计算map的阈值
      • 如果table数组不为空,判断s的理论长度是否大于map的阈值,如果大于对map汇合进行扩容
      • 当map的长度确定下来之后,遍历m汇合,把键值对取出来存入map汇合当中

增删查办法源码解析

  • hash值计算过程:
static final int hash(Object key) {
        int h;
        //判断key的值是否为空
            // 如果为空则返回0
            // 如果不为空则调用key的hashCode办法计算出hash值
            //     并让hash值的高16位与低16位进行异或操作,得出最初的hash值
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
  • put办法

put办法大抵的流程能够分为以下几点:

* 1)计算hash值,依据hash值得出索引值,采纳的是以后table长度-1 & hash值相与得出索引值(hash值是通过下面的hash办法计算得出,而不是调用hashCode办法)
    举个例子:存入两个key的hash值别离为14和35,而以后table的长度为默认容量16(2^n)
    那么第一个key对应的索引值为:0000 1110 & 0000 1111,得出索引值为14
    第二个key对应的索引值为:0010 0011 & 0000 1111,得出索引值为3
    这样做能确保每个不管hash值有多大,都可能存入数组,截取的是hash值的二进制数的后n位
* 2)依据hash找到对应的索引值,有三种状况:
    * 以后地位为空,间接存入
    * 以后地位不为空,且是链表,插入到链表的尾部
    * 以后地位为空,且是红黑树,插入到红黑树当中
* 3)判断以后table的理论长度size是否超出阈值threshold,如果超出则进行扩容

以下是对源码的解读:

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;
        //2)判断 table数组是否为空 || table数组的长度是否0,也就是是否是第一次寄存
        if ((tab = table) == null || (n = tab.length) == 0)
            //其中一个条件满足,给table扩容
            n = (tab = resize()).length;
        //3)计算 (数组长度 - 1 & hash值),得出索引值,获取对应索引的值,判断是否为空
        if ((p = tab[i = (n - 1) & hash]) == null)
            //如果为空,在该索引地位创立一个新的节点,并放入
            tab[i] = newNode(hash, key, value, null);
        //4)如果不为空,证实该索引地位曾经有值了
        else {
            HashMap.Node<K,V> e; K k;
            //判断是否是同一个key
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                //如果是同一个就赋给e(赋给e是为了接下来是否要笼罩该地位的值做筹备)
                e = p;
            //如果不是同一个key,判断是否是树节点,如果是树节点,把节点插入到红黑树外面
            else if (p instanceof HashMap.TreeNode)
                e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //如果既不是同一个key,也不是树节点,那只可能是链表
            else {
                //循环链表,判断每个节点的key是否与要插入的key雷同,如果雷同则笼罩掉。
                //binCount记录该链表的节点地位
                for (int binCount = 0; ; ++binCount) {
                    //判断以后地位是否是尾结点
                    if ((e = p.next) == null) {
                        //如果是尾节点,则在为节点的下一个节点插入新的节点(尾插法)
                        p.next = newNode(hash, key, value, null);
                        //判断以后链表的节点树是否大于(TREEIFY_THRESHOLD - 1)
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //如果大于则将链表转换成红黑树
                            treeifyBin(tab, hash);
                        //跳出循环
                        break;
                    }
                    //判断以后地位和咱们要存入的key是否雷同,如果雷同则跳出循环
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //如果以上两个判断都不满足,持续遍历下一个节点
                    p = e;
                }
            }
            //判断e是否为空
            if (e != null) { // existing mapping for key
                //不为空,取出e的value值
                V oldValue = e.value;
                //onlyIfAbsent如果为false,则示意如果呈现的key雷同,则笼罩掉原来的值,反之就不笼罩
                    //能够参考HashMap的另一个办法,putIfAbsent的源码,外面的onlyIfAbsent就设为true
                //还有一种状况:原本寄存的value是null,那么不论onlyIfAbsent是true还是false,肯定会被笼罩掉
                if (!onlyIfAbsent || oldValue == null)
                    //笼罩掉本来的value值
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //记录批改次数
        ++modCount;
        //判断存入之后的size是否大于阈值
        if (++size > threshold)
            //如果大于则扩容,扩容的办法能够往下翻
            resize();
        afterNodeInsertion(evict);
        return null;
    }
  • remove(key)办法

remove的办法流程大抵如下:

  • 计算hash值,依据hash值计算出索引地位
  • 找到要删除的索引地位的值
  • 该值有如下三种状况

    • 以后节点
    • 链表上的几点
    • 红黑树上的几点
  • 依据找到的节点再做判断

    • 如果是红黑树,那么将该节点从红黑树上删掉
    • 如果是链表,进行断链操作
    • 如果是以后节点,该索引地位指向以后节点的下一节点

具体源码如下:

// 1)判断key是否为空,并计算出hash值
    final HashMap.Node<K,V> removeNode(int hash, Object key, Object value,
                                       boolean matchValue, boolean movable) {
        HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, index;
        //1)判断外部的table数组是否为空 && table数组长度是否大于0
        // && (以后table的长度-1)与 hash值 相与,取出该索引地位的值,判断是否为空
        if ((tab = table) != null && (n = tab.length) > 0 &&
                (p = tab[index = (n - 1) & hash]) != null) {
            HashMap.Node<K,V> node = null, e; K k; V v;
            //2)如果以后索引地位的值p与要删除的key是雷同的话
            //  把p赋给节点node(赋给节点node是为了删除完之后还要返回被删除节点的值)
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            //3)如果不雷同,判断以后节点的下一个节点是否为空
            //如果不为空,可能要删除的点是链表中的某一个节点或者是树节点(红黑树)
            else if ((e = p.next) != null) {
                //判断是否是树节点
                if (p instanceof HashMap.TreeNode)
                    //如果是树节点,依据以后节点找到根节点,并依据根节点往下找直到找到要删除的节点
                    node = ((HashMap.TreeNode<K,V>)p).getTreeNode(hash, key);
                //如果是链表,则遍历链表,直到找到要删除的节点
                else {
                    do {
                        if (e.hash == hash &&
                                ((k = e.key) == key ||
                                        (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            //如果找到的节点node不等于空,判断该节点的构造
            if (node != null && (!matchValue || (v = node.value) == value ||
                    (value != null && value.equals(v)))) {
                //如果是树节点,则证实该链表曾经被转换成红黑树,删除树节点
                if (node instanceof HashMap.TreeNode)
                    ((HashMap.TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                //如果该节点就是一个node对象,则把该节点的下一个节点赋给该节点对应的索引地位
                //(因为如果要删除的节点等于以后节点,证实该索引地位上就一个值,
                // 则以后节点的下一个节点就肯定为null,这样就相当于把以后节点对应的索引地位置空)
                else if (node == p)
                    tab[index] = node.next;
                //如果既不是树节点,也不是node对象,则要删除的节点是链表上的某一个节点,则把要删除的节点删掉(进行断链的操作)
                else
                    p.next = node.next;
                //批改次数加一
                ++modCount;
                //table的理论长度减一
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }
  • get(key)办法

get办法的大抵流程如下:

  • 计算hash值,依据hash值计算出索引地位
  • 判断该索引地位的值,有如下三种状况

    • 是否是以后节点
    • 是否是红黑树上的节点,如果是依据红黑树查找
    • 是否是链表节点,如果是遍历链表
  • 返回找到的节点

具体源码的正文如下:

// 1)判断key是否为空,并计算出hash值
    final HashMap.Node<K,V> getNode(int hash, Object key) {
        HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k;
        //1)判断外部的table数组是否为空 && table数组长度是否大于0
        // && (以后table的长度-1)与 hash值 相与,取出该索引地位的值first,判断是否为空
        if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
            //2)判断找到的first与key是否雷同,如果雷同则间接返回
            if (first.hash == hash && // always check first node
                    ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //如果步骤2的条件不满足,有一种状况是真的没有对应的值
            // 还有一种状况可能是hash抵触造成的起因,也就是该first节点实际上是一个链表
            // 可能所要取的值不在头节点上,这时候就要去遍历链表的每一个节点
            //判断first的下一个节点是否为空,如果为空证实要找的key没有对应的值,否则进行下一步
            if ((e = first.next) != null) {
                //判断first是不是TreeNode节点,也就是判断该链表是否被转化成红黑树
                // 如果不是进行下一步,如果是查找红黑树节点
                if (first instanceof HashMap.TreeNode)
                    //getTreeNode大抵的办法流程如下:
                    //将first节点转换成TreeNode节点,判断first节点的父节点是否为空
                    // 如果为空证实该节点是根节点,如果不为空依据以后节点往上始终找,直到找到根节点
                    //依据根节点遍历每一个子节点直到找到绝对应的key
                    return ((HashMap.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);
            }
        }
        return null;
    }

扩容机制

为什么要扩容:缩小哈希抵触,进步性能

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;//以后map的总长度
        int oldThr = threshold;//以后map的阈值
        int newCap, newThr = 0;
        //1)判断以后容量是否大于0
        if (oldCap > 0) {
            //判断以后容量是否超过最大容量,如果超过则不持续扩容
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //否则判断以后容量扩容一倍后是否小于最大容量 && 旧的容量的长度要大于默认容量16
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
                //满足这两个条件,将阈值扩容一倍
                newThr = oldThr << 1; // double threshold
        }
        //2)如果以后容量不大于0,则判断以后阈值是否大于0
        else if (oldThr > 0) // initial capacity was placed in threshold
            //满足则新的容量等于以后阈值的值
            newCap = oldThr;
        //3)如果1和2都不满足,证实这是一个新创建的map
        else {               // zero initial threshold signifies using defaults
            //则新的容量等于默认容量16,新的阈值等于默认的负载因子*0.75 * 默认容量16
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 4)判断新的阈值是否等于0
        if (newThr == 0) {
            //满足的话,判断新的容量是否小于最大容量
            //满足的话判断新的容量*负载因子是否小于最大容量
            //如果小于,那么新的阈值等于新的容量*负载因子,如果不小于,则新的阈值等于最大容量
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                    (int)ft : Integer.MAX_VALUE);
        }
        //5)创立新的newTab表,笼罩掉本来的table
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        //6)如果旧的table表不等于空,遍历oldTab
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                HashMap.Node<K,V> e;
                //如果以后地位上的值不等于空,则将这给地位取出来赋给e,并把这个地位置空
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    //判断e.next是否等于空,如果等于空,从新计算索引地位并赋给newTab
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    //如果不等于空,判断是否为树节点,如果是拆分树节点并从新计算索引地位,赋给newTab
                    else if (e instanceof HashMap.TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //如果不是树节点,那么就是链表
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        //循环遍历该索引地位对应的链表
                        do {
                            next = e.next;
                            // 如果以后节点的hash值与oldTab的容量相与等于0,把该节点放到Lo的链表上
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            //如果不等于0,把这个节点放到Hi的链表上
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        //循环完结后别离判断Lo和Hi是否为空,如果不为空则把Lo和Hi的头节点别离放入newTab表里
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        //7)循环完结,扩容实现,返回新数组
        return newTab;
    }

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据