java数据结构-Map集合（1）_newhashmapwithexpectedsize

基本介绍和使用

Key-value 键值对形式的容器

在java.util包中

创建容器方式：

1.无参数

2.有参数//设置默认容量

基本使用方法：

HashMapo<Integer,String>map=new HashMap();

E v = put(key,value)//增

putAll(map);//加map中全部的数据

get(key)//取得元素返回值是value

E v = remove(key)//
boolean = remove(key,value)
replace(oldkey,newValue)//改
put(oldKey,newValue)
size()//获取有效元素个数

//map集合的遍历
//先获取全部的key
Set keys = map.keySet();//返回值就是Set可以⽀持泛型
//获取⼀个迭代器对象装满了key的值
Iteratorit=keys.itetrator();
while(it.hasNext()){
Ineteger Key =it.next():
String value=map.get(key);
}

特点
HashMap
key⽆序⽆重复
value⽆序可重复
如果重复 将原来的元素覆盖
适合查找某⼀个元素 唯⼀存在

内部数据结构

java中两大基本数据结构，数组加链表，数组（ArrayList底层）遍历非常快，插入和删除困难，链表（Linklist底层）：遍历满，插入和删除容易，HashMap是将两者结合

数组每个地方都存在一个key-value的实例，java7中叫Entry java8叫Node

本身所有的位置都为null，在put插入的时候会根据key的运用hash算法去计算一个index值（源码分析，hash如何确定）

进行hash算法计算的hashmap内部的hash（）函数

把key-value 的实例放到index 对应的数组位置中
但是
数组长度有限，hash值有可能是相同的，多个index 相同的 key-value实例，会在同一个node形成链表：

每一个节点都会保存自身的hash、key、value、和下一个节点：单个entry的结构图

随着数据量的增加，同一个节点上的链表可能挂载的元素变得很多，链表变长，查询的性能变慢，在java8后为了解决这一问题，采用了
数组+ 链表/红黑树的形式：当链表长还是<8时候仍然是链表形式，当>8时会变成红黑树，当红黑树内部元素个数小于6会转为链表
如图：

总结：java7之前是数组加链表，java8之后是数组+ 链表（<8）/红黑树

1.判断数组是否为空，为空则进行初始化；//怎么初始化呢

2.如果不为空，计算k的hash值，通过（n-1）&hash计算应当存放在数组中的下标index

3.查看table[index]是否存在数据，没有数据旧构造一个Node节点存放在table[index]中

4.存在数据，说明发生了hash冲突，继续判断key是否相等，相等，用新的value替换原数据（onlyIfAbsent为false）；

5.如果不相等，判断当前节点类型是不是树型节点，如果是树型节点，创建树型节点插入红黑树中

6.如果不是树型节点，创建普通Node加入链表中，判断链表长度是否大于8，大于的话链表转换为红黑树

7.插入完成后判断当前节点数是否大于阈值，如果大于开始扩容为原数组的两倍

HashMap 默认容量机制：

容量的定义：
HashMap 有两个“容量” 一个是size 是Map 所有元素的个数（我装“了”多少元素）（也表示数组的容量）
一个是capacity是Map的容量（我“能装多少元素”）
例子：

try {
            Map<String,String> map =new HashMap<>(16);
            map.put("key","value");
            System.out.println("size"+map.size());
            Class clazz=map.getClass();//因为capactiy 的得到方法为私有，这里通过反射去得到并执行私有的方法
            Method getCapcity =   clazz.getDeclaredMethod("capacity");
            getCapcity.setAccessible(true);
            System.out.println("capacity"+getCapcity.invoke(map));

        } catch (Exception e) {
            e.printStackTrace();
        }
1
2
3
4
5
6
7
8
9
10
11
12

HashMap的构造中如果没有指定容量，会得到一个默认容量为16（数组长度为16）,

初始化大小是16的原因：

static final int DEFAULT_INITIAL_CAPACITY=1 <<4
1

