HashMap(JDK1.8)

    HashMap是一个散列桶(数组和链表或数组和红黑树),它存储的内容是键值对(key-value)映射,不是线程安全的,HashTable是线程安全的 
    首先,我们先看下HashMap结构 
image.png

HashMap最外层为数组,JDK1.8优化,默认会将超过8个元素的桶转换成红黑树,否则则为链表形式
在这篇中我们将每个数组位置称为桶

一、参数说明

        //HashMap初始容量,必须为2的幂 (默认:16)
       final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
       // HashMap最大容量,必须为2的幂  (默认:1 << 30)                        
       final int MAXIMUM_CAPACITY = 1 << 30;
       //默认装载因子0.75f  (默认:0.75f)                         
       final float DEFAULT_LOAD_FACTOR  = 0.75f;
       //当桶中元素个数超过这个值,将从链表节点转变为红黑树(默认:8)                         
       final int TREEIFY_THRESHOLD = 8;
       //当桶中元素个数小于这个值,将从红黑转变为树链表节点(默认:6)
       final int UNTREEIFY_THRESHOLD = 6;
       /**table表中元素超过这个值 才会将通中元素转换成红黑树,否则则扩容table
         *  这个值应该大于 4*REEIFY_THRESHOLD 
         *  避免红黑树和扩容之间冲突
         *(默认:64)**/
       final int MIN_TREEIFY_CAPACITY = 64;
        //hash表
       transient Node<K,V>[] table
        //保存缓存的entrySet()
       transient Set<Map.Entry<K,V>> entrySet
       // HashMap长度
       transient int size  
        //记录HashMap的修改次数  put()和get() 等方法会进行++操作                                                                         
       transient int modCount 
        //临界值 当HashMap中元素超过这个值,会触发HashMap扩容
       int threshold  
        //hash表装载因子
       final float loadFactor;   

二、内部类说明

1.链表类

      static class Node<K,V> implements Map.Entry<K,V> {
         //HashMap  key的hash值
        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; }
       //此hash值区分HashMap key的hash值
        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;
        }
    } 

2 红黑树类

     红黑树目前不做摘录

三、方法说明

1.创建方法

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
    /**这个方法一定会返回2的幂
    * 说明:n |= n >>> 1 等价为 n = n| n>>> 1
    * | 或操作(相同位只要一个为1即为1) 
    *     n |= n >>> 1;
    *     n |= n >>> 2;
    *     n |= n >>> 4;
    *     n |= n >>> 8;
    *     n |= n >>> 16
    *    会将 字节码低位全部置为1
    *    int n = cap - 1; 是为了防止出现 2的最大幂的出现
    *    因为字节码首位1之后都是1的字节码 ,加1后首位进1
    *    就变成了 首位为1 之后都为0 的字节码
    *    也就意味着  类似  cap 为 7会返回 8 
    *    
    **/
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

也就是说我们创建HashMap时候,无论规定长度多少,threshold 的长度都为2的幂
注意:当我们初始化传入HashMap 长度时候 threshold 赋值 发生在创建时期
当我们不指定HashMap 长度时候 threshold赋值 发生在put时期

2.put()方法

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    /**
      *  新的元素存放于哪个桶里边 是由key的hash和哈希表长度散列决定
      *   i =  (n - 1) & hash   
      *  & 操作 同时为1,则对应结果位也为1
      * 由此可以看出位于同一桶中元素 的hashcode值并不一定相同
      * @param onlyIfAbsent  if true, don't change existing value
      *如果为true,则出现相同key值时候并不会覆盖原来的value值,(不包括null,value为null,onlyIfAbsent不论true或者false都可以覆盖 )
      * @param evict if false, the table is in creation mode.
      *  如果为假,则表处于创建模式
     **/
    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;
        if ((p = tab[i = (n - 1) & hash]) == null)
           //如果这个位置没有元素,则新增
            tab[i] = newNode(hash, key, value, null);
        else {
           //p是为红黑树或者链表
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //如果元素的hash值及key相等,也就意味着插入相同key值元素
                e = p;
            else if (p instanceof TreeNode)
               //如果这个桶类型为 红黑树
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                  //如果这个桶类型为链表
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        //尾部插入(jdk1.7在头部插入)
                        p.next = newNode(hash, key, value, null);
                        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;
                }
            }
            //在这里我们判断e是否为null,不为null则代表之前存在相同key值
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                //这也是上面我们的解释是为什么值为null,都会覆盖掉。
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
               //LinkedHashMap实现
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
          //LinkedHashMap实现
        afterNodeInsertion(evict);
        return null;
    }

3.resize() 方法

    /**Table 扩容
     ** JDK1.8扩容时,采用头复制,避免链表循                
    **环死锁问题。**/
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
           //对于最大长度限制
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //如果当前hash表长度 扩容1倍后不超过长度限制 则进行扩容
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
             //如果我们刚开始创建HashMap不指定长度,put 会进入这里
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        //hash表扩容
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    //oldTab[j] 为null,但是e指向oldTab[j],e不为null
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        //树形结构
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                       //hi存放扩容后的数据,链表中的数据可能在扩容后位置发生变动,附图解释
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            /**e.hash & oldCap,&运算 2个都为1结果才为1,因为从上面得知只                                      
                             **能为2的幂oldCap ,结果只能为0或者oldCap,
                             **,*/
                            if ((e.hash & oldCap) == 0) {
                                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) {
                           /**对于链表尾节点处理 ,假设链表存在 a→b→c→d元素,a→c继续落    
                              **   到桶1,但是上面代码未对 c的next节点处理,会导致链表
                              ** a→c→d存在,所以要对尾节点处理 **/          
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

对于HashMap扩容链表中数据可能存在以下情况,扩容前


image.png

扩容后 元素位置如下


image.png

4.get()方法

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

 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) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(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;
    }


