• 面试-Java【之】HashMap原理，源码逐行分析，理论总结（变量、常量、数据结构、Node、TreeNode、初始化、添加、查询、更新、删除）

    面试-Java【之】HashMap原理，源码逐行分析，理论总结（变量、常量、数据结构、Node、TreeNode、初始化、添加、查询、更新、删除）

    1.源码分析

    1.HashMap属性与变量（扩容因子、扩容阈值、结构转换阈值…）

     public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
     
     //默认扩容的临界值（table大于此值时，进行扩容）
     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
     //扩容临界值的最大值
     static final int MAXIMUM_CAPACITY = 1 << 30;

     //链表转红黑树的大小阈值（当链表长度大于8时，并且数组长度大于64时， 链表数据结构，转为红黑树）
     static final int TREEIFY_THRESHOLD = 8;
     //链表转红黑树的大小阈值（当链表长度大于8时，并且数组长度大于64时， 链表数据结构，转为红黑树）
     static final int MIN_TREEIFY_CAPACITY = 64;
     //红黑树转链表的阈值（当链表长度小于6，并且数组长度小于64时， 红黑树数据结构，转为链表）
     static final int UNTREEIFY_THRESHOLD = 6;

 	//当前扩容因子（扩容时的倍数），默认0.75f
     static final float DEFAULT_LOAD_FACTOR = 0.75f;

 	//数组（内部存储 Node链表节点，或者，TreeNode红黑树节点）
     transient Node<K,V>[] table;
     //扩容的临界值（table大于此值时，进行扩容）,默认值 DEFAULT_INITIAL_CAPACITY
     int threshold;
 	//当前扩容因子（扩容时的倍数）
     final float loadFactor;
 }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    2.Node（链表节点）

    public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {

 static class Node<K,V> implements Map.Entry<K,V> {
     	//当前节点-hash
        final int hash;
     	//当前节点-key   
     	final K key;
    	//当前节点-value   
     	V 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;
        }
 }
}

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

    3.TreeNode（红黑树节点）

    public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {

   static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
       	//父节点
        TreeNode<K,V> parent;  // red-black tree links
        //相邻左侧节点
       	TreeNode<K,V> left;
       	//相邻右侧节点
       	TreeNode<K,V> right;
       	//上一页 
       	TreeNode<K,V> prev;    // needed to unlink next upon deletion
        
       	TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
   }
}

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

    4.初始化（new）

    public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
	
	//设置扩容因子，和，扩容临界值，并未初始化数组
    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);
    }

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

	//设置扩容因子，和，扩容临界值，并未初始化数组
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
	
	//无参构造函数，设置扩容临界值，并未初始化数组
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

	//设置扩容临界值，并，插入数据
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
 }

    • 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

    5.插入、更新（put、putVal）

    public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {

   	//key : 键
	//value : 值
	//hash(key) : 调用对象自身的 hash方法
	public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
	final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
       
        //tab:当前数组
        //i:数据在tab中的索引下标
        //p:在tab中，key对应的下标节点数据，也就是 tab[i]
        //n:tab长度
        Node<K,V>[] tab; Node<K,V> p; int n, i;

        //如果tab为空，执行初始化或扩容数组
        //resize() ：初始化或扩容数组
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        
        //如果tab中当前位置没有数据，直接创建并插入节点
        //i是tab中，数据对应存放的位置： = (n - 1) & hash
        //p是tab中，数据对应存放的值
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        
        //如果位置上已经有数据，此时出现冲突
        else {
            
            //对比当前位置数据的Key，与将要插入的数据的Key，如果一致，直接替换数据  e = p;
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            
           	//如果Key不一致，判断是否为红黑树节点，是则插入数据
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
           
          	//如果Key不一致，也不是红黑树节点
            else {
                
                //循环比对当前链表内的Key
                //如果不存在，则直接插入，如果存在一致，则替换
                for (int binCount = 0; ; ++binCount) {
                   
                    //如果不存在，则直接插入
                    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;
                    }
                    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;
        //判断扩容阈值
        if (++size > threshold)
            resize();
        //在HashMap中这里是空实现
        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
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85

    6.删除（remove、removeNode）

    public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {

    //key:删除条件KEY
	public V remove(Object key) {
        //e:被删除的节点
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }
    
    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
       	//tab:当前数组
        //n:当前数组长度
        //index:key对应的在数组中的下标
		//p:key对应在数组中的数据 ,也就是tab[index]
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        
        //如果tab不等于空，并且对应index下标位置有数据，则判断通过
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
           
          	 //node：将要被删除的节点
            Node<K,V> node = null, e; K k; V v;
            
             //继续判断，hash相同，key相同，则被删除节点就是当前下标数据，也就是 node=tab[index]
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            
            //如果当前位置Node节点不满足条件，则继续判断
            else if ((e = p.next) != null) {
                
                //如果当前节点是红黑树，则获取节点数据，赋值给node
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
               
                //否则，循环从链表中读取，找到后，赋值给node
                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 TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                
                //删除Node节点(将原有位置数据的引用，指向链表中下一个数据，实现删除逻辑)
                else if (node == p)
                    tab[index] = node.next;
                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
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74

    7.读取（get、getNode）

     public class HashMap<K,V> extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable {
    
    //e:读取结果
	public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
	
    final Node<K,V> getNode(int hash, Object key) {
        
      	//tab:当前数组
        //n:当前数组长度
		//first:key对应在数组中的数据 , 也就是tab[index]
        //k:first的key
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        
        //数组不为空，并且first不等于空，继续执行
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            
            //first的 hash与key 和 传入的一致，证明 first就是查询结果，直接返回
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            
            //比对结果不一致，继续判断
            if ((e = first.next) != null) {
                
                //如果first位置的Node是红黑树，直接获取数据
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                
                //如果first位置的Node是链表，遍历链表获取数据
                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
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    2.理论总结

    1.核心：数组+ 链表或者红黑树

    • 核心：数组Node<K,V>[] table + 链表或者红黑树
    • 因为这种存储结构，所以，HashMap的查询效率高：第一次查询是 O(1) , 第二次是 O(n)
    • 1.初始化：new：确定 扩容因子 loadFactor 和 临界点 threshold,并没有初始化数组，初始化数组是在第一次查询数据时 resize()内实现的

    2.put 操作：首次插入：无冲突情况

    • 2.put 操作：首次插入：无冲突情况
      • 1.计算KEY的Hash值 ; 例如 “a” 的HashCode 是 97
      • 2.判断临界点 threshold 是否扩容，更新临界点
      • 3.创建Node（链表结构） ，存放位置 i = (数组长度 - 1) & hash
      • 4.再次判断并更新临界点

    3.put 操作：继续操作：出现突情况时

    • 3.put 操作：继续操作：出现突情况时
      • 当 存放位置 i = (数组长度 - 1) & hash 已经存在数据时
      • 先判断节点类型，链表还是红黑树
      • 是链表，遍历链表
      • 如果当前节点的下一个节点不存在，直接创建插入Node，如果存在判断KEY是否相同，相同就覆盖，不同就继续循环
      • 创建插入Node后，判断长度，是否转为 红黑树
        • binCount >= TREEIFY_THRESHOLD - 1 链表长度大于8 并且
        • (n = tab.length) < MIN_TREEIFY_CAPACITY 并且 数组长度大于64
    • 是红黑树，创建节点插入即可

    4.删除：remove

    • 4.删除：remove
      • 1.计算 KEY 的 Hash值， 找到数组中的位置
      • 2.判断KEY是否相同，相同直接删除，不同就判断当前 链表/红黑树 中下一个节点的数据
      • 3.删除：将当前位置指向 next数据，实现从链表中删除数据的功能

    5.获取：get

    • 5.获取：get
    • 1.计算 KEY 的 Hash值， 找到数组中的位置
    • 2.判断，数组不为空，并且first不等于空，继续执行，为空直接返回NULL
    • 3.如果first位置的Node是红黑树，getTreeNode（） 获取数据
    • 4.如果first位置的Node是链表，遍历链表获取数据

    6.补充

    • 默认扩容的临界值初始16
    • 扩容因子（扩容时的倍数），默认0.75f
    • 链表转红黑树（当链表长度大于8时，并且数组长度大于64时， 链表数据结构，转为红黑树）
    • 红黑树转链表的阈值（当链表长度小于6，并且数组长度小于64时， 红黑树数据结构，转为链表）
    • Node节点是一个Map链表结构，特点是 next
    • TreeNode 是一个 LinkedHashMap ,特点是 parent 父节点 left right prev（上一页）

    《目录：Java-JDBC学习》

    《幕》

    • 留白 —<老吉>
    • ~ 今 ~ ❀ ~ ❀❀❀❀❀❀❀❀❀❀ ❀❀❀❀❀❀❀❀❀❀ ❀❀❀❀❀❀❀
  • 相关阅读:
    LoadRunner下载与安装
    PyTorch常用代码段合集
    使用GGML和LangChain在CPU上运行量化的llama2
    浏览器内置NoSQL数据库IndexedDB
    Unity --- 网格链接与动态障碍物
    自动挂载管理
    网络数据采集-免费全网数据采集软件
    Stream Collectors.groupingBy的四种用法 解决分组统计（计数、求和、平均数等）、范围统计、分组合并、分组结果自定义映射等问题
    java中的serializable接口作用
    微信小程序调起微信支付
  • 原文地址：https://blog.csdn.net/m0_37969197/article/details/125518658