HashMap (1.7 & 1.8)

2019-08-29 本文已影响0人 Aaron_Swartz

前言：面试中多次遇到问这两个map的实现原理的，于是打算总结如下。

HashMap

map类图

1 HashMap不是线程安全的，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

package com.yiibai;
import java.util.*;
public class CollectionsDemo {
   public static void main(String[] args) {
      // create map
      Map<String,String> map = new HashMap<String,String>();
      // populate the map
      map.put("1","TP"); 
      map.put("2","IS");
      map.put("3","BEST");
      // create a synchronized map
      Map<String,String> synmap = Collections.synchronizedMap(map);
      System.out.println("Synchronized map is :"+synmap);
   }
}

2 LinkedHashMap(可以保证有序读取)：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。

3 TreeMap：TreeMap实现SortedMap接口，能够把它保存的记录根据键值排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

在以上三种map中要求map的key都是不可变对象，不可变对象就是该对象在创建后其hash值是不可变的，否则map根据key映射的时候就找不到对象了。

学习思路：搞清楚HashMap，首先需要知道HashMap是什么，即它的存储结构-字段；其次弄明白它能干什么，即它的功能实现-方法。下面我们针对这两个方面详细展开讲解。

HashMap的结构

1 本质是数组+链表+红黑树，链表长度大于8时，链表转为红黑树（jdk1.8利用红黑树快速增删改查的特点提高HashMap的性能）
2 如果这个元素所在的位子上已经存放有其他元素了，那么在同一个位子上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾，这里使用的是头插法。
3 数组下标计算方法为 hashcode & (length - 1) 当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小。初始的length 默认为16。

image.png

HashMap resize

1 首先，Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。HashMap的扩容是原来哈希数组长度的2倍。假如需要存储的数据个数为m，那么当初始化一个HashMap最小的大小应该满足：**0.75 * n > m 即n为2的幂指数，并且n大于m4/3的条件 **。
2 扩容时机
当hashmap中的元素个数超过数组大小loadFactor时，就会进行数组扩容。
3 扩容过程就是new 一个原来数组2倍大小的数组，然后依次遍历原来的数组散列表，重新计算hash位置，有冲突的时候使用头插法插入到链表头。其中使用的是transfer()数组。注意，transfer() 数据迁移方法在数组比较大的时候会非常耗费资源。
4 注意
当前线程迁移过程中，其他线程新增的元素有可能落在已经遍历过的哈希槽上，在遍历完成之后，table数组引用指向了newtable，这时新增元素就会丢失，这个也是hashMap在高并发场景下线程不安全的一个原因。

HashMap 在高并发场景中新增对象丢失原因如下

1 并发赋值被覆盖
就是两个线程同时put元素，并且落到一个slot里边，此时当一个线程获取桶的位置，并且要将桶上挂的链表挂到新插入元素的结点下的时候，另一个线程也获取桶的位置，执行同样的操作的时候，就会有第二个线程最后生成的链表赋值到该桶下的时候覆盖第一个线程生成的链表。
2 已遍历区间新增元素丢失(关注的是向旧表插入元素的丢失)
hashMap中当一个线程在resize过程中，另一个线程向旧表进行新增元素时，迁移完成后这部分元素就会丢失。
3 “新表“被覆盖(关注的是向新表插入元素的丢失)
如果是多个线程同时执行resize操作，每个线程都会new Entry[newCapaticy]，这个是线程内的局部数组对象，线程之间是不可见的，迁移完成后，resize的线程会赋值给table线程共享变量，从而覆盖其他线程的操作，因此在“新表”中进行的插入操作会丢失。

HashMap 在高并发场景下的死链问题

本质就是在多线程resize过程中，导致的hash桶上的挂的链表有环的问题，这个会导致可能出现hashMap.get(key) 操作出现死循环问题，因此问题比较严重

参考：
1 阿里P8架构师谈：深入探讨HashMap的底层结构、原理、扩容机制
2 高并发环境下，HashMap可能出现的致命问题。注意：是在jdk8以下版本