02-03-01、HashMap的源码实现

原创
2020/03/11 03:09
阅读数 101

(JDK1.8)

基本思想:

1、以一个 Node<K,V>[] table  数组存放K-V数据,当调用put方法时,计算Khash值,HashCode &  (table.size - 1) 即可得到一个0-(table.size - 1)之间的一个数值,然后将K-V存放到这个值对应的 table  数组 的index位置。  (存放)

2、K-V被一个Node内部类封装,  Node内部类实现了Map.Entry接口,因此一个HashMap实例的table数组中每一项存放的都是一个Map.Entry实例。一个Node就是一个节点,它有指向下一个节点的指针,在出现hash碰撞时,会将相同hash值的K-V放在table 数组中index相同的位置,并加入到Node组成的结构当中,这个结构可以是链表,也可以是红黑树。(hash碰撞处理)

3、将数据放入table后,如果数据数量 > 容量*负载因子,则新建一个容量为原来容量两倍的新table,遍历原来的数组并将数据重新放入到新的table中。(调整table容量)

4、通过get()方法获取K对应的V时,先计算K的hashcode,HashCode &  (table.size - 1) 即可得到一个0-table.size之间的一个数值,找到数组对应的位置,使用equals()方法比较传入的K与Node的K是否一致,一致则返回对应的V,否则继续找Node指向的下一个Node进行比较,遍历完依然没有,则返回null。(获取数据)

 

具体实现:

1、构造函数

HashMap有两种构造函数:

    public HashMap(int initialCapacity, float loadFactor) {
        // 略...
        this.loadFactor = loadFactor;  // 设置负载因子,一个大于0的单精度浮点数,默认值:0.75f
        this.threshold = tableSizeFor(initialCapacity);  // 会根据容量计算得到一个最接近的2的n次幂的数作为容量,默认值:16
    }
    public HashMap(Map<? extends K, ? extends V> m) {
        // 以一个map作为构造参数,如果这个map有值,则会初始化一个容量为的table,并将这个map的值都放入到table中
        this.loadFactor = DEFAULT_LOAD_FACTOR;  // 负载因子,默认值:0.75f
        putMapEntries(m, false);
    }

 

2、存入数据的过程

1、判断table是否已经初始化,若未初始化则调用resize()方法初始化table。从构造方法中可知,构造时并没有初始化table,而是到putVal()时才进行初始化table
2、检查table中与新传入的可以对应的位置是否有数据,table数组对应位置没有数据,直接放入新的Node。
3、 table数组对应位置已经存在数据,则可能出现了hash碰撞,也可能是更新数据,需进一步处理
    3.1、已经存在的值 和 新put的值的hash、key都一样,说明是要更新数据,更新数据后即可返回,因此更新数据不会触发扩容
   3.2、 如果已近存在的节点是红黑树节点,这将k-v参数放入树中,若树中已经存在该key,则修改该Node的值即可返回;如不存在,则将新的k-v加入树的新节点。
   3.3、 如果存在的节点是一个链表节点,且头结点与传入的key不一样,则需遍历链表进行比较处理
           3.3.1、新传入key不存在,证明是新的key,所以在链表的表尾插入新的Node。插入新节点后,如果链表长度大于等于8,将链表转成红黑树
            3.3.2、 传入的key与某个节点相同,遍历结束,修改节点值即可返回。
4、若是新增数据,则数据计数增1。如果新增数据后,数据量 > 容量*负责因子,则进行扩容。(完成)

源码如下:

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }


    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; 
        Node<K,V> p; 
        int n, i;

        // 1、判断table是否已经初始化,若未初始化则调用resize()方法初始化table
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;           // 从构造方法中可知,构造时并没有初始化table,而是到putVal()时才调resize()方法初始化table

        // 2、如果table已经初始化过了,并且table数组对应位置没有数据,直接放入新的Node
        if ((p = tab[i = (n - 1) & hash]) == null) // 需要注意的是此处是(n-1)& hash,n是容量,是一个2的某次幂的数,n-1和一个数按位与可以得到0-(n-1)的之间的任意一个整数
            tab[i] = newNode(hash, key, value, null);  
        else {
        // 3、 table数组对应位置已经存在数据,则可能出现了hash碰撞,也可能是更新数据,需进一步处理
            Node<K,V> e; K k;

            // 3.1、已经存在的值 和 新put的值的hash、key都一样,说明是要更新数据,到后面的if中更新即可
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p; 
            else if (p instanceof TreeNode)
            //3.2、 如果已近存在的节点是红黑树节点,这将k-v参数放入树中,若树中已经存在该key,则返回对应的Node,如不存在,则将新的k-v加入树的新节点,并返回null
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
            //3.3、 如果存在的节点是一个链表节点,且头结点与传入的key不一样,则需遍历链表进行比较处理
                for (int binCount = 0; ; ++binCount) {
                   // 3.3.1、新传入key不存在,证明是新的key,所以在链表中新增一个新的Node
                   if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null); // 将新节点放在链尾,因此这里采用的是尾插法
                        if (binCount >= TREEIFY_THRESHOLD - 1) // 插入新节点后,如果链表长度大于等于8,将链表转成红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 3.3.2、 传入的key与某个节点相同,遍历结束,后面修改节点值即可
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // 更新value值
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);   // 数据被更新后的hook方法
                return oldValue;
            }
        }
        ++modCount;    // 新增数据计数
        // 4、 如果新增数据后,数据数据 > 容量*负责因子,则进行扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);   // 新增数据后的hook方法
        return null;
    }

 

