专栏首页Java学习录Java集合-HashMap源码解析-JDK1.8

Java集合-HashMap源码解析-JDK1.8

HashMap简介

HashMap在jdk 1.8中使用用的是数组+链表+红黑树的结构来进行存储的,请看下图:

当要对一个HashMap进行增删改查等操作时,一般情况下都是先根据key的Hash值定位到key在左侧数组桶的位置,然后判断当前的数组桶是使用的链表存储还是使用了红黑树存储。

举一个简单的例子,我们要往HashMap中添加一个元素21,经过一个特定Hash算法得出的结果是索引0,所以我们把21这个元素放到了数组桶索引0的第一个位置上,因为这个时候索引0的位置上还没有元素,所以是以链表的方式存储的,接着继续添加33节点。。。如上图

接着当索引3的位置上的元素超过了一个界限以后,如果还使用链表的方式进行存储的话效率比较低,所以把整个链表转换成了红黑树进行存储

HashMap的属性

HashMap的一些基础属性:

 /**     * 默认的初始容量 默认16     */    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    /**     * 最大容量,2的30次方     */    static final int MAXIMUM_CAPACITY = 1 << 30;
    /**     * 默认扩展因子,比如初始情况下,当键值对的数量大于 16 * 0.75 = 12 时,就会触发扩容     */    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /**     * 当某个箱子中,链表长度大于 8 时,有可能会转化成树     */    static final int TREEIFY_THRESHOLD = 8;
    /**     * 哈希表扩容时,如果发现链表长度小于 6,则会由树重新退化为链表     */    static final int UNTREEIFY_THRESHOLD = 6;
    /**     * 在转变成树之前,还会判断一次,只有键值对数量大于 64 才会发生转换。     */    static final int MIN_TREEIFY_CAPACITY = 64;    /**     * 存储数据的Entry数组     */    transient HashMap.Node<K, V>[] table;
    /**     * HashMap的大小,它是HashMap保存的键值对的数量     */    transient int size;
    /**     * HashMap被修改的次数     */    transient int modCount;
    /**     *  当前 HashMap 所能容纳键值对数量的最大值,超过这个值,则需扩容     * (threshold = 容量*实际扩展因子)     */
    int threshold;
    /**     * 实际的扩展因子     *     * @serial     */    final float loadFactor;

HashMap存储数据所使用的链表数据结构:

/**     * 单向链表     */    static class Node<K, V> implements Map.Entry<K, V> {        //hash值        final int hash;        //键        final K key;        //值        V value;        //下一个节点        HashMap.Node<K, V> next;
        Node(int hash, K key, V value, HashMap.Node<K, V> next) {            this.hash = hash;            this.key = key;            this.value = value;            this.next = next;        }
    }

HashMap存储数据所使用的红黑树数据结构:

 static final class TreeNode<K, V> extends LinkedHashMap.Entry<K,V>{

        HashMap.TreeNode<K, V> parent;  // red-black tree links        HashMap.TreeNode<K, V> left;        HashMap.TreeNode<K, V> right;        HashMap.TreeNode<K, V> prev;    // needed to unlink next upon deletion        boolean red;
        TreeNode(int hash, K key, V val, HashMap.Node<K, V> next) {            super(hash, key, val, next);        }  }

HashMap的构造方法

  • 因子的构造方法 */ public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); //如果指定的初始容量大于预定义允许的最大容量则使用预定义允许的最大容量 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; //计算当前HashMap的容量 this.threshold = tableSizeFor(initialCapacity); } /** * 指定初始容量及加载因子的构造方法,加载因子使用默认0.75f */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * 默认构造方法,初始容量为16,加载因子为0.75f */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } /** * 包含子map的构造方法 */ public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; // 将m中的全部元素逐个添加到HashMap中 putMapEntries(m, false); } /** * 根据初始容量计算计算当前HashMap的容量 * 检查所传的参数是否为2的幂次方 * 如果不为2的幂次方则将其变为比cap大的最小的2的幂次方的值 */ 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; }

HashMap的添加方法

