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

Java学习录

发布于 2019-04-18 15:09:06

2810

发布于 2019-04-18 15:09:06

文章被收录于专栏：Java学习录Java学习录

◆

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;    }

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

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

◆

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;    }

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

首先判断HashMap是否已初始化，没有初始化则执行初始化逻辑
如果已初始化则进行扩容HashMap 。正常情况下按当前桶数组长度的2倍进行扩容，阈值也变为原来的2倍（如果计算过程中，阈值溢出归零，则按阈值公式重新计算）
将键值对节点重新映射到新的桶数组里。如果节点是 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完整源码解析请点击下方“阅读原文”查看！！！

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2019-04-08，如有侵权请联系 cloudcommunity@tencent.com 删除

node.js