Java HashMap 1.8 底层原理解析

左手的ㄟ右手 2022-05-22 00:12 345阅读 0赞

### HashMap 原理解析 ###

\* transient:关键字，不去参加序列化操作；

1. HashMap 用于存储数据的，想到底层数据的存储方式，存储数据需要有使用数据结构；

2. 常用的数据结构：数组，链表，树形，图形

*  1.这些数据结构对应的实现例子有那些：ArrayList---->数组存储， 数组查询速度快，没有节点数据都有下标，但是删除和添加效率低点，删除data2,他需要把data2后面的数据统一往前移动一位;  
    
 *  ![70][]
 *    
    
 *  2. LinkedList---->双向链表存储；双向链表的查询速度慢点，没有node节点没有下标，但是添加删除效率高，在第一个data后面插入一条数据不需要后面的数据统一移动，而是把数据前一个前一个node指向data1，后一个data指向data2；  
    
 *  ![70 1][]

*   3. HashMap 是结合数组、链表、红黑树进行存储的；默认数组长度DEFAULT\_INITIAL\_CAPACITY = 1 << 4; //16,当超过12长度时，采用两倍扩容，DEFAULT\_LOAD\_FACTOR = 0.75f用于判断HashMap扩容系数;
 *  Map<String,String> m = new HashMap();HashMap用于存储键值对的集合，每一个键值对也叫Node,这些键值对(Node)分散存储在数组中，这个数组就是HashMap的主干；
 *  class Node\{//HashMap 内部类
 *      int hash;//用于计算Node 存放位置  
    
 *      K key；//键  
    
 *      V value;//值  
    
 *      Node next;//指向下一个节点  
    
 *  \}
 *   *   ![70 2][]

*    
    
 *  往HashMap中put()一条数据时，需要计算这条数据存放的位置，同事需要Node节点存放位置要随机性，不能按照顺序放，不然链表就表示不出来随机性；  
    
 *  算法
 *   *  要知道Node 节点该往哪里存储，我们可能会猜测根据key的HashCode值与HashMap的长度取模运算？
     *  实现也就是这样 = hash(Key)\{ 
     *         int hash = key.hashCode
     *         int result = hash%length 结果0\-(length-1)之间
     *  \}这样做固然简单，但是效率较低；
    
    #####  #####
    
     *  HashMap是如何计算每个值的位置坐标同时还需要保证随机性位置呢？
    
     *  ![70 3][]
     *  我们先根据key得到它hash值，
     *  int hash(key)\{  
        
        
        int h ;
        
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16) ;\}
        
        然后在与(n-1）进行并运算，tab\[ (n - 1) & hash\])得到具体的下标；
     *  hash值的意义就是记录每一个node节点应该存储的位置；我们知道他的下标之后，进行node节点存放，存放之前需要先判断这个位置是否有node值存在（碰撞），如果没有碰撞就存放；  if ((p = tab\[i = (n - 1) & hash\]) == null)\{tab\[i\] = newNode(hash, key, value, null)\}
     *   如果不为null（有碰撞） ，有三种情况分析：
     *  1. 如果他们的hash相同或者他们的key相同，这个可以是进行值的覆盖，就不进行node节点添加；if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;
     *  2. 如果node采用的是红黑树存储，(p instanceof TreeNode) 添加一个红黑树节点；
     *  3. 如果采用的链表存储，for (int binCount = 0; ; ++binCount) \{ if ((e = p.next) == null) \{\}
     *   *  我们就需要循环遍历这个链表，谁的next下一个节点为空，为空就插入在他的下面；同时需要进行长度判断，如果长度大于8，自动转换成红黑树存储； if (binCount >= TREEIFY\_THRESHOLD - 1) \{treeifyBin(tab, hash);\}

\*    当单项列表的长度大于8时，单项链表会自动转换成红黑树存储，就不需要再单项链表中一级一级往下跑在进行插入，提高效率；

\*    当红黑树的节点数量小于6，自动换成链表数据存储；

*  两倍扩容之后需要重新计算每一个数据节点的hash值来摆放位置；
 *   *  为什么是两倍扩容？
     *   *  HashMap在长度超过12(而不是16)的时候进行自动扩容；为什么是2倍扩容，或者我们在手动设置HashMap的初始长度时，要是2的次幂？
         *  置我们往HashMap中put一条数据的位置，是根据hash&(n-1)计算出来的，
         *  Hash ----(h = key.hashCode()) ^ (h >>> 16)  低16bit ^ 高16bit 来确保值分散性  
            
         *  Length-1的值的所有二进制位都是1，这种情况下比对出来的位置比较均匀，不容易造成值的重复性；
     *  如果不是2的次幂会怎样？
     *   *  如果length的长度是10
         *  hash                 101001101100010000 1001
         *  Length-1                                        1001  
            
         *  Index                                              1001

*  Hash                 101001101100010000 1011     
    
 *  Length-1                                        1001
 *  Index                                              1001

*  hash                 101001101100010000 1111
 *  Length-1                                        1001  
    
 *  Index                                              1001  
    
 *  这样造成位置的严重重复性，所以length必须要是2的次幂；

*  HashMap根据我们的key得到的hash值需要与(n-1)并运算，降低我们位置的重复性，保证分散性，均匀性

*  两倍扩容之后，通过put添加新值时，如果当前位置不为空，设置为null；此时length长度发生改变，需要重新计算每一个Node的hash值，进行位置的重新摆放if ((e = oldTab\[j\]) != null) \{oldTab\[j\] = null;\}
 *   *  当前Node节点下没有数据及next=null，重新计算hash值，if (e.next == null)\{newTab\[e.hash & (newCap - 1)\] = e;\}
     *  e.hash & (newCap - 1) 根据当前hash计算位置；
     *  如有next有值，不管是红黑树还是链表，都进行位置的重新摆放；

![70 4][]

*      我们的get(key)方法做了哪些操作呢？  
    
 *  ![70 5][]
 *  首先根据我们的hash(key)获取到hash值，用于位置的计算;
 *  final Node<K,V> getNode(int hash, Object key) \{ 
    
        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) \{ 
    
    > //通过(n-1)&hash计算这个位置的node是否存在；
    
            if (first.hash == hash && // always check first node
    
                ((k = first.key) == key || (key != null && key.equals(k))))
    
    > //存在并且hash值和key值相同就返回当前node
    
                return first;
    
            if ((e = first.next) != null) \{ 
    
    > // 如果是红黑树存储的，就从红黑树里进行获取
    
                if (first instanceof TreeNode)
    
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
    
    > //如果是链表存储，就进行链表遍历查询，当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;
    
    \}
 *

[70]: /images/20220522/4235ef9b10f74fb593ffaae40f77a218.png
[70 1]: /images/20220522/884beba04edb4bc8b04660e75c3245b4.png
[70 2]: /images/20220522/4c9ef56425844b56b90094df305779d2.png
[70 3]: /images/20220522/2b7c50f9e6554f9a85f2d07a1916cec0.png
[70 4]: /images/20220522/f540b6b5c89c4851acb797a79bb37b06.png
[70 5]: /images/20220522/973839db3ddd437388763339c6dba323.png