/**     * 添加方法     */    public V put(K key, V value) {        return putVal(hash(key), key, value, false, true);    }     /**     * 计算key的hash     */    static final int hash(Object key) {        int h;        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);    }
    /**     * 具体的添加方法     */    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;        //如果Map为空或者容量为0        if ((tab = table) == null || (n = tab.length) == 0)            //扩容            n = (tab = resize()).length;        if ((p = tab[i = (n - 1) & hash]) == null)            tab[i] = newNode(hash, key, value, null);        else {            HashMap.Node<K, V> e;            K k;             // 如果键的值以及节点 hash 等于链表中的第一个键值对节点时,则将 e 指向该键值对            if (p.hash == hash &&                    ((k = p.key) == key || (key != null && key.equals(k))))                e = p;            // 如果桶中的引用类型为 TreeNode,则调用红黑树的插入方法            else if (p instanceof HashMap.TreeNode)                e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);            else {                // 对链表进行遍历,并统计链表长度                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;                }            }            // 判断要插入的键值对是否存在 HashMap 中            if (e != null) { // existing mapping for key                V oldValue = e.value;                // onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值                if (!onlyIfAbsent || oldValue == null)                    e.value = value;                afterNodeAccess(e);                return oldValue;            }        }        ++modCount;
        if (++size > threshold)            // 键值对数量超过阈值,进行扩容            resize();        afterNodeInsertion(evict);        return null;    }

整个添加方法主要包含以下逻辑:

  1. 判断Map是否初始化,如果没有初始化则通过扩容的方式进行初始化操作
  2. 判断要添加的节点是否等于通过hash计算出的索引的位置的第一个链表元素
  3. 判断此位置的元素是否是使用红黑树存储,如果是则调用红黑树的添加方法
  4. 此位置的元素使用的是链表存储,判断新插入的元素在链表中存在,如果存在则替换,不存在就插入到列表最后。计算链表是否需要转换为红黑树
  5. 添加结束之后再次判断是否需要扩容