3、触发扩容的操作和扩容过程

扩容的条件:

HashMap触发扩容的有两个临界条件

  • 数据量  >  容量 * 负载因子
  • table容量  <  64  ,并且    table中存在某一个位置新增数据后链表长度  >=  8

以上两个临界条件,只要满足一个条件即会引发扩容操作。

 

触发扩容的操作:

put(K key, V value)、putAll(Map<? extends K, ? extends V> m);

首先需要明确的是,扩容的实现方法时resize()方法,但其中还包含了初始化table  数组的实现,因此并非所有调用了resize()方法的都是进行扩容操作。因此,实际的触发扩容的两个方法时put()和putAll()。

 

扩容的过程:

1、计算出新table的容量,为原table的2倍
2、遍历原table,将原table中的数据取出,放入到新table中
    2.1、当前位置只有一个Node,直接rehash再放入新table
    2.2、当前节点是红黑树节点,遍历红黑树,将Node rehash存入新table
    2.3、当前位置是多节点的链表
        2.3.1、通过hash & oldCap计算出Node是否在新table中的索引位置不变,然后分别使用两个头指针 和 两个尾指针 分别指向不需要改变位置 和 需要改变位置的Node,构建出两个新的链表,并把它们放到新table中的当前索引 和 当前索引 + oldCap的位置。

resize()方法源码

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;

        // 1、计算出新table的容量,为原table的2倍
        // 省略 计算新table容量过程 ...

        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            // 2、遍历原table,将原table中的数据取出,放入到新table中
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;      // 将j位置设置为空,此时get将不再可取到数据,因为get的逻辑是tab[tab.length & hash]) != null

                    if (e.next == null)    
                    // 2.1、当前位置只有一个Node,直接rehash再放入新table
                        newTab[e.hash & (newCap - 1)] = e;   // 注意此处也是 hash & (newCap - 1)
                    else if (e instanceof TreeNode)    
                    // 2.2、当前节点是红黑树节点,遍历红黑树,将Node rehash存入新table
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else {
                    // 2.3、当前位置是多节点的链表

                        // 此处分别使用两个头指针 和 两个尾指针 分别指向不需要改变位置 和 需要改变位置的Node,构建出两个新的链表,并把它们放到新table中
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;

                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) { // 注意,此处是 hash & oldCap,值为0意味着到了新table这些Node依然还是会落到当前index的位置
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;  // 位置不变的链表数据,依然放在新table的当前位置
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead; // 位置发生变化的链表数据放到新table的j+oldCap位置
                        }
                    }
                }
            }
        }
        return newTab;
    }

从构造方法、put() 和 resize() 方法的源码中可以发现一个比较值得去思考的东西:

  • 为什么初始化table时,要将容量设置成一个2的幂的一个数?
  • 为什么put时,存放数据的位置是 (n - 1) & hash ,而判断数据在新table的存放位置是否发生变化时使用的是  (e.hash & oldCap) == 0  ?
  • 为什么将只有一个Node的位置的数据存放到新table中的位置时 e.hash & (newCap - 1),而多值链表位置发生变化的链表放入新table 的位置是 j + oldCap ?
  • 为什么将数据放入新table是没有对hash碰撞的处理?

带着上面的疑问,首先从 & (按位与)运算开始,&运算是将数据的二进制按位进行与运算,然后得到一个新的二进制。如:

                         00000001             |                                 00000001     
1 & 2  <=>   &                                 |        1 & 3  <=>   &                        
                        00000010              |                                 00000011      
                        ---------                 |                                 ----------
                        00000000             |                                 00000001      

可以知道,按位与运算只有两个数的相同位都为1时,得到的结果的对应位才会是1,否则是0。

我们再来看看2的m次幂(m为大于等于0的整数)的数的二进制的情况:2^0 = 1 = 00000001 ;2^1 = 2 = 00000010 ;2^2 = 4 = 00000100 ;……    2的m次幂其实就是 1  << m,它的二进制只有第m位(从0开始向左数)是1,其他为都是0。

那么就可以好理解“为什么put时,存放数据的位置是 (n - 1) & hash”这个问题了,n是一个2的m次幂的数,那么n-1是一个后m位都是1的二进制数,那么无论什么样的一个整数与(n-1)按位与,得到的数都将不会大于n-1,而是一个 0 - (n-1) 区间的一个整数,这样就能将 hash 映射到table的 0 - (n-1)个位置上了。假设 n = 16 ,则 (n - 1) & hash 如下:

                         000001111                     |                                 000001111     