1.一般的初始容量最好是2的幂，这是为了方便位运算，位运算远比平常的算术运算高很多，
2.选2的4次方 16 是为了服务将key映射到index 的算法， index=HashCode （key） & （Length-1）
例子：
一个key的hash后的二进制为
10111011000010110100
Length-1=15 15的二级制为1111
index = 10111011000010110100 & 1111 得到的值为0100转十进制为4
所有的key都需要拿到对应的hash，但为了保证链表不要其中某个长的太突出，需要尽可能得到一个均匀分布的hash值
Length为2的幂时，Length-1 的值是所有二进制位全为1，这时index的结果等同于HashCode后几位的值
？只要输入的HashCode本身分布均匀，Hash算法的结果就是 分布均匀的

具体容量16呗作为一个经验值采用了：让这个初始值不能太小（频繁扩容影响效率）不能太大（浪费空间）

指定容量初始化

hashmap根据用户传入的初始化容量，理工无符号右位移和按位或运算等方式计算出第一个大于该数的2的幂

负载因子是0.75 如果自己传入初始大小k，会对k进行数据处理，处理成为大于k的2的整数次方

如果用户传17，那么hashmap初始化大小为32；

实例如下：

 try{
            HashMap map=new HashMap(17);
            Class clazz=map.getClass();//因为capacity的得到方法为私有，
            Method getCapcity=clazz.getDeclaredMethod("capacity");
            getCapcity.setAccessible(true);
            System.out.println("size:"+map.size());
            System.out.println("capacity:"+getCapcity.invoke(map));
        }catch (Exception e ){
			           e.printStackTrace();
        }
1
2
3
4
5
6
7
8
9
10

//当传入值非2的n次方是，容量计算的实现代码
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;
//初始二进制数依次右位移1，2，4，6，8，16位，然后与自己异或（“|”）
    //最终把高位第一个为1的数后面全变为1
    //111111 +1 =100000=2^6??
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    //三位运算符做一个极限值的判断把之前计算得到的数值+1
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

hashmap在没有给定默认值时，第一次put时候，会进行一次初始化这很耗费性能,一般开发中我们尽可能的为map给予初始值（这里阿里开发手册也提到）

如何确定比较适合的默认值呢

要知道map不是满了才扩容，他的扩容临界点默认是0.75*capacity

这时候可能有个问题是：如果我设置的默认值，到默认值前就到了扩容临界点了怎么办

要知道扩容的性能代价不是一般的大

比如设置 new HashMap（7） 7是我想要的默认值，认为这个容器装7个就够了

但是容器帮你将capaity扩容到8 ，但是这时候的容器扩容临界点为8*0.75=6;

在元素数量还没到你预定的默认值就会开始进行‘“漫长”的扩容

遇到这种预想默认值大于临界值的情况应该怎么办：

可以通过一个简单的算法

expectsize/0.75F + 1.0F

7/0.75+1=10 的默认值 会被设置成16 这就大大减少了扩容的几率

将预想值进行一个小小的处理就能一定程度上解决扩容的几率//只是会牺牲些内存

//注：这个F是因为小数默认是double类型 加个F后缀提醒程序这事个Float类型的再次给初学者提醒下

算法在map源码中有实现开发时候，通过Map创建一个HashMap实现这个容量改变：

Map<String,String>map=Maps.newHashMapWithExpectedSize(7);
1

源码码如下

public static <K,V> HashMap<K,V> newHashMapWithExpectedSize(int expectedSize){
    return new HashMap(capacity(expectedSize));
}
static int capacity(int expectedSize){
    if(expectedSize < 3){
        CollectPreconditions.checkNonnegative(expectedSize,"expectedSize");
        return expectedSize +1;
    }else{
        return expectedSize < 1073741824 ? (int)((float)expectedSize / 0.75F + 1.0F) : 2147483647;
    }
}
1
2
3
4
5
6
7
8
9
10
11

当向map中put一个元素会通过hash方法确定吧这个元素放到数组的什么地方