查找方法JDK1.8增加对红黑树查找

5.remove()方法

remove方法我们不常用,这里我们看下逻辑

    public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
     //查找这个key所在hashtab中的位置
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            //对比第一个元素是否key相等
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
           //否则去对比链表或树
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                       //p为node的上个节点
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
               //如果要移除掉的节点是链表头结点,直接将它的下一个结点替换为桶节点
                else if (node == p)
                    tab[index] = node.next;
                else
               //前面说过p为node上一个节点,所以这里可以将node移除
                    p.next = node.next;
                ++modCount;
                --size;
                //LinkedHashMap实现
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

四、几个问题

1、HashMap为什么线程不安全

HashMap线程不安全主要体现2个方面
1.在调用put()方法时,如果有2个线程添加元素到相同桶中,因为新的元素会添加到Node next 属性,所以有可能造成数据缺失。HashMap链表插入会执行以下代码

  for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    //尾部插入
                    p.next = newNode(hash, key, value, null);              
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }

我们假设HashMap中有个桶中存在2个相同hashcode元素a和b ,有2个线程t1和t2要对这个桶分别插入 c和d,桶的初始结构如下


image.png

假设 t1和t2 都运行到 p.next = newNode(hash, key, value, null)这句(假设已经完成newNode(hash, key, value, null),但是没指向p.next),此时p为b元素
,t1线程没有获得cpu运行,t2将d元素插入,t2插入后结构如下


image.png

这时t1获得cpu运行,t1将c 指向 p.next,插入后结构如下,导致d元素缺失
image.png

2.在resize()方法时
我们假设有2个线程t1和t2,假设扩容前HashMap结构如下(我们在resize()举例的)
假设扩容后a和c还继续在桶1,b和d在桶5


image.png
   table = newTab;
        //hash表扩容
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {       
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    //oldTab[j] 为null,但是e指向oldTab[j],e不为null
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        //树形结构
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                       //hi存放扩容后的数据,链表中的数据可能在扩容后位置发生变动,附图解释
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {                                                            标记1
                            next = e.next;
                            /**e.hash & oldCap,&运算 2个都为1结果才为1,因为从上面得知只                                      
                             **能为2的幂oldCap ,结果只能为0或者oldCap,
                             **,*/
                            if ((e.hash & oldCap) == 0) {
                                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) {                        标记2
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }

假设t1先快速执行标记1 while循环
第一遍while循环

next  = e.next = a.next =b;
/**我们假设a还是落到桶1 **/
loHead = e = a;
loTail = e = a;

第二遍while循环

next  = e.next = b.next =c;
/**我们假设b还是落到桶5**/
hiHead = e = b;
hiTail = e = b;

第三遍while循环

next  = c.next = c.next =d;
/**我们假设c还是落到桶1  loTail .next 此时相当于将a.next指向了c**/
loTail .next = a.next =c ;
loTail = e = c;

第四遍while循环

next  = e.next =c.next =d;
/**我们假设b还是落到桶5   hiTail.next 此时相当于将a.next指向了d**/
hiTail.next= b.next = d;
hiTail = e =d;

t1循环执行完毕
此时t1没有继续往下执行代码,t2开始执行循环
第一遍while循环

next  = e.next = a.next =c;
/**我们假设a还是落到桶1 **/
loHead = e = a;
loTail = e = a;

第二遍while循环

//没有标记2对尾节点处理 c的next是还指向d的/
next  = c.next = c.next =d;
/**我们假设c还是落到桶1  loTail .next 此时相当于将a.next指向了c**/
loTail .next = a.next =c;
loTail = e = c;

第三遍while循环

next  = e.next = d.next =null;
/**我们假设b还是落到桶5   hiTail.next 此时相当于将a.next指向了d**/
hiHead = e = d;
hiTail = e = d;

t2循环执行完毕
t1继续执行标记2代码 t2在t1执行完毕后再执行,最终HashMap结构如图,发生元素d缺失


image.png

2、链表插入为什么在尾节点插入新的数据

在插入hashcode相同但是key不同的数据时候,jdk1.7采用头部插入,但是1.8采用尾部插入,这样做有什么好处?,上面我们看了1.8的结构,这里简单对HashMap(JDK1.7)做了介绍https://www.jianshu.com/p/eab549ac0359
有很多人说1.8尾插法避免了1.7中扩容死循环问题,链表只是一种数据结构,尾插法和头插法,如果不考虑数据因素,并不会改变链表最终的数据结构,不会因为尾插法和头插法造成死循环,1.8解决扩容死循环问题在于1.8采用从链表头进行复制,复制迁移过程并没有像JDK1.7一样复制完链表逆序排列
关于1.8为什么采用尾插法,后续待补充

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 213,864评论 6 494
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,175评论 3 387
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 159,401评论 0 349
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,170评论 1 286
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,276评论 6 385
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,364评论 1 292
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,401评论 3 412
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,179评论 0 269
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,604评论 1 306
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,902评论 2 328
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,070评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,751评论 4 337
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,380评论 3 319
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,077评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,312评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,924评论 2 365
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,957评论 2 351

推荐阅读更多精彩内容