15 & 999  <=>   &                                 |        15 & 1000  <=>   &                        
                        1111100111                      |                                 1111101000     
                        -----------                     |                                 ------------
                        00000111                       |                                  00001000      

选取位置还可以通过 hash%n  获得,但位运算速度更快。

为什么“判断数据在新table的存放位置是否发生变化时使用的是  (e.hash & oldCap) == 0  ”呢?

从HashMap的源码中可知,每次扩容都是扩容为原来的两倍,也就是n<<1,如原来是16 (二进制 10000),变成原来的两倍,即32 (二进制  100000),(e.hash & oldCap) == 0 表明hash的二进制数的第m位(n=2^m,从0开始右往左数)一定是0, 那么hash 与 2n-1的二进制按位与,第4位也依然是0,因此这样的 hash值  (n - 1) & hash   和  (2n - 1) & hash   是相等的,因此可知,(e.hash & oldCap) == 0 的节点在新table的位置是不变的。如:

                     000001111           |                              000010000       |                          000011111    
15 & 999  <=>   &                    |     16 & 999  <=>   &                     |    31 & 999  <=>   &                   
                    1111100111            |                              1111100111          |                          1111100111   
                    -----------           |                              ------------        |                          ------------ 
                    00000111             |                               00000000         |                           00000111    

那么“多值链表位置发生变化的链表放入新table 的位置是 j + oldCap ”这个问题和上面的问题类似,hash & (n-1) = j,位置发生变化的Node的hash的第m位(n=2^m,从0开始右往左数)一定是1,因此,hash & (2n-1) = j + oldCap。

那么,“为什么将只有一个Node的位置的数据存放到新table中的位置时 e.hash & (newCap - 1)”,因为无法确认hash的二进制的第m为是0还是1,所以需要进行重新计算。

为什么将数据放入新table是没有对hash碰撞的处理?”这个问题也和上题类似,因为在oldTable中用链表存储的,都已经以链表的形势转移到newTable中了,其他的Node不会与其他的碰撞,因为它的hash的位要么是0,要么是1。是0,则落在原位置上,不会冲突;是1,则落在 j + oldCap位置,也不会冲突。

从上面几个问题的回答可知,“为什么初始化table时,要将容量设置成一个2的幂这么一个数呢?”,这就是作者的巧妙设计,如果不是2的幂,那么以上的这些操作都只能取模,rehash也只能重复进行,也无法判断哪些Node的位置不变。

与capacity 设置为2的幂相一致的是kye的hash的计算方法,其方法源码如下:

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

Object.hashCode()方法返回的是一个int的整数,int 长度为 4字节,即32位,00000000 00000000 00000000 00000000,因为 计算key在table中的位置使用的是 (n - 1) & hash,而n是2的幂的一个数,即便n为2^15(32768),也只占用了后16位,因此如果不对key.hashCode()的值进行处理,那么key.hashCode()的值的高16位在大部分的时间内都将不会被使用,这将大大提高hash碰撞的可能,因此计算key的hash时,通过对 key.hashCode() 进行无符号右移16位(h>>>16)将高位数向低位移动,然后进行异或计算得到最终的hash值,从而使数据更分散。

 

(不得不佩服 @author Doug Lea  的这波骚气操作,不仅是这里,还有像线程池、CHM等地方都留下了他炉火纯青的位运算用法,膜拜!膜拜!

 

4、HashMap线程不安全的原因

线程不安全是因为有数据的共享与竞争引起的:

  • 在插入新的Key时,会将新的Node放到链表的链尾,如果是并发的情况,当两个线程同时获取到同一个链表当前的链尾的next指针,并将其指向各自新加入的Node时,将会出现数据的丢失;
  • 在扩容时,若有两个线程同时进行扩容,那么将会出现两个新的table,最终将会有数据丢失。

 

5、使用HashMap注意事项

  • 使用Final的Object作为key,最好不要使用非final的Object作为Key,可能会引发内存泄漏;
  • 作为key的对象重写hashCode()方法后,一定要重写equals()方法,不然可能会存入业务意义上的重复数据;
  • 可以使用null作为key,因为HashMap默认null的hashCode为0,但也只能有一个key为null。
  • 因为Value可以是null,因此在需要判断key是否已经放入HashMap中时,要用containsKey(Object key)方法,而不是通过get(Object key)方法是否返回null来判断。

 

 

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

写得不好,说得不一定对,希望您带着批判性阅读,希望您能多提提宝贵意见,希望不误人子弟。也没很细致校对,错误之处望不吝指出,谢谢!

展开阅读全文
打赏
0
0 收藏
分享
加载中
该评论暂时无法显示,详情咨询 QQ 群:912889742
详情链接: http://suo.im/6gl5S1
2020/03/11 12:55
回复
举报
更多评论
打赏
2 评论
0 收藏
0
分享
返回顶部
顶部