java Map集合又很多种，很多人java开发几年，却不知道这几种常见的Map有什么区别 。大部分人开发存放key-value键值对数据类型集合容器， 第一想到HashMap集合， 其他Map到没有怎么使用过，甚者可能连HashMap的实现原理也都不清楚。
发现问题查找博客，发现大部分的博客知识点错误百出 简直误人子弟，当然 我早些年写的博客 甚至现在可能写的博客知识也有这种情况，如果有读者指出错误，我很乐意和读者探讨。
本篇文章Map基于openj9.1.8

HashMap

数据结构

JDK1.8之前HashMap由数组+链表组成 ，JDK1.8以在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转 化为红黑树，以减少搜索时间

链表长度不超过8

链表长度超出8 且HashMap数组长度超出64（默认是64）

HashMap数据存放过程

HashMap put的流程 map.put(key,value);

1. 先根据key 找到key的Node hash 值 int hashCode = hash(key); (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
2. 根据hash和hashMap数组长度计算对应的数组下标 (n - 1) & hash n为数组长度
   所以 当hashMap数组扩容后 key的数组下标值会变动
3. 该数组索引对应的桶有没有数据，没数据 new Node 放入数组下标内。 到这里跳到第6步。
4. 数组索引对应的桶有数据，判断数据存放类型 如果是自平衡的排序二叉树 new TreeNode insert数据到红黑树。到这里跳到第6步。
5. 数据索引对应的桶 数据类型为Node ，遍历链表节点 如果与key hash值相等 覆盖该节点 ，否则 在链表最后面添加 新节点 Node ，链表长度+1 判断修改后的链表长度 如果超出8 链表改为红黑树。到这里跳到第6步。
6. 判断hashMap 散列表的装填因子 ，如果装填因子超出0.75 （默认值0.75），给数组扩容 把HashMap集合数据重新组装存放到新的数组内。

HashMap 线程安全问题

与大多数集合类一样，此类不同步。可以使用 Collections.synchronizedMap 方法构造同步的HashMap。Map m = Collections.synchronizedMap(new HashMap(...)); ，为什么说HashMap是线程不安全的呢？

线程不安全的情况，多个线程给map put数据

1. 两个线程（线程A 和线程B）key 计算的数组索引下标相同 都是2
2. . 线程A 优先获取时间调度 判断出 数组索引2 的位置没有数据 new 出一个Node 名叫nodeA ，
3. 紧接着线程B 获取了资源， 线程A挂起 。 判断数组索引2位置没有数据也 new 一个Node 叫nodeB， 线程B准备存放数据时 ，线程A 获取资源 把nodeA 放入 索引2 内， 结束put工作 ，接着线程B获取资源 把nodeB放入数组内 。这样线程A存放的数据被覆盖get线程A的key 返回为null。

图文表示：

线程A 找到下标2的位置，看没有值 创建一个nodeA

线程A被挂起，线程B 查询 下标2 没有数据，创建节点 NodeB

线程A获取资源，直接把nodeA放入桶内

线程B ，一直认为索引2的桶没有数据 ，忽略已有的链表数据 直接把nodeB节点覆盖放入桶内

多线程不安全案例

案例测试代码

public class HashMapTest {

    static HashMap map = new HashMap();
    public static void main(String[] args) {

        new Thread(() -> {
            System.out.println("线程1 执行");
            for (int i = 0; i < 8000; i++) {
                map.put(i,i);
            }
            System.out.println("线程1---------"+map.get(500));
        }).start();

        new Thread(() -> {
            System.out.println("线程2 执行");
            for (int i = 8000; i < 16000; i++) {
                map.put(i,i);
            }
            System.out.println("线程2---------"+map.get(1500));
        }).start();

    }


}

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 执行
线程2---------null
线程1---------null



线程1 执行
线程2 执行
线程1---------500
线程2---------1500



线程1 执行
线程2 执行
线程1---------null
线程2---------1500


线程1 执行
线程2 执行
线程2---------1500
线程1---------null

线程1 执行
线程2 执行
线程1---------500
线程2---------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

Collections.synchronizedMap(new HashMap(…));保证Map安全

public class HashMapTest {

    public static void main(String[] args) {

        Map map = Collections.synchronizedMap(new HashMap());
        new Thread(() -> {
            System.out.println("线程1 执行");
            for (int i = 0; i < 80000; i++) {
                map.put(i,i);
            }
            System.out.println("线程1---------"+ map.get(500));
        }).start();

        new Thread(() -> {
            System.out.println("线程2 执行");
            for (int i = 80000; i < 160000; i++) {
                map.put(i,i);
            }
            System.out.println("线程2---------"+ map.get(80020));
        }).start();

    }


}

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

HashTable

和hashMap一样，Hashtable 也是一个散列表，它存储的内容是键值对(key-value)映射。

数据结构

数据存放过程

和hashMap 差不多相同 但是没有红黑树 ，具体的看代码。

线程安全问题

HashTable 内的方法是同步的 synchronized ，当多个线程同时put 或remove 时
多线程案例,把创建的HashTable对象 加锁，缺点：没加锁之前多个线程 put key的数组下标索引不一样时，同时往数组添加数据没有影响 ，整个对象加锁后 要等上个线程释放锁后才能操作put

hashTable锁加的只加

public class HashTableTest {

    static  Hashtable<Integer,Integer> map = new Hashtable();

    public static void main(String[] args) {



        new Thread(() -> {
            System.out.println("线程1 执行");
            for (int i = 0; i < 8000; i++) {
                map.put(i,i);
            }
            System.out.println("线程1---------"+map.get(500));
        }).start();

        new Thread(() -> {
            System.out.println("线程2 执行");
            for (int i = 8000; i < 16000; i++) {
                map.put(i,i);
            }
            System.out.println("线程2---------"+map.get(1500));
        }).start();


    }


}

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

执行结果
线程相对安全的

线程1 执行
线程2 执行
线程2---------1500
线程1---------500

1
2
3
4
5

ConcurrentHashMap

jdk1.6版本：

1.默认情况下会有16个区段 Segment数组 Segment[16]

2.每次每个区段Segment中会保存若干个散列桶，每次散列桶长度扩容成2^n次方的长度。 多个散列桶相连就构成了散列表。

3.存入元素： key带入到hashcode方法众获得hashcode值，然后把hashcode值带入到散列算法中获取segment的下标(区段编号)，再根据key带入到定义好的函数中获取Segment对象中散列桶的下标。

如果此位置有元素就构成链表(JDK1.8及以后会形成红黑树)，如果没有元素就存入

3.存取的线程安全问题： 如果多个线程操作同一个Segment，则某个线程给此Segment加锁，另一个线程只能阻塞。

同时解决了HashTable的问题，HashTable只能由一个线程操作。 ConcurrentHashMap可以让一个线程操作第一个Segment，另一个线程操作另一个Segment。

4.小矩形块表示散列桶

绿色的Segment表示ConcurrentHashMap集合众 Segment[16]数组里的一个对象。

5.并发问题：

两个线程给不同的区段Segment中添加元素，这种情况可以并发。 所以ConcurrentHashMap可以保证线程安全(多个线程操作同一个Segment，则某个线程给此Segment加锁，另一个线程只能阻塞)并且在一定程度上提交线程并发执行效率。

两个线程给同一个区段Segment中添加元素，这种情况不可以并发， 这样JDK1.8进行了改进:

没有区段了，和HashMap一致了，数组+链表+红黑树 +乐观锁 + synchronized

8及以后

省略 下次补上

WeakHashMap

与大多数集合类一样，此类不同步。可以使用 Collections.synchronizedMap 方法构造同步的 WeakHashMap。

WeakHashMap.Entry 和 HashMap.Node 的不同点在于，WeakHashMap.Entry 继承了WeakReference。
弱引用的生存期特别短。https://blog.csdn.net/ChineseSoftware/article/details/119212399的时候，一旦发现弱引用对象，无论当前内存空间是否充足，都会将弱引用回收。
想象一下如下场景：

1. 调用两次 size()：第一次为 10，第二次就为 8 了。
2. 两次调用 isEmpty()：第一次返回 false，第二次返回 true。
3. 两次调用 containsKey()：第一次返回 true，第二次返回 false。
4. 两次调用 get()：第一次返回一个 value，第二次返回 null。
   在如今的并发泛滥的大环境下，大家应该都用过缓存，缓存都是放在内存中的，而内存几乎是计算机中最宝贵也是最稀缺的资源，所以需要谨慎的使用，不然很容易就出现 https://blog.csdn.net/ChineseSoftware/article/details/119212481。缓存的主要作用是为了更快的处理业务、降低服务器的压力，那么就要保证缓存命中率，这里假设整个缓存是一个 key-value 结构的(以键值对缓存为例)，HashMap 作为强引用对象在没有主动将 key 删除时是不会被 JVM 回收的，这样 HashMap 中的对象就会越积越多直到 OOM 错误；那么如何做到既让缓存的命中率高又不占用那么多的内存，这里就可以采用 WeakHashMap，当然不会有 HashMap 100% 的命中率(假设内存足够)，但是在保证程序正常的前提下更好的实现了缓存这套解决方案。

WeakHashMap使用了软引用结构，它的对象在垃圾回收时会被删除
注：垃圾回收是优先级非常低的线程，不能被显示调用，当内存不足的时候会启用
下面是 WeakHashMap 的实现原理拆分：

public class WeakHashMap<K,V> extends AbstractMap<K,V> implements Map<K,V> {
    ... ...
    // 用于存储需要清理的引用对象
    private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
    ... ...
    // 内部Entry继承自WeakReference，从而有弱引用特性
    private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
        ... ...
    }
    ... ...
    // 用于移除内部不用的Entry来释放内存
    private void expungeStaleEntries() { ... ... }
    ... ...
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

WeakHashMap 原理说明
1.每次GC清理对象后，引用对象被放置到 ReferenceQueue 之中
2.每次访问 WeakHashMap 都会调用 expungeStaleEntries 遍历删除 ReferenceQueue 中引用对象

1、缓存中使用
由于 WeakHashMap 是弱引用，因此适合在缓存中使用，当内存不足GC的时候，会清理不用的引用达到释放内存的目的

2、不要使用基础类型作为WeakHashMap的key

我大概理解的是，基础类型的一定范围不会被回收
原文：objectMap.put方法执行的时候i会被封装为Integer类型的，Integer保留了-128到127的缓存。但是对于int来说范围大很多，因此那些Key <= 127的Entry将不会进行自动回收，但是那些大于127的将会被回收，因此最后的尺寸总是会稳定在128左右

key 设置从0 开始 ，一直循环发现 0至128 的key value 没有被清理

    public static void main(String[] args) {
        WeakHashMap map = new WeakHashMap();
        map.put(0,0);
        for (int i = 0; map.size() == 0; i++) {
            try {
                Thread.sleep(10);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            if(i< 2000){
                map.put(i,i);
            }
            System.out.println("i 值为：  "+i);
            System.out.println("map size 为：  "+map.size());
            if(map.size() == 0){
                System.out.println("map size 为  " + 0);
                break;
            }
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int 类型改为大于 128 gc自动清除

public class WeakHashMapTest {
    public static void main(String[] args) {
        WeakHashMap map = new WeakHashMap();
        map.put(3000,3000);
        for (int i = 129; map.size() != 0; i++) {
            try {
                Thread.sleep(10);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            if(i< 2000){
                map.put(i,i);
            }
            System.out.println("i 值为：  "+i);
            System.out.println("map size 为：  "+map.size());
            if(map.size() == 0){
                System.out.println("map size 为  " + 0);
                break;
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

在检测到适当的可达性更改后，垃圾收集器会将注册的引用对象附加到该队列中。

byte[] key = new byte[1024*10];
WeakReference reference = new WeakReference<>(key,queue);

//当垃圾回收之后实际上会将reference对象放进引用队列中。
//而key就是也就是byte数组对象回收掉。通常引用队列就是作为一个通知的信号，表明这个对象被回收掉了。

验证代码 这里设置堆的大小为-Xmx20m （20m）

@Test
public void test() throws InterruptedException {
ReferenceQueue queue = new ReferenceQueue<>();

new Thread(()->{
    HashMap map = new HashMap<>();
    for(int i=0;i<100;i++){
        WeakReference reference = new WeakReference<>(new byte[1024*100],queue);
        map.put(reference,"a");
    }
    System.out.println(map.size());
}).start();

new Thread(()->{
    int cnt = 0;
    WeakReference k;
    try {
    	//ReferenceQueue.remove是阻塞的。poll()方法是不阻塞的。
        while((k = (WeakReference) queue.remove()) != null) {
            System.out.println("byte对象地址" + k.get());
            System.out.println("WeakReference的地址" + k);
        }
    }catch (Exception e){

    }
}).start();
Thread.sleep(2000);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

}

WeakReference的地址java.lang.ref.WeakReference@6930026c
byte对象地址null
WeakReference的地址java.lang.ref.WeakReference@561e343
byte对象地址null

map.size()=100

实际上只有map数组中key对象中的byte数组被回收掉了。

IdentityHashMap

IdentityHashMap数据结构

IdentityHashMap数据存放过程