HashMap的扩容

 /**     * 扩容方法     */    final HashMap.Node<K, V>[] resize() {        HashMap.Node<K, V>[] oldTab = table;        //HashMap的长度        int oldCap = (oldTab == null) ? 0 : oldTab.length;        //当然HashMap容量        int oldThr = threshold;        //新的HashMap长度和容量        int newCap, newThr = 0;        //判断数组桶是否初始化        if (oldCap > 0) {            //如果超过了数组的最大容量值,则扩容到Integer.MAX_VALUE            if (oldCap >= MAXIMUM_CAPACITY) {                threshold = Integer.MAX_VALUE;                return oldTab;            }            //newCap=hashMap的长度*2            //newCap<最大容量且>=初始容量            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                    oldCap >= DEFAULT_INITIAL_CAPACITY)                //newThr=扩容的阈值*2                newThr = oldThr << 1; // double threshold        }        //没有初始化,并且扩容阈值大于0        else if (oldThr > 0) // initial capacity was placed in threshold            newCap = oldThr;        else {            // 调用无参构造方法时,桶数组容量为默认容量,            // 阈值为默认容量与默认负载因子乘积            newCap = DEFAULT_INITIAL_CAPACITY;            newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);        }        //newThr 为 0 时,按阈值计算公式进行计算        if (newThr == 0) {            float ft = (float) newCap * loadFactor;            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?                    (int) ft : Integer.MAX_VALUE);        }        threshold = newThr;        //创建新的数据缓冲区        @SuppressWarnings({"rawtypes", "unchecked"})        HashMap.Node<K, V>[] newTab = (HashMap.Node<K, V>[]) new HashMap.Node[newCap];        table = newTab;        // 如果旧的桶数组不为空,则遍历桶数组,并将键值对映射到新的桶数组中        if (oldTab != null) {            for (int j = 0; j < oldCap; ++j) {                HashMap.Node<K, V> e;                if ((e = oldTab[j]) != null) {                    oldTab[j] = null;                    if (e.next == null)                        newTab[e.hash & (newCap - 1)] = e;                    else if (e instanceof HashMap.TreeNode)                        //对红黑树进行拆分                        ((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);                    else { // preserve order                        HashMap.Node<K, V> loHead = null, loTail = null;                        HashMap.Node<K, V> hiHead = null, hiTail = null;                        HashMap.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;                        }                    }                }            }        }        return newTab;    }

整个扩容方法主要包含以下逻辑:

  1. 首先判断HashMap是否已初始化,没有初始化则执行初始化逻辑
  2. 如果已初始化则进行扩容HashMap 。正常情况下按当前桶数组长度的2倍进行扩容,阈值也变为原来的2倍(如果计算过程中,阈值溢出归零,则按阈值公式重新计算)
  3. 将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型,则需要拆分红黑树。如果是普通节点,则各个节点重新进行hash

HashMap的查找

 /**     * 根据键获取值     */    public V get(Object key) {        HashMap.Node<K, V> e;        return (e = getNode(hash(key), key)) == null ? null : e.value;    }
    /**     * 具体的查找方法     */    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;        //定位键值对所在桶的位置        //tab=table        //n=table.length        //first=table[table.length-1]        //k=first.key        //e=first.key        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 HashMap.TreeNode)                    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;    }

查找时先定位键值对所在的桶的位置,然后再对链表或红黑树进行查找

HashMap的删除

  • 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; //如果桶不为空 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; //如果查找的键在第一个位置 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; else if ((e = p.next) != null) { //如果是红黑树类型,则调用红黑树的方法查找到key的位置 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); } } // 根据具体的类型删除节点 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); else if (node == p) tab[index] = node.next; else p.next = node.next; ++modCount; --size; afterNodeRemoval(node); return node; } } return null; }

同样的套路,先定位桶,然后根据类型进行操作。

鉴于篇幅有限,本篇文章仅列出上方部分代码,HashMap完整源码解析请点击下方“阅读原文”查看!!!

本文分享自微信公众号 - Java学习录(Javaxuexilu),作者:Java学习录

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java集合-TreeMap源码解析-JDK1.8

    TreeMap在jdk 1.8中使用用的是红黑树的结构来进行存储的,一个典型的红黑树就如下图所示:

    Java学习录
  • Eureka获取服务列表源码解析

    在之前的文章:EurekaClient自动装配及启动流程解析中,我们提到了在类DiscoveryClient的构造方法中存在一个刷新线程和从服务端拉取注册信息的...

    Java学习录
  • 科普:为什么SpringBoot中main方法执行完毕后程序不会直接退出呢

    大部分人应该都知道使用System.exit()或Runtime.exit()可以直接导致当前JVM进程退出,但是仔细想想这个好像跟SpringBoot没啥关系...

    Java学习录
  • Java集合必会14问(精选面试题整理)

    答:通过分析源码我们知道了HashMap通过resize()方法进行扩容或者初始化的操作,下面是对源码进行的一些简单分析:

    Java3y
  • JDK1.8源码分析之HashMap

    HashMap是一种Map,HashMap仅是一种Map的实现版本,下面的图片展示了java中Map的一些实现版本:

    九州暮云
  • 死磕Java之聊聊HashMap源码(基于JDK1.8)

    HashMap是Java程序员使用频率最高的数据结构之一。另外,JDK1.8对HashMap底层的实现进行了优化,如引入红黑树的数据结构以及扩容的优化等等来提高...

    haifeiWu
  • Java集合必会14问(精选面试题整理)

    答:通过分析源码我们知道了HashMap通过resize()方法进行扩容或者初始化的操作,下面是对源码进行的一些简单分析:

    我没有三颗心脏
  • Java集合必会14问(精选面试题整理)

    答:通过分析源码我们知道了HashMap通过resize()方法进行扩容或者初始化的操作,下面是对源码进行的一些简单分析:

    乔戈里
  • Java HashMap工作原理及实现(干货)

    发生了什么呢?下面是一个大致的结构,希望我们对HashMap的结构有一个感性的认识:

    用户1257215
  • JDK8中的HashMap实现原理及源码分析

    在写上一篇线性表的文章的时候,笔者看的是Android源码中support24中的Java代码,当时发现这个ArrayList和LinkedList的源码和Ja...

    技术zhai

扫码关注云+社区

领取腾讯云代金券