HashMap 源码总结

谁践踏了优雅 2022-12-17 01:30 185阅读 0赞

## 1.运算规则 ##

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

## 2.哈希值 ##

哈希值: 通过一定的散列算法,把一个不固定长度的输入,转成一个固定长度的输出,输出的结果集map中,hash就是一个int值

哈希表: 存储哈希值的数组 – 存取散列值(哈希值)的一个容器

哈希值到底如何存,该如何取呢??? --通过数组的角标实现数据的存取

需要一个映射: 不同的hash值存在对应角标位 hash值 – 运算–>index

哈希函数: 将哈希表通过某种运算规则得到对应index

如何让存取效率是最高的??? —如果元素都是均匀储存在数据的角标位,而不产生冲突,就是效率最高的

① 尽可能少的产生hash冲突
        hash函数计算出来的角标要尽可能均匀
        static int indexFor(int h, int length){ 
        return h& (length-1);//length 是map中数组的长度
    }
    length长度的规则是什么??  -- 要求是2的幂次方,为啥???
        假如长度是8-1 ===7
        00000000000000000000000000000111  - - - 长度8,参与hash运算是7
        00000000000000000000000000001111  - - - 长度16,参与hash运算是15
        00000000000000000000000000011111  - - - 长度32,参与hash运算是31
        
        00110000100111000010101010100111  
     &  00000000000000000000000000001111 
    ----------------------------------------------
        00000000000000000000000000000000  --  00000000000000000000000000001111  
        [得到的值,正好是0-15的范围,该范围正好是长度为16的数组的角标]
        
        假设长度不是2的幂次方
        奇数  --长度5
         00110000100111000010101010100111  
     &   00000000000000000000000000000100  --长度5 参与hash运算是4
     ------------------------------------------
        得到的结果永远是一个偶数,代表获取的角标永远是偶数,奇数位的角标永远浪费
        [数组就浪费掉一半]
        
           偶数  --长度6
         00110000100111000010101010100111  
     &   00000000000000000000000000000101  --长度6 参与hash运算是5
     ------------------------------------------
        第二位永远是0,导致2,3角标位都不可能有值
        [数组就浪费掉一半]
        
        
        
        2的幂次方,在扩容时,扩容后的数组长度是原数组长度的2倍,结果还是2的幂次方有啥好处??
        假设原来是8
        			00000000000000000000000000000111
        扩容后是16
        			00000000000000000000000000001111
        
        在扩容时,数据要从原数组中迁移到新数组中
        		00000000000000000000000000001101
        	  & 00000000000000000000000000000111
        ------------------------------------------
        										101 === 5 原数组的角标位
        
        		00000000000000000000000000001101
        	  & 00000000000000000000000000001111
        ------------------------------------------
        										1101 === 13 (原角标位=扩容长度) 新数组的角标位
         [扩容后,数据迁移时,数据要么在原来位置,要么在原来位置+扩容长度不需要重新hash--效率更好]
        
        
        
        
        
        ②确实产生了hash冲突 -- 数据结构
        
        扩容
        	什么时候扩容
        		jdk 1.7:
         			判断是否到达阈值(0.75*数组长度)
         			同时是否产生hash冲突
        
        		jdk 1.8:
        			先添加原数
        			判断是否到达阈值
                       
            
            怎么扩容
                jdk1.7
                        添加元素使用头插法
                        将单项链表的数据进行迁移
                jdk1.8
                        添加元素使用尾插法
                        
                        如果对应角标位是单向链表,将单项链表进行数据迁移
                        如果对应角标位是红黑树,将双向链表进行数据迁移
                           如果发现迁移数据后,双向链表的结构小于/等于6,就会将红黑树重新转为链表
                
                        
                 扩容后有什么问题(多线程环境下)
        			jdk1.7
                        多线程环境下会形成环形链表
                    jdk1.8
                        多线程环境下会有数据丢失的问题
                        
        数据结构解决
                        jdk1.7产生冲突后,会形成单向链表
                        
                        jdk1.8产生冲突后
                        	  会形成链表
                        	  如果单向链表的长度大于/等于8,会转成红黑树+双向链表(扩容时使用

## 为什么要转红黑树？ ##

回答自然很简单，因为链表是取一个数需要遍历链表，
    复杂度为O(N)，而红黑树为O(logN)呗，那么问题来了
    
    为什么不直接使用红黑树，而是要先使用链表实在不行再转红黑树呢？
    
    答案自然要在源码和注释里找：在HashMap类中第174行左右有描述：
    
         Because TreeNodes are about twice the size of regular nodes, we
         use them only when bins contain enough nodes to warrant use
         (see TREEIFY_THRESHOLD)
    
    “因为树节点的大小是链表节点大小的两倍，
    所以只有在容器中包含足够的节点保证使用才用它”，
    显然尽管转为树使得查找的速度更快，但是在节点数比较小的时候，
    此时对于红黑树来说内存上的劣势会
    
    超过查找等操作的优势，自然使用链表更加好，但是在节点数比较多的时候
    ，综合考虑，红黑树比链表要好。
    
    为什么是8，而不是9不是10？
    
    看看源码的描述：
    复制代码
    
    Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution 
    with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although 
    with a large variance because of resizing granularity. Ignoring variance, the expected 
    occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). 
    The first values are:
          0:    0.60653066
          1:    0.30326533
          2:    0.07581633
          3:    0.01263606
          4:    0.00157952
          5:    0.00015795
          6:    0.00001316
          7:    0.00000094
          8:    0.00000006
          more: less than 1 in ten million
    
    复制代码
    
    理想情况下，在随机哈希码下，哈希表中节点的频率遵循泊松分布，
    而根据统计，忽略方差，列表长度为K的期望出现的次数是以上的结果，
    可以看到其实在为8的时候概率就已经很小了，再往后调整并
    
    没有很大意义。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MTI5MTQ4Mw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/3f133586b6874685bba7f5df0f011a8b.png