Map类集合中hash函数设计：（定位）

哈希：
定义：是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数，翻译做“散列”，把任意长度的输入，通过散列算法，变换成固定长度的输出，输出的就是散列值，这种转换时一种压缩映射，散列值的空间通常远小于输入的空间，
Tips：不同的输入可能会散列出相同的输出,：散列值不同 输入值肯定不同，散列值相同，输入值不一定相同
理解图如下

不同的输入值根据同一个散列函数计算的值相同的现象叫做碰撞
常见的Hash函数：

直接定址法：直接以关键字k或者k加上某个常数（k+c）作为hash地址
数字分析法：提取关键字中取值比较均匀的数字作为哈希地址
除留余数法：用关键字k除以某个不大于哈希表长度m和数p，将所得余数作为哈希表地址
分段叠加法：按照哈希表地址位数将关键字分层位数相等的几部分，其中最后一部分可以比较短，然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址
平方取中法：如果关键字各个部分分布都不均匀的话，可以先求出它的平方值，然后按照需求取中间的几位作为哈希地址。
伪随机数法：采用一个伪随机数当作哈希函数。

衡量一个hash函数好坏的重要指标就是发生碰撞的概率和解决方案，但任何hash函数基本无法彻底避免碰撞

常见的解决碰撞的方法有以下几种

1. 开放地址法：一旦发生冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
2. 链地址法：将哈希表的每个单元作为链表的头结点，所有哈希地址为i的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。
3. 再哈希法：当哈希地址发生冲突用其他的函数计算另一个哈希函数地址，直到冲突不再产生为止
4. 建立公共溢出区：将哈希表分为基本表和溢出表两部分，发生冲突的元素都放入溢出表中

hash方法源码解析

hash方法：

hashmap中定义了一个hash（Object k）方法 被内部负责增删的方法调用，内部充当定位的一个角色

hash基本原理：调用Object 的hashCode（）方法计算key的hash值返回一个整数， （int hash(Object k)）

然后根据容器的容量进行取模球的最后index值( indexFor(int h ,int length))

jdk1.7中的hash方法

final int hash(Object k){
    int h=hashSeed;
    if(0!= h && k instanceof String){//String 有它自己变成hash的一套方式
        retrun sun.misc.Hashing.stringHash32((String)k)
    }
    
    h ^= k.hashCode();
    //解决hash冲突
    h ^=(h>>>20)^(h>>>12);
    return h^(>>>7)^(h>>>4);
}

