常用Map的比较与实现(jdk1.8+)

常用Map的比较与实现

- 常用的Map比较
- HashMap 的实现
- - - put(K key, V value) 方法的主要执行过程
    - get(K key) 方法主要执行过程
    - rehasing 的一些问题.
- ConcurrentHashMap 的实现
- - - put(K key, V value) 方法的主要执行过程
    - get(K key) 主要执行过程
    - ConcurrentHashMap 改进的总结 (1.7 -> 1.8)
- HashTable
- TreeMap
- 常用Map的继承结构图

常用的Map比较

比较项	ConcurrentHashMap	HashTable	HashMap	TreeMap
线程安全	是	是	否	否
线程安全方式	锁分段技术1.7 / CAS+synchronized1.8	方法synchronized	不安全	不安全
Key可以为null	否	否	是	否
Value可以为null	否	否	是	是
继承自	AbstractMap	Dictionary	AbstractMap	AbstractMap

HashMap 的实现

// hashmap 的整体结构
    A[0]       A[1]       A[2]       A[3]       RBTR[4]       A[5] 
     ↓          ↓          ↓          ↓          ↓             ↓
    null      A[1-1]      null      A[3-1]     RBTR[4-1]      null    
                ↓                     ↓        ...(超过8)   
              A[1-2]                null     RBTR[4-n] RBTR[4-m]  

    数组的元素结构
    class Node{ //链表        0,1,2,3,5 的数据结构       
        K Key;
        V Value;
        int hash;
        Node next;
    }

   class TreeNode{ //红黑树     4的数据结构
        TreeNode parent;
        TreeNode left;
        TreeNode right;
        TreeNode prev;
        boolean red;
     }

HashMap的整体结构就是数组 + 链表(元素少于8使用链表, 元素大于8使用红黑树).

数组串起来了HashMap的主体, 链表则为了解决hash冲突的问题.

put(K key, V value) 方法的主要执行过程

首先计算key的hashcode. 调用了key自身的hashCode() 方法. 所以所有插入HashMap 的Key都必须重写其hashCode方法和equels方法.

拓展: 一个自定义类作为Key时, 必须同时重写equals方法和hashCode.

推荐使用String 来作为Key, 其优点是 String 是不可变的, 并且已经实现了 equals 和 hashCode 方法.

如果不重写这两个方法, 可能引发的就是高几率hash碰撞, 导致性能问题.
如果数组没有初始化, 那么调用默认初始化, 长度 16, 阈值为16 * 0.75(默认的阈值因子)
根据当前Key的 HashCode 与 (数组长度-1) 做并集的结果作为数组下标查找, 如果没有查找到值, 那么直接插入Node.
如果hash碰撞, 根据数组现有元素进行判断数据处理

4-1 : 如果插入值与数组现有元素 hash 值相同, key 也相同, equal 方法也相同, 那么说明是插入重复值.

4-2 : 如果数组现有元素是 TreeNode类型(红黑树节点), 那么直接插入节点到红黑树.

4-3 : 如果 Hash 碰撞的值小于插入转化为红黑树的阈值 (默认8个), 那么直接如插入链表尾部, 否则将链表转化为红黑树. 所有该hash值的key转为TreeNode.
如果当前的map的元素数量超过阈值(初始化阈值 16 * 0.75 = 12), 那么调整数组的大小, 也叫rehashing.

5-1 : 如果数组大小已经超过默认最大值 (1<<30), 不再变动

5-2 : 没有超过默认最大值, 将数组的容量 * 2.

5-3 : 将旧数组中的元素赋值到新的数组中.

get(K key) 方法主要执行过程

遍历整个数组

1: 如果数组中节点 equals(), key, hash 和传入值都相等, 那么直接返回.

2: 如果hash值相等, 节点类型是 TreeNode, 则转由红黑树查找, 否则遍历整个链表查找.

rehasing 的一些问题.

当两个线程同时调整HashMap的情况下, 调整链表的next节点时, 可能造成收尾递归, 从而无限循环. 所以在多线程情况下, 推荐使用 ConcurrentHashMap.

ConcurrentHashMap 的实现

ConcurrentHashMap的整体结构和HashMap类型, 只不过通过CAS和synchronized来控制并发操作, 整体看来它就是优化和线程安全的HashMap.

jdk1.7 中, ConcurrentHashMap是由一个 Segment 数组和多个 HashEntry数组组成, Segment 数组就是将一个大表转化为多个小表, 加锁时, 只对一个Segment元素(HashEntry数组) 进行加锁, 减小了锁的粒度, 提高了性能. 其他的数据结构和HashMap实现类似.

put(K key, V value) 方法的主要执行过程

首先获取hash值
如果数据没有初始化, 则调用数组初始化

2-1 : 如果已经开始初始化的标志位小于0, 那么当前线程就挂起

2-2 : 已经开始初始化的标识位等于0, 将开始初始化的标志位设置为-1, 并开始初始化

2-3 : 上面两部就是防止并发初始化.
没有检测hash冲突那么就直接调用UnSafe的CAS插入该元素

3-1 : 如果没有扩容, 直接插入

3-2 : 如果容器正在扩容, 那么会调用帮助helpTransfer方法帮助扩容.
如果检测到hash冲突 ,使用 synchronized 加锁完成类似 HashMap 碰撞插入的操作.
检测元素数量是否超过阈值, 进行扩容.

get(K key) 主要执行过程

遍历整个数组

1: 根据hash值, 找到数组中节点 hash, equals(), key 都相同的元素, 直接返回

2: 如果数组查找返回的hash值< 0, 那么数组正在扩容

2-1 : 获取到正在扩容的数组, 执行第一步

2-2 : 不是首结点, 就向下遍历查找

ConcurrentHashMap 改进的总结 (1.7 -> 1.8)

降低了锁的粒度, 由一个Segment(多个HashEntry) -> 一个HashEntry. 提升了性能
使用内置的synchronized来代替ReentrantLock, 因为ReentrantLock相对synchronized在大量操作时, 会有更多的内存开销, 由于锁粒度下降, ReentrantLock相对synchronized也没有了优势, 且随着synchronized的优化, synchronized的性能也有一定的提升.

HashTable

HashTable 虽然是线程安全的, 但是已经不推荐使用, 因为其public方法直接使用synchronized加锁, 相比ConcurrentHashMap, 在多线程操作时, 性能弱了不少.

其内部存储就是一个弱化的 HashMap , 通过数组 + 链表存储结构.

TreeMap

本质就是一个红黑树, 根据Key的比较器来比较大小进行排序.

常用Map的继承结构图

常用Map的比较与实现(jdk1.8+)

常用Map的比较与实现(jdk1.8+)