HashMap源码分析(一)——逐行分析

﹏ヽ暗。殇╰゛Y 2022-02-18 19:43 260阅读 0赞

首先，我们要了解一下HashMap的存储方式

#### 既然名字包含Hash，不难看出他是以hash值作为地址存储的，更确切的讲他是以哈希桶aka链地址的方式存储元素的 ####

如果不了解什么是哈希桶，或者想先看一下HashMap的实现特点参见——[HashMap实现特点——基于JDK文档][HashMap_JDK]

#### 哈希冲突采用的是哈希桶，桶中元素使用链表存储，但是如果元素过多，那么就会采用树的方式存储。树是HashMap中最重要的数据结构。 ####

--------------------

## 首先我们要通过源码分析HashMap的存储以及操作。 ##

1.  HashMap()构造方法
2.  putVal()方法
3.  resize()方法

##### HashMap是按照下面图示方式存储元素（如果没有哈希冲突），一个数组，数组中元素叫做节点也就是桶，所以首先我们需要了解节点。如果有哈希冲突，那么每个节点的桶就会存多个元素，文章下面有。 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE0NjM3OTQ_size_16_color_FFFFFF_t_70]  
下面是内部类Node：

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

可以看到，是一个很常见的节点的表达方式，下面这个图就没有写hash，因为hash使用制定存放地址的，这里的next一般是为了解决哈希冲突而设置的，本篇文章下面还有一幅图更详细  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE0NjM3OTQ_size_16_color_FFFFFF_t_70 1]

新建HashMap对象后，只有使用它，它才会初始化，也就是put语句，使用put后

## @pass是指由于条件语句为假所以不运行改语句块 ##

所以由于table为空，所以初始化也就是运行resize方法，tab = resize();**调用了resize**()方法  
继续向下看：

final Node<K,V>[] resize() {
    	//初始化table数组，或者加倍，先讨论初始化
            Node<K,V>[] oldTab = table;
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
    		//oldCap = 0;
    		//threshold: The next size value at which to resize (capacity * load factor).
            int oldThr = threshold;
            int newCap, newThr = 0;
    		@pass
            if (oldCap > 0) {
                if (oldCap >= MAXIMUM_CAPACITY) {
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // double threshold
            }
    		@pass
            else if (oldThr > 0) // initial capacity was placed in threshold
                newCap = oldThr;
            else {               // zero initial threshold signifies using defaults
    		//运行这一步。因为oldThr初始为0
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
    		
    		@pass
            if (newThr == 0) {
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
    		
            threshold = newThr;
    		//threshold初始化了
    		//开始新建一个Node数组，大小为newCap
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    		//table赋予值
            table = newTab;
    		@pass
           //下面代码也被省略
            
            return newTab;
        }

**目前就完成了初始化，得到一个默认容量的链表，然后继续执行putVal方法**

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;
    		//############################################################################
    		//上面已经执行过了，所以不用管，继续看下面
    		
    		//在条件语句中 i = 0
            if ((p = tab[i = (n - 1) & hash]) == null)
            	tab[0]也就是首元素 = newNode();所以我们继续看newNode()方法
                tab[i] = newNode(hash, key, value, null);
            else {
                //由于条件语句，跳过这些代码
            }
            //...也省略
            return null;
        }

// Create a regular (non-tree) node
        Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
            return new Node<>(hash, key, value, next);
        }

可以看到他是创建节点的函数，继续调用Node的构造方法，上面已经介绍了Node和它的构造方法，所以返回了一个新的节点，由于这是第一个节点，也就是头节点。继续添加节点和上面步骤一样，**不过需要注意的是，当遇到hash冲突时，也就是我们要存放一个元素，根据其hash值存放，不过检测到原节点数组该位置已经有元素，并且他们两个的key值不一样，这就遇到了hash冲突，所以我们会执行哈希桶，也就是链地址法去解决冲突**，如果不了解哈希桶，可以参见我另一篇文章；  
下面我介绍一下哈希冲突元素的添加：（从第一个哈希冲突介绍）

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
           //上面代码忽略，因为条件语句跳过。
    		
    		//运行下面这一句，p就获取了当前hash地址的节点，并且不为空，所以执行else中语句
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
                Node<K,V> e; K k;
    			//p已经被找到为旧节点
    			
    			//如果p.hash = hash p存放key = k，说明找到节点，并且没有出现hash冲突，e = p；
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
    				
    			//哈希冲突
    			 //因为p目前是第一个hash冲突元素，所以不运行下面这段
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    			
                else {
                    for (int binCount = 0; ; ++binCount) {
    					//因为是第一个hash冲突，所以p.next = null;
                        if ((e = p.next) == null) {
    						//先创建一个存放冲突节点的。此时冲突node之间是线性连接的
                            p.next = newNode(hash, key, value, null);
    						//哈希冲突数量过多就用类似TreeMap的形式存储
                            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;
        }

此图就讲解了Hash冲突的解决方案。如果哈希桶中元素过多会使用树去代替链表，树在HashMap中是很重要的一个结构，足足占了600行代码。以后会专门讲解。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE0NjM3OTQ_size_16_color_FFFFFF_t_70 2]

[HashMap_JDK]: https://blog.csdn.net/u011463794/article/details/89336279
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE0NjM3OTQ_size_16_color_FFFFFF_t_70]: /images/20220218/f7ef37f2a77e43dba140f6ca382e36de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE0NjM3OTQ_size_16_color_FFFFFF_t_70 1]: /images/20220218/a8cbc872541548b7831aed48465e3416.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE0NjM3OTQ_size_16_color_FFFFFF_t_70 2]: /images/20220218/07eebe6e46144131a23e33a42827734e.png