static int  indexFor(int h,int length){
    return h&(length-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

indexFor 取模 解析：

方法的目的是为了取模：数学计算中叫做取余数 h%length

方法考虑到效率问题将数学运算变成了位运算：

//位运算直接对内存数据进行操作，不用变成十进制，比一般转成二进制再转回来的数学运算快很多

​ h&（length-1）=h%length

位运算 实现取模运算一样的结果的原理：
//前文说到length无论怎么初始化它都是2^n

h & (2^n -1)=h2^n

设n为3 2^3为8 二进制为1000. 2^3-1=7的二进制位0111

h & 1000 相当于取二进制后三位数 结果为 0111

2^n-1 形成一个 低位掩码，“与”操作的结果就是散列值h的值高位全部归0 ，只保留低位值

如下

 01001010(h)
&00000111(lenght-1)
==================
 00000010
 
1
2
3
4
5

所以如果有人问为什么hashmap的容量必须是2的次方，主要的原因就是为了方便内部的位运算尤其是取模时候的位运算

位运算作用：1.性能

2.解决了index为负数的问题 ：2^n-1 首先值是正数，二进制第一位是0，与hash码取模位运算时第一位是0

//位运算问题？

但是这样只取后面几位进行取模，依然很有可能产生重复

hash冲突问题解决（扰动函数机制）

冲突问题是什么：多个不同的键，按位与运算后得到的结果相同

java7处理hash冲突：通过让自己的高位取和低位取做异或，混合原始哈希码的高位和低位，加大低位的随机性

h^=k.hashCode();
h^=(h>>>20^(h>>>12));
return h^(h>>>7) ^ (h>>>4);//扰动计算
1
2
3

这段代码是为了对key的hashcode 进行扰动计算，防止不同hashCode=的高位不同但低位相同导致hash冲突，简单点讲，就是为了把高位的特征和低位的特征组合起来，降低哈希冲突的概率，也就是说，尽量做到任何以为的变化都能对最终得到的结果产生影响

新java8的hash函数

在java8之前使用单项链表来存储相同index的元素，这样有可能会让Hashmap的get方法从0（1）降低到0（n）

java8 使用平衡树来替代链表 存储冲突的元素让性能从0（n）提高到0（logn）

//0（n） 0（1）

// 如果恶意程序知道我们用的是Hash算法，则在纯链表情况下，它能够发送大量请求导致哈希碰撞，然后不停访问这些key导致HashMap忙于进行线性查找，最终陷入瘫痪，即形成了拒绝服务攻击（DoS）。

java 8hash函数做了优化，只做了一次右位移异或混合，而不是四次

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

HashMap扩容和插入机制：

内部数组容量是有限的 ，多次插入后，到达一定的数量就会进行扩容，也就是resize
redsize 扩容的时机
两个因素：
Capacity：HashMap 当前长度
LoadFactor （DEAFAULT_LOAD_FACTOR） 负载因子默认为0.75，负载因子确认的是扩容的时机，当容量到某点时候就扩容
扩容点=当前容量*负载因子

默认情况当size 大于capacity*0.75 就会触发机制

扩容程序：
1.扩容：创建一个新的Entry 数组容量是原来的两本
2.ReHash： 遍历原Entry 数组，把所有的Entry重新Hash，算一遍hash值，根据hash进行index放置
赋值要Hash而不是直接复制的原因
长度扩大以后，Hash的规则也随之改变：
Hash公式–>index =HashCode (key) & (Length-1)
所以扩容后可能的结构样子是这样的：

新节点的插入方式：
java8之前是头插法，就是说新来的值会取代原有的值，原有的值就顺推到链表中去//这时候的原因是新的元素被查找的可能性更大
java8之后是尾插法：为什么换成尾插法

java8前的头插法：
如果想容量为2的put 两个值，负载因子是0.75 ，因为2*0.75=1，当即将插入第二个就会扩容
当想要在容量为2的容器李用不同的线程插入A、B、C，三个线程可能是在resize之前就执行了插入

链表的指向为A->B->C

这时候在进行扩容
在java8前 resize 的赋值方式，
1.使用了单链表的头插入方式，同一位置新元素总会被放在链表的头部位置
2.在旧数组同一条Entry链上的元素，会同重新计算索引位置
但是在头插法的过程中可能会出现原本后面的值突然到了头部，原本的头部跑到了后面，而它的指向并没有变
如图

这时候就会出现环形链表
取值就会出现Infinit Loop

java8的尾插法：
使用了尾插法后，即使是扩容后也能保证链表元素原本的顺序，就能解决链表成环的问题

HaspMap数据插入流程：

Hashmap在1.7的resize中的transfer函数//这个transfer在做什么？--------------

void transfer(Entry [] newTable,boolean rehash){
    int newCapacity=newTable.length;
    for(Entry<K,V> e:table){//遍历每一个key-value Entry节点
        while(null!=e){
            Entry<K,V> next =e.next;//因为是单链表，如果要转移头指针，一定要转移头指针，一定要保存下一个节点，不然转移后链表就丢了
            if(rehash){
                e.hash=null==e.key?0:hash(e.key);//
                //
            }
            //
            int i=indexFor(e.hash,newCapacity);//计算新表的位置
            //根据hash值和容量取模
            //注意这段代码，如果多线程环境线程在这里挂起
            //能看出这是头插法：相邻两个元素之间通过建立中间变量进行赋值实现两者调转来实现元素像下移动，过程如下图
            e.next=newTable[i];//e要插入到链表的头部，先用e.next指向新的hash表的第一个元素
            newTable[i]=e;//新的表的头指针依然指向e没转移前端第一个元素，所以要将新hash表的头指针指向e
            e=next;//转移e节点开始下一步循环
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

总结：
java7 多线程操作Hashmap 因为头插法导致 了链表前后倒置 形成环链表形成死循环
java8 同样多线程环境，因为尾插法导致顺序扩容前后一致，不会形成环链表的死循环
但是线程安全并不局限于此：读某个值时候，因为hashmap没有加线程所，并不能保证，开始读值时到读值后，两个时间点，值没有被更改过，就算改了插入方法依然保证不了线程安全

HashMap 的去重机制：
HashMap 的key 是不允许的重复的，
去重原理就是在add之前看看这个key对象是否与内部有重复，而HashMap内部通过重写了Object这个所谓的祖先类（所有对象默认继承Object）的equals方法和hashCode，用来比较对象是否相同
在Object 的原来equals方法中equals仅仅通过== ，对于值对象判断值，对于引用比较地址

 public boolean equals(Object obj) {
        return (this == obj);
    }
1
2
3

HashMap 重写的equals相对来讲比较复杂，毕竟也有可能出现地址不一样但内容一样的这种情况
Tip：这个方法是重写了AbstractMap的方法（它继承了AbstractMap）

  public final boolean equals(Object o) {
            if (o == this)//如果地址直接一样，直接返回true结束方法
                return true;
            if (o instanceof Map.Entry) {//如果它属于节点对象
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&//比较entry对象的key 和value 与o 的key和value
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }   
1
2
3
4
5
6
7
8
9
10
11

但是，hashmap index 的确定是根据hashCode，同一条链表的对象如果hash值相同，就很难具体的得到链表上某个具体的对象
这时候需要重写hashCode方法避免给每个对象赋予只属于它的hash码作为标识

扩容机制：

/**
* 初始化或加倍扩容的表大小如果为空
*/
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;
            }
            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
            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;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != 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;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            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) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

Hashmap在java7与java8的区别

HashMap 中java7 和java8的线程安全问题

hashmap java7中在多线程中产生的问题：

我们开多个线程进行put操作

public class Text{
       public static void main(String []args){
       	 	HashMapThread thread0 = new HashMapThread();
       	    HashMapThread thread1 = new HashMapThread();
       	 	HashMapThread thread2 = new HashMapThread();
        	HashMapThread thread3 = new HashMapThread();
        	HashMapThread thread4 = new HashMapThread();
        	thread0.start();
			thread1.start();
        	thread2.start();
       		thread3.start();
         	thread4.start();
       }
       class MapThread extends Thread{
       		private static AtomicInteger atomicInteger=new AtomicInteger();
       		//一个线程安全的Interger包装类
       		private static Map<Integer,Integer> map =new HashMap();
       }   
       public void run(){
           while(atomicInteger.get()<1000000){
               map.put(atomicInteger.get(),ai.get());
               atomicInteger.incrementAndGet();//原子性自增
              
           }
       }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

以上代码运行可能出现两个问题：

1.死循环

2.数组越界出现：ArrayIndexOutOfBoundsException

问题出现原因：

多线程环境put导致get死循环

原因是多线程进行put操作时候触发了HashMap 扩容（resize函数），出现链表两个节点形成闭环导致死循环，put操作流程：

死循环发生在HashMap的扩容函数中，根源在transfer函数中：

多线程中，线程在transfer函数中的：e.next=newTable[i]中被挂起

void transfer(Entry [] newTable,boolean rehash){
    int newCapacity=newTable.length;
    for(Entry<K,V> e:table){//遍历每一个key-value Entry节点
        while(null!=e){
            Entry<K,V> next =e.next;//因为是单链表，如果要转移头指针，一定要转移头指针，一定要保存下一个节点，不然转移后链表就丢了
            if(rehash){
                e.hash=null==e.key?0:hash(e.key);//
                //
            }
            //
            int i=indexFor(e.hash,newCapacity);//计算新表的位置
            //根据hash值和容量取模
            //注意这段代码，如果多线程环境线程在这里挂起
            //能看出这是头插法：相邻两个元素之间通过建立中间变量进行赋值实现两者调转来实现元素像下移动，过程如下图
            e.next=newTable[i];//e要插入到链表的头部，先用e.next指向新的hash表的第一个元素
            newTable[i]=e;//新的表的头指针依然指向e没转移前端第一个元素，所以要将新hash表的头指针指向e
            e=next;//转移e节点开始下一步循环
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

上面这段代码流程分析

假设size=2，key为 3，7，5

最终

单线程环境下resize在rehash后

key 为5 被hash到1的index位置，重新hash后，7这个原来的末尾值作为新值插入到3的头部

多线程环境时候 如果有两个线程A和B 都在进行put操作//

如果线程A在transfer 的 newTable[i]= e 这行代码中挂起//

扩容时候造成的数据丢失分析：

此时应该再放一遍transfer源码：

void transfer(Entry [] newTable,boolean rehash){
    int newCapacity=newTable.length;
    for(Entry<K,V> e:table){//遍历每一个key-value Entry节点
        while(null!=e){
            Entry<K,V> next =e.next;/
            if(rehash){
                e.hash=null==e.key?0:hash(e.key);//
                //
            }
            //
            int i=indexFor(e.hash,newCapacity);//计算新表的位置
          
            e.next=newTable[i];//e要插入到链表的头部，先用e.next指向新的hash表的第一个元素
            newTable[i]=e;//线程A在这里挂起
            e=next;//转移e节点开始下一步循环
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

线程A挂起时：

线程B完成后

开启A线程

在A线程中e=7 next =5 newTable[3]=null

继续开始执行后

此时e 为5

next =e.next //next =null

e.next=newTable[1]//e.next=5

newTable[1]=e // newTable[1]=5

此时因为newTable[3]=null //会有元素丢失

java8中的hashmap的优化：

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 {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))//如果没有hash碰撞则直接插入元素
                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) {
                        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;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

这是1.8中 HashMap中put操作的主函数，第6行中国若没有hash碰撞会直接插入元素，如果线程A和线程B同时put操作，刚好不同的数据hash值都一样，并该位置数据为null，两个线程都会进入第六行代码，如果A进入后在还未进行数据插入时候挂起，B正常执行，和插入数据，A唤醒后，不用再进行hash判断，会将B插入的数据覆盖

总结：

jdk1.7的线程问题是：形成环形链或者数据丢失

jdk.1.8的线程问题是：发生数据覆盖

参考资料

https://mp.weixin.qq.com/s/ktre8-C-cP_2HZxVW5fomQ

https://mp.weixin.qq.com/s?__biz=MzI3NzE0NjcwMg==&mid=2650126376&idx=1&sn=6ff01e62f001084c35b72e3615471100&chksm=f36ba509c41c2c1f502446a260890e6741d3a5257749e4b9757eacd4d6727042b02724f4c7e0&mpshare=1&scene=1&srcid=0617liVpx2YPGcNCYCAWqSI4&sharer_sharetime=1592403240996&sharer_shareid=48f6d0356198efc068ac3be54595c640&key=74cd249bb6cd420f039f4125d52dc4fbea61100f4280157b23544499f28ccce1cdc500271976554e140562bd506131590207227bd1fdcda4c648a3ec8c506c2b67fd90f2b47692967d4c413eeba9b683&ascene=1&uin=NzU1NjUzMDM2&devicetype=Windows+10+x64&version=62090070&lang=zh_CN&exportkey=A9OWou4STTudvBFdIQ0EIQE%3D&pass_ticket=oJhfBWnYt1x1XWTXlfV2aqTgTV8MldZMMbfbBWktBUmaVkhRwJM151xGFJ7kvrns