• HashMap源码

    HashMap

    HashMap实际上由数组，列表，红黑树组成

    插入一个，会生成一个节点Node

    Node包含：

    • Hash_Key
    • Key
    • Value
    • Node Next
    static int hash(int h) {
    return h ^ (h >>> 7) ^ (h >>> 4);
}

    • 1
    • 2
    • 3

    会根据路由寻址来决定插在数组的位置

    发生冲突，则插在同一个index的链表上

    在这里插入图片描述

    各个参数

    //默认哈希表大小
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;
//树化阈值 单链表的长度>8 则转为红黑树
static final int TREEIFY_THRESHOLD = 8;
//树降级成为链表的阈值 
static final int UNTREEIFY_THRESHOLD = 6;
//哈希表的元素达到64以后，树化。满足两个条件
static final int MIN_TREEIFY_CAPACITY = 64;
//哈希表增删后，会+-1
transient int modCount;
//扩容阈值
int threshold;


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    构造方法

    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;
    this.threshold = tableSizeFor(initialCapacity);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

    • 1
    • 2
    • 3
    public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

    • 1
    • 2
    • 3
    public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

    • 1
    • 2
    • 3
    • 4
    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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    Put方法

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

    • 1
    • 2
    • 3
    * @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
    
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    //tab：引用当前的hashMap的散列表
    //p:表示当前散列表的元素
    //n:表示当前散列表的长度
    //i:表示路由寻址的结果
    //
    //延迟初始化逻辑 
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    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 {
        Node<K,V> e; K k;
        //要插入的元素和当前元素的key和hash均一致，表示后续需要替换操作
        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) {
                
                //条件成立的话，说明迭代到了最后一个，也没找到一个与要插入元素的key一致的node
                //说明需要插入到末尾
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //列表元素达到8，则达到树化的条件
                    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;
            }
        }
        //替换
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;    
        }
    }
    //modCount：散列表被修改的次数，替换Node的value不计数
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

    • 1
    • 2
    • 3
    • 4

    resize扩容方法

    final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    //oldCap：表示扩容之前的表的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //oldThr：表示扩容之前的扩容阈值，触发本次扩容
    int oldThr = threshold;
    //newCap：表示扩容之后的表的长度
    //newThr：扩容之后，触发下次扩容的条件
    int newCap, newThr = 0;
    
    //已经初始化过，是一次正常扩容
    if (oldCap > 0) {
        
        //扩容前的表的长度已经达到最大阈值，通过将扩容条件设置为int 最大值，达到不扩容的效果
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        
        //MAXIMUM_CAPACITY=1<<30
        //DEFAULT_INITIAL_CAPACITY=16
        //oldCap左移一位实现翻倍，且赋值给newCap。newCap小于最大长度限制 且 扩容之前的阈值 >= 16
        //则，下一次扩容的阈值 等于当前阈值的翻倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    
    //oldCap = 0 hashMap中的散列表还是null
    //new HashMap(int initialCapacity, float loadFactor)
    //new HashMap(int initialCapacity)
    //new HashMap(Map m)
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    
    //oldCap = 0 ，oldThr = 0
    //new HashMap()
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    //newThr为零时，通过newCap和loadFactor计算出一个新newThr
    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"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    
    //在本次哈希表扩容前，table不为null
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            
            //当前node节点
            Node<K,V> e;
            //说明当前桶位有数据，但是数据具体是 单个数据 链表 红黑树 不知道
            if ((e = oldTab[j]) != null) {
                //置空，方便JVM GC时回收内存
                oldTab[j] = null;
                
                //第一种情况：当前桶位只有一个元素，从未发生过碰撞，这情况 直接计算出当前元素应该存放
                //在 新数组的位置，然后放入
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                
                //第二种情况：当前节点已经树化  
                else if (e instanceof 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;
                        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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114

    get方法

    public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

    • 1
    • 2
    • 3
    • 4
    final Node<K,V> getNode(int hash, Object key) {
    //tab:引用当前hashMap的散列表
    //first：桶位的头元素
    //e：临时node元素
    //n：表的长度
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    
    //判断是否存在数据
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        
        //第一种情况：头元素就是 我们要get的数据
        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 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);
        }
    }
    return null;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    remove方法

    public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    public boolean remove(Object key, Object value) {
    return removeNode(hash(key), key, value, true, true) != null;
}

    • 1
    • 2
    • 3
    final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    //tab:引用当前hashMap的散列表
    //p：当前元素
    //n：表的长度
    //index：表示寻址结果
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        //说明路由的桶位是有数据的，需要进行查找操作，并且删除
        
        //node：查找到的结果
        //e: 当前Node的下一个元素
        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) {
            //当前桶位 要么是 链表 要么是 红黑树
            
            if (p instanceof TreeNode)//判断当前桶位是否升级为 红黑树
                //第二种情况：
                //红黑树查找操作
                node = ((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);
            }
        }
        //equals方法重写过
        //判断node非空，按照key查找到需要删除的数据了
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            //第一种情况：node是树节点，需要进行树节点的删除
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            //第二种情况：桶位元素即为查找结果，则将该元素的下一个元素放入桶位中
            else if (node == p)
                tab[index] = node.next;
            //第三种情况：将当前元素p的下一个元素 设置成要删除元素的 下一个元素
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
  • 相关阅读:
    进大厂必备的Java八股文大全（2022最强精简易懂版，八股文中的八股文）备战秋招，赶快转发收藏起来吧~
    LeetCode算法题解（动态规划）|LeetCode509. 斐波那契数、LeetCode70. 爬楼梯、LeetCode746. 使用最小花费爬楼梯
    MySQL-InnoDB索引详解
    一级造价工程师（安装）- 计量笔记 - 第五章第四节静置设备与工艺金属结构工程
    【无标题】
    智能答题功能，CRMEB知识付费系统必须有！
    相似文本聚类与调参
    如何设计一张数据库表
    免费享受企业级安全：雷池社区版WAF，高效专业的Web安全的方案
    OpenHarmony中SystemAbility的实现方法
  • 原文地址：https://blog.csdn.net/weixin_45629803/article/details/133957943