Java基础底层-HashMap底层源码分析

旧城等待， 2022-12-25 15:47 197阅读 0赞

## 一、概述 ##

在了解hashMap之前需要先了解下常见的数据结构 数组，链表，红黑树；以及hash碰撞

*  数组：  
    数组具有遍历快增删慢的特点。数组在堆中有一块连续的存储空间，首地址知道后，就能快速遍历任意元素；增删慢是因为当中间插入或者删除元素时，会造成元素后面的所有元素地址的改变
 *  链表：  
    链表具有增删快遍历慢的特点。链表中各个元素的内存空间不连续，在遍历时，需要从第一个开始依次拿到地址才能遍历到需要的第n个元素；增删快是因为在进行操作时只需要修改该位置的前驱结点和后继节点，其他元素不做变动。
 *  红黑树：  
    是一种自平衡二叉查找树，是计算机科学领域中的一种数据结构，典型的用途是实现关联数组，存储有序的数据；（此处大致概括，不做赘述）
 *  Hash碰撞：  
    hash碰撞是指两个元素通过hash函数计算出的值是一样的，是同一个存储地址。当后面的元素要插入到这个地址时，发现已经被占用了，这个时候就产生了hash碰撞。
    
    > 解决Hash碰撞的方法  
    > 开放地址法： 找查询产生冲突地址的下个地址，直到寻找到空的地址；  
    > 再哈希法： 再哈希法又叫双哈希法，有多个不同的hash函数，当发生冲突时，使用第二个哈希函数计算地址直到无冲突；  
    > 建立公共溢出区： 将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素一律填入溢出表  
    > 链地址法：将所有哈希地址相同的元素按照顺序记录在同一链表中；(HashMap底层使用此方法解决hash碰撞)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0h1YW5nMTE3ODM4Nzg0OA_size_16_color_FFFFFF_t_70]

*  **HashMap**：  
    Hash表是一个数组+链表的结构；在jdk1.7中，只是单纯的数组+链表的结构；在jdk1.8中，当hash上的链表长度大于8时（此处有歧义，具体看后面的扩容机制），该节点的数据就不在以链表存储二是转成一个红黑树进行存储  
    jdk7到jdk8 hashmap数据结构的变化主要是因为同一个hash值存储在一个链表中时，如果元素较多则查询的效率会变得很低，而当链表长度大于8时将链表转换为红黑树大大减少了查找时间。

## 二、 HashMap实现原理 ##

> 存储结构是一个数组链表，即每个数组中的元素都是一个首节点的链表。当添加一个元素（key-value）时，会通过hash函数计算key的hash值，以此确定插入数组中的位置。  
> 但是可能存在同一个hash值的元素已经被放在数组同一个位置（hash碰撞）；出现hash碰撞后就会把这个元素存储在同一个hash值的元素后面，即形成了链表，同一个链表上的hash值是相同的；  
> 当链表长度太长时，链表就转换为红黑树，这样就大大提高了查找效率

*  原理图  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0h1YW5nMTE3ODM4Nzg0OA_size_16_color_FFFFFF_t_70 1]

## 三、源码解析 ##

#### 1. 继承关系 ####

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

继承AbstractMap，AbstractMap是继承于Map的抽象类，实现了Map中大部分的API；实现了Cloneable，表示支持克隆；实现了Serializable，则支持序列化  
疑问： 为什么继承了AbstractMap还要实现Map:这是类库设计者的拼写错误（设计者曾经认为这样写有价值，但是后来发现并没有意义），HashMap不应该实现Map的

#### 2. 主要成员变量 ####

##### 2.1 主要成员 #####

一般将数组中的每一个元素称作桶（segment），桶中连的链表或者红黑树中的每一个元素成为bin  
capacity： 源码中没有明确表示此属性；是指hashMap中桶的数量，默认为16

// 序列化ID
    	private static final long serialVersionUID = 362498820763181265L;
    	// 默认初始化容量 2^4=16
    	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
    	// 最大的容量 2^30 
    	static final int MAXIMUM_CAPACITY = 1 << 30;
    	// 默认resize的因子 ：即实际数量超过总数Default_Load_Factor的数量会发生resize动作
    	static final float DEFAULT_LOAD_FACTOR = 0.75f;
    	// 树化阈值8；当单个segment(链表)的容量超过阈值时，会将链表转化为红黑树
        static final int TREEIFY_THRESHOLD = 8;
        // 链化阈值 6；当resize后或者删除操作后单个segment（红黑树）的容量低于阈值时，将红黑树转化为链表
        static final int UNTREEIFY_THRESHOLD = 6;
        // 最小树化容量；当数组的segment(链表)被树化时，最下的hash表容量，低于该容量不会被树化
        static final int MIN_TREEIFY_CAPACITY = 64;
        // 表示当HashMap的size大于threshold时会执行resize操作；threshold=capacity*loadFactor
        int threshold;
        // 装载因子，用来衡量HashMap满的程度；默认值为0.75f；计算HashMap的实时装载因子的方法是size/capacity
        final float loadFactor;

##### 2.2 哈希桶数组 #####

// hash桶数组
        transient Node<K,V>[] table;	
        transient Set<Map.Entry<K,V>> entrySet;
        transient int size;
        transient int modCount;

##### 2.3 结点Node #####

存储信息的结点Node，数组桶存放的就是此结点；每个数组桶中的结点又是该结点所在链表上的首节点。（原理图）

