【Java容器源码】HashMap（一）底层结构分析

我会带着你远行 2022-12-05 10:17 275阅读 0赞

> HashMap 系列：
> 
>  *  [【Java容器源码】HashMap（一）底层结构分析][Java_HashMap]
>  *  [【Java容器源码】HashMap（二）添加元素及树化源码分析][Java_HashMap 1]
>  *  [【Java容器源码】HashMap（三）扩容源码分析][Java_HashMap 2]
>  *  [【Java容器源码】HashMap（四）获取 value 及迭代器源码分析][Java_HashMap 2]
>  *  [【Java容器源码】HashMap（五）源码分析&死锁问题（JDK7）][Java_HashMap_JDK7]
>  *  [【Java容器源码】关于HashMap的几个问题][Java_HashMap 3]

从 HashMap 的类注释中，我们可以得到如下信息：

*  允许 null 值，不同于 HashTable ，是线程不安全的；
 *  load factor（负载因子） 默认值是 0.75， 是均衡了时间和空间损耗算出来的值，较高的值会减少空间开销（扩容减少，数组大小增长速度变慢），但增加了查找成本（hash 冲突增加，链表长度变长），不扩容的条件：数组容量 > 需要的数组大小 /load factor；
 *  如果有很多数据需要储存到 HashMap 中，建议 HashMap 的容量一开始就设置成足够的大小，这样可以防止在其过程中不断的扩容，影响性能；
 *  HashMap 是非线程安全的，我们可以自己在外部加锁，或者通过 Collections\#synchronizedMap 来实现线程安全，Collections\#synchronizedMap 的实现是在每个方法上加上了 synchronized 锁；
 *  在迭代过程中，如果 HashMap 的结构被修改，会快速失败。

HashMap 继承关系，核心成员变量，主要构造函数：

public class HashMap<K,V> extends AbstractMap<K,V>
        	implements Map<K,V>, Cloneable, Serializable {
        
        	 //---------------------------------默认值---------------------------------
        	 // 初始（数组）容量为 16
             static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
        
             // 最大容量
             static final int MAXIMUM_CAPACITY = 1 << 30;
        
             // 负载因子默认值（又或者说扩容因子）
             static final float DEFAULT_LOAD_FACTOR = 0.75f;
        
             // 当数组容量大于 64 时，链表才会转化成红黑树
             static final int MIN_TREEIFY_CAPACITY = 64;
    
    		//（桶上的）链表长度大于等于8时，链表转化成红黑树
    		// 注：如果数组容量不大于等于64，那么会再触发一次数组扩容，而不是当前槽点的链表转红黑树
             static final int TREEIFY_THRESHOLD = 8;
        	
             //（桶上的）红黑树大小小于等于6时，红黑树转化成链表
             static final int UNTREEIFY_THRESHOLD = 6;
        	
        	//--------------------------------属性-----------------------------------
            // 负载因子，当已有槽点点占总槽点数的比值，达到后扩容
            // 可理解为，一个数组能用的槽点只用 ~%
            final float loadFactor;
            
             // 记录迭代过程中 HashMap 结构（数组）是否发生变化，如果有变化，迭代时会 fail-fast
             transient int modCount;
        
             // HashMap 实际的 Entry 数量，即节点数量（Node + TreeNode）
             transient int size;
        
             // 存放数据的数组
             transient Node<K,V>[] table;
        
             // 阈值，两个作用：初始容量 --> 扩容阈值
             int threshold;  
             
             //-------------------------------Node---------------------------------------------
             // 链表的节点
             // 注：一个哈希桶中的node，hash和key可能都不相同，因为槽点是通过hash%(n-1)得到的
             static class Node<K,V> implements Map.Entry<K,V> {
        //Map.Entry是个接口
             	// 当前node的hash值，作用是决定位于哪个哈希桶，是通过key的hashCode计算来的
             	// 注：1.不直接使用 key 定位哈希桶是因为，不是所有 key 都是 Integer
    	        // 	   2.不同 key 可能算出相同 hash 值
             	//     3.将hash单独作为属性是因为，每次使用时都通过key计算会使代码复杂冗余
                final int hash; 
                // 可能是包装类实例可能是自定义对象，
                final K key; 
                V value;
                // 指向当前node的下一个节点，构成单向链表
                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;
                }
        
                public final K getKey()        {
         return key; }
                public final V getValue()      {
         return value; }
                public final String toString() {
         return key + "=" + value; }
        
                public final int hashCode() {
        
                    // Objects.hashCode 防止空指针
                    return Objects.hashCode(key) ^ Objects.hashCode(value);
                }
        
                public final V setValue(V newValue) {
        
                    V oldValue = value;
                    value = newValue;
                    return oldValue;
                }
        
                public final boolean equals(Object o) {
        
                    if (o == this)
                        return true;
                    if (o instanceof Map.Entry) {
        
                        Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                        if (Objects.equals(key, e.getKey()) &&
                            Objects.equals(value, e.getValue()))
                            return true;
                    }
                    return false;
                }
            }
            
            //-------------------------------TreeNode-------------------------------------------
            // 红黑树的节点
            // 注意：这里是直接继承 LinkedListMap.Entry，而 LinkedListMap.Entry 是继承自 HashMap.Node
            // 只不过它扩充了双向链表的 before、after
         	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
    	        boolean red;
    			
    			//......
    	    }
         	
         	//---------------------------构造方法----------------------------------------------
         	
         	// 空参构造
            public HashMap() {
        
            	// 使用默认负载因子 = 0.75
                this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
            }
    
    		// 初始（数组）容量
            public HashMap(int initialCapacity) {
        
            	// 初始容量 + 默认负载因子 0.75
                this(initialCapacity, DEFAULT_LOAD_FACTOR);
            }
            
         	// 初始（数组）容量，负载因子
         	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;
                // 不是直接就使用传入的初始容量，而是要经过 tableSizeFor() 处理，使最终结果是2的幂
                this.threshold = tableSizeFor(initialCapacity);
            }
               
        }

这里我们主要关注 Capacity 和 threshold

**1.Capacity （数组大小）必须是2的幂**

1）目的：保证计算槽点位置 tab\[i = (n - 1) & hash\] 的结果在 \[0,Cap-1\] 之间

2）实现

*  空参构造：16
 *  指定 initialCapacity：通过 threshold = tableForSize(cap) 计算出初始容量，得到 >= cap 且最接近的2的幂  
    比如 给定初始化大小 19，实际上初始化大小为 32，为 2 的 5 次方
 *  后续扩容 resize() >> 1

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

**2.threshold阈值**

threshold 有两个作用：

1）初始容量

在扩容 resize() 中使用，用于指定容量时的初始化，threshold = tableSizeFor(initialCap)，

注：

1.  此时 threshold 肯定是 2 的幂
2.  初始化完成后就直接变成 newThr = NewCap\*0.75 成为扩容阈值

2）扩容阈值

然后用于记录数组扩容阈值，= 数组容量\*0.75，在 putVal() 中使用

注：当 threshod=Integer.MAX\_VALUE 无法再扩容

[Java_HashMap]: https://blog.csdn.net/weixin_43935927/article/details/108501752
[Java_HashMap 1]: https://blog.csdn.net/weixin_43935927/article/details/113884949
[Java_HashMap 2]: https://blog.csdn.net/weixin_43935927/article/details/113886585
[Java_HashMap_JDK7]: https://blog.csdn.net/weixin_43935927/article/details/108502329
[Java_HashMap 3]: https://blog.csdn.net/weixin_43935927/article/details/108733304