深入理解HashMap底层实现原理

一、HashMap （JDK8）put(K key, V value)底层实现

1. 首先判断这个hashmap是否为空，为空就初始化一个hashmap

2. 根据key 计算hashcode()值，和数组长度-1 进行&（等价于求余），得到bucket的位置

3. 得到位置后判断该处的值是否为空如果为空直接插入

4. 如果不为空，判断数组后面链接的是否是一棵树，是树就将其put到这颗树中。

5. 不是树，先挂在链表后面，然后判断链表大小是否大于8，大于8就要把链表转换成树

源码：

 public V put(K key, V value) {

         return putVal(hash(key), key, value, false, true);

     }

      /**

      * Implements Map.put and related methods

      *

      * @param hash hash for key

      * @param key the key

      * @param value the value to put

      * @param onlyIfAbsent if true, don't change existing value

      * @param evict if false, the table is in creation mode.

      * @return previous value, or null if none

      */

 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;

     /*如果table的在（n-1）&hash的值是空，就新建一个节点插入在该位置*/

         if ((p = tab[i = (n - 1) & hash]) == null)//&相当于取余

             tab[i] = newNode(hash, key, value, null);

     /*表示有冲突,开始处理冲突*/

         else {

             Node<K,V> e;

         K k;

     /*检查第一个Node，p是不是要找的值*/

             if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))

                 e = p;

             else if (p instanceof TreeNode)//数组后面是否为树，如果是树则将其put到树中

                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)

             else {//否则挂在链表后面

                 for (int binCount = 0; ; ++binCount) {

         /*指针为空就挂在后面*/

                     if ((e = p.next) == null) {

                         p.next = newNode(hash, key, value, null);

                //如果冲突的节点数已经达到8个，看是否需要改变冲突节点的存储结构，　　　　　　　　　　　　　

 　　　　　　　　　　　　//treeifyBin首先判断当前hashMap的长度，如果不足64，只进行

                         //resize，扩容table，如果达到64，那么将冲突的存储结构为红黑树

                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

                             treeifyBin(tab, hash);

                         break;

                     }

         /*如果有相同的key值就结束遍历*/

                     if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))

                         break;

                     p = e;

                 }

             }

     /*就是链表上有相同的key值*/

             if (e != null) { // existing mapping for key，就是key的Value存在

                 V oldValue = e.value;

                 if (!onlyIfAbsent || oldValue == null)

                     e.value = value;

                 afterNodeAccess(e);

                 return oldValue;//返回存在的Value值

             }

         }

         ++modCount;

      /*如果当前大小大于门限，门限原本是初始容量*0.75*/

         if (++size > threshold)

             resize();//扩容两倍

         afterNodeInsertion(evict);

         return null;

     }

二、扩容

hashmap 默认大小16，每次扩大两倍(增加一倍)，加载因子默认是0.75，当 hashmap容量大于数组长度 * 加载因子的时候就会扩容，也就是初始达到12 的时候就会扩容

扩容时先重建一个2倍长度的数组，然后重新 hash

加载因子表示数组填充的程度，加载因子越大填充的越满，空间利用率越高，但冲突越大，加载因子越小，空间利用率越低，但冲突小，一般平衡在0.75

为什么每次数组的大小都是2的次幂？

1.在计算哈希桶下标的时候hash值和数组长度减一按位与，数组长度是2的倍数减一二进制表示都是1，速度快；

2. hash & (array.length-1)相当于对array.length-1 取模运算，也就是 % 运算，&效率比%高；

3.数组长度是2的次幂，不同key求的hash值相同几率很小，冲突小，查询快

三、HashMap和HashTable的区别

1. hashmap 的 key 可以为 null，hashtable不行，为空时，hashcode默认为0。

2. hashtable是线程安全的，方法前面都有 synchronized 关键字。

3. hashtable继承Dictionary 类，hashmap继承 AbstractMap类,但都实现了 Map、Cloneable、Serializable接口

四、如何保证HashMap线程安全

1. 使用ConcurrentHashMap

2. Collections.synchronizedMap(new HashMap<String, Integer>());

巴特西

深入理解HashMap底层实现原理

最新文章

热门文章