static class Node<K,V> implements Map.Entry<K,V> { 
       		final int hash;	//对应的hash值
            final K key;	//键值对 Key （唯一）
            V value;		//键值对 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;
            }
    
            public final K getKey()        {  return key; }
            public final V getValue()      {  return value; }
            public final String toString() {  return key + "=" + value; }
    
            public final int 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;
            }
        }

#### 3. 构造函数 ####

//默认构造函数，赋值加载因子为默认的0.75f
    	public HashMap() { 
           	this.loadFactor = DEFAULT_LOAD_FACTOR; 
        }
        //指定初始化容量的构造函数
        public HashMap(int initialCapacity) { 
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
        //同时指定初始化容量 以及 加载因子， 用的很少，一般不会修改loadFactor
        public HashMap(int initialCapacity, float loadFactor) 
       { 
    		//边界处理
    		if (initialCapacity < 0)
        		throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        	    //初始容量最大不能超过2的30次方
    		if (initialCapacity > MAXIMUM_CAPACITY)
    			initialCapacity = MAXIMUM_CAPACITY;
    		//显然加载因子不能为负数
    		if (loadFactor <= 0 || Float.isNaN(loadFactor))
    			throw new IllegalArgumentException("Illegal load factor: " +	loadFactor);
    		this.loadFactor = loadFactor;
    		//设置阈值为 》=初始化容量的 2的n次方的值
    		this.threshold = tableSizeFor(initialCapacity);
    	}
    
        //新建一个哈希表，同时将另一个map m 里的所有元素加入表中
    	public HashMap(Map<? extends K, ? extends V> m) { 
    		this.loadFactor = DEFAULT_LOAD_FACTOR;
    		putMapEntries(m, false);
    	}

#### 4. 主要方法介绍 ####

##### 4.1 Hash函数介绍 #####

// 扰动算法的作用，为什么长度取2的幂->解释：https://www.cnblogs.com/ljxt/p/11612735.html
    	// 异或运算： https://blog.csdn.net/weixin_40539125/article/details/85688919 ：参加运算的两个对象，如果两个相应位为“异”（值不同），则该位结果为1，否则为0
    	//获取位置下标 ^ 是异或运算 / >>> 位运算 右移16位，取低位数
    	// 上面这段代码叫做“扰动函数” 是HashMap对应的Hash函数；此方法获得key值对应的hash值
    	static final int hash(Object key) { 
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
        // jdk源码中的模运算是在indexFor()方法中完成的，indexFor()方法的代码很简单，就是把散列值和数组长度做一个“与”操作
        // 此方法是针对hash值找出该值对应的下标：hash值对桶长度取模
        static int indexFor(int h, int length){ 
        	return h & (length - 1);
    	}
    	// 桶数组下标
    	bucketIndex = indexFor(hash, table.length);

##### 4.2 Put方法 #####

public V put(K key, V value) { 
            return putVal(hash(key), key, value, false, true);
        }
        // 参数onlyIfAbsent表示是否替换原值 默认为否
        // 参数evict我们可以忽略它，它主要用来区别通过put添加还是创建时初始化数据的
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { 
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            // 空表，需要初始化
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;	// resize不仅用来调整大小，还用来进行初始化配置
    
            // 非空表，判断hash位置是否有元素，实际位置是hash%(length-1)
            if ((p = tab[i = (n - 1) & hash]) == null)
            	// 没有元素，直接插入
                tab[i] = newNode(hash, key, value, null);
            else { 
            	// 有元素,此时需要进行三次判断
                Node<K,V> e; K k;
                // 有元素，Key值相等，则覆盖对应value(此处可能是修改操作)
                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 { 
                	// 要把待插元素插在链尾
                    for (int binCount = 0; ; ++binCount) { 
                    	// 找到链尾节点
                        if ((e = p.next) == null) { 
                        	// 将待插元素插入到链尾
                            p.next = newNode(hash, key, value, null);
                            // 判断当前链表长度是否大于8（binCount>=7)
                            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();
            afterNodeInsertion(evict);
            return null;
        }

##### 4.3 Get方法 #####

public V get(Object key) { 
            Node<K,V> e;
    		// 计算hash值，与key一起找value
    		// 找得到对应的value则返回该值，找不到则直接为null
            return (e = getNode(hash(key), key)) == null ? null : e.value;
        }
    	
    	final Node<K,V> getNode(int hash, Object key) { 
            Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    		//如果该hash表不为空，获取该key值对应的数组桶结点first
            if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { 
    			// 如果first满足条件，则直接返回
                if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
                    return first;
    			// 如果第一个不符合条件，则找下一个结点
                if ((e = first.next) != null) { 
    				// 如果对应的结点类型是红黑树，则使用红黑树获取key值
                    if (first instanceof TreeNode)
                        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
    				// 如果不是红黑树，遍历链表，找到对应hash和key的node结点对象
                    do { 
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            return e;
                    } while ((e = e.next) != null);
                }
            }
            return null;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0h1YW5nMTE3ODM4Nzg0OA_size_16_color_FFFFFF_t_70]: /images/20221120/eece8c564e994c579673b1853ca54cd9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0h1YW5nMTE3ODM4Nzg0OA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201202160101785.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0h1YW5nMTE3ODM4Nzg0OA==,size_16,color_FFFFFF,t_70