目录

一. hashmap回顾

1.1 基本结构

1.2 hashMap分布策略

1.3 问题

1.4 为什么不使用锁解决线程安全问题

二. ConcurrentHashMap

2.1 java1.7 版本实现机制

分段锁机制

源码分析

一. hashmap回顾

1.1 基本结构

HashMap存储的是存在映射关系的键值对，存储在被称为哈希表的数据结构中。

通过计算key的hashCode来确定键值对在数组中的位置。

假如产生碰撞，则使用链表或者红黑树。

key最好使用不可变类型的对象，否则当对象产生变化时，重新计算他的hashCode值会与之前的不一样，导致查找错误。

 由第一点可知，在存储键值对时，我们希望的情况是尽量避免碰撞。这样查找效率会更高。

如何尽量避免碰撞，核心在于元素的分布策略和动态扩容

1.2 hashMap分布策略

• 数组的长度始终保持为2的次幂
• 将哈希值的高位参与运算
• 通过位与操作来等价取模操作

详见：JAVA面试考点—— JAVA集合容器梳理（hashmap）

1.3 问题

不是线程安全的，在扩容时可能会出现环形链表异常；

多线程进行put操作时，也容易出现脏数据读写问题。

1.4 为什么不使用锁解决线程安全问题

既然hashMap有线程安全问题，可以加锁，即给put、get加上synchronized。hashTable就是这么实现的。

    public synchronized V get(Object key) {...}
    public synchronized V put(K key, V value) {...}

 为什么加锁会导致线程效率低下？

因为全表加锁之后，只能单一线程操作，其他想要读写的线程都会被阻塞

 

 

二. ConcurrentHashMap

2.1 java1.7 版本实现机制

分段锁机制

 ConcurrentHashMap内部维护了一个segment数组；

该数组的每个元素是hashEntry数组

 

源码分析

1. 继承关系

ConcurrentHashMap 继承 AbstractMap（MAP的公共方法），实现了ConcurrentMap（增删改查，要求线程安全）接口。

public class ConcurrentHashMap extends AbstractMap
    implements ConcurrentMap, Serializable {...}

2. 静态变量

static final int DEFAULT_INITIAL_CAPACITY = 16; // hashEntry数码的初始值
static final float DEFAULT_LOAD_FACTOR = 0. 75f ; //加载因子，决定扩容时机
static final int DEFAULT_CONCURRENCY_LEVEL = 16;    //并发等级
static final int MAXIMUM_CAPACITY = 1 << 30;      //hashEntry数目的最大值
static final int MIN_SEGMENT_TABLE_CAPACITY = 2;   //segment数组的最小长度
static final int MAX_SEGMENTS = 1 << 16; // segment数组的最大长度
static final int RETRIES_BEFORE_LOCK = 2;  // 重试次数

3. 成员变量

final int segmentMask;
final int segmentShift;
final Segment[] segments;
transient Set keySet;
transient Set> entrySet ;
transient Collection values ;

4. 内部类

HashEntry

用来封装散列映射表中的键值对。在 HashEntry 类中，key，hash 和 next 域都被声明为 final 型，value 域被声明为 volatile 型

static final class HashEntry {
        final int hash;
        final K key;
        volatile V value;
        volatile HashEntry next;

        HashEntry(int hash, K key, V value, HashEntry next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        //只列出主要部分
}

Segment 类

继承 ReentrantLock JAVA面试考点——Reentrantlock

segment数组中，一个segment对象就是一把锁。一个segment对象对应一个hashEnry数组。

这个数组中的数据同步就依赖同一把锁，不同HashEntry数组的读写互不干扰，这就形成了所谓的分段锁。

    
    static class Segment extends ReentrantLock implements Serializable {
        private static final long serialVersionUID = 2249069246763182397L;

        //scanAndLockForPut中自旋循环获取锁的最大自旋次数
        static final int MAX_SCAN_RETRIES =
        Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;

        //存储着一个HashEntry类型的数组
        transient volatile HashEntry[] table;

        //存放元素的个数，这里没有加volatile修饰，所以只能在加锁或者确保可见性(如 
        //Unsafe.getObjectVolatile)的情况下进行访问，不然无法保证数据的正确性
        transient int count;

        //存放segment元素修改次数记录，由于未进行volatile修饰，所以访问规则和count类似
        transient int modCount;

        //当table大小超过阈值时,对table进行扩容,值为(int)(capacity *loadFactor)
        transient int threshold;

        //负载因子
        final float loadFactor;

    }

未完待续