Java-HashMap、ConcurrentHashMap解析

Hash表

Hash表也叫散列表，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。存放记录的数组叫做哈希表。
在HashMap中，就是将所给的“键”通过哈希函数得到“索引”，然后把内容存在数组中，这样就形成了“键”和内容的映射关系。

在了解哈希表之前，先大概了解下其他数据结构在新增，查找等基础操作执行性能：

• 数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)。对应到集合实现，代表就是ArrayList。

• 线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)。对应的集合类是LinkedList。

• 二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。对应的集合类有TreeSet和TreeMap。

• 哈希表：相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)。对应的集合类就是HashMap。

哈希表的主干是数组。要新增或查找某个元素，通过把当前元素的关键字 通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。即：

存储位置 = f(关键字)

其中，这个函数f一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。这会涉及到哈希冲突。举个例子，比如要在哈希表中执行插入操作：

查找操作同理，先通过哈希函数计算出实际存储地址，然后从数组中对应地址取出即可。

当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。哈希函数的设计至关重要，好的哈希函数会尽可能地保证计算简单和散列地址分布均匀。但是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址）、再散列函数法、链地址法。而HashMap即是采用了链地址法，也就是数组+链表的方式。

简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度依然为O(1)，因为最新的Entry会插入链表头部，即需要简单改变引用链即可，而对于查找操作来讲，此时就需要遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

---

HashMap-Jdk1.7

类定义

public class HashMap<K,V>
         extends AbstractMap<K,V> 
         implements Map<K,V>, Cloneable, Serializable

简介

1. 继承AbstractMap抽象类；
2. 实现Map接口，拥有一组Map通用操作；
3. 实现Cloneable接口，可进行拷贝（浅拷贝）；
4. 实现了Serializable接口，可实现序列化；
5. 允许键/值为空对象（null）；
6. 非线程安全，可通过Collections类的静态方法synchronizedMap获得线程安全的HashMap；
7. 不保证有序性（如插入顺序），也不保证顺序不随时间变化；

数据结构

HashMap 采用的数据结构 = 数组（主） + 单链表（副），该结构又称拉链法，具体描述如下:

当实例化一个HashMap时，系统会创建一个长度为Capacity的Entry数组，这个长度被称为容量(Capacity)，在这个数组中可以存放元素的位置称之为“桶”(bucket)，每个bucket都有自己的索引，系统可以根据索引快速的查找bucket中的元素。 每个bucket中存储一个元素，即一个Entry对象，但每一个Entry对象可以带一个引用变量，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Entry链。 Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。 Entry是HashMap中的一个静态内部类。代码如下：

/** 
 * Entry类实现了Map.Entry接口
 * 即 实现了getKey()、getValue()、equals(Object o)和hashCode()等方法
**/  
static class Entry<K,V> implements Map.Entry<K,V> {
  final K key;  // 键
  V value;  // 值
  Entry<K,V> next; // 指向下一个结点 ，也是一个Entry对象，从而形成解决hash冲突的单链表
  int hash;  // 对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算
  
  /** 
   * 构造方法，创建一个Entry 
   * 参数：哈希值h，键值k，值v、下一个结点n 
   */  
  Entry(int h, K k, V v, Entry<K,V> n) {  
    value = v;  
    next = n;  
    key = k;  
    hash = h;  
  }  
  
  // 返回 与 此项 对应的键
  public final K getKey() {  
    return key;  
  }  

  // 返回 与 此项 对应的值
  public final V getValue() {  
    return value;  
  }  
  
  public final V setValue(V newValue) {  
    V oldValue = value;  
    value = newValue;  
    return oldValue;  
  }  
  
  /** 
   * 判断2个Entry是否相等，必须key和value都相等，才返回true  
   */ 
  public final boolean equals(Object o) {  
    if (!(o instanceof Map.Entry))  
      return false;  
    Map.Entry e = (Map.Entry)o;  
    Object k1 = getKey();  
    Object k2 = e.getKey();  
    if (k1 == k2 || (k1 != null && k1.equals(k2))) {  
      Object v1 = getValue();  
      Object v2 = e.getValue();  
      if (v1 == v2 || (v1 != null && v1.equals(v2)))  
        return true;  
    }  
    return false;  
  }  
  
  /** 
   * hashCode（） 
   */ 
  public final int hashCode() { 
    return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());  
  }  
  
  public final String toString() {  
    return getKey() + "=" + getValue();  
  }  
  
  /** 
   * 当向HashMap中添加元素时，即调用put(k,v)时， 
   * 对已经在HashMap中k位置进行v的覆盖时，会调用此方法 
   * 此处没做任何处理 
   */  
  void recordAccess(HashMap<K,V> m) {  
  }  
  
  /** 
   * 当从HashMap中删除了一个Entry时，会调用该函数 
   * 此处没做任何处理 
   */  
  void recordRemoval(HashMap<K,V> m) {  
  } 
}

所以，HashMap的整体结构如下：

重要属性

// 1. 容量（capacity）： HashMap中数组的长度
// a. 容量范围：必须是2的幂 & <最大容量（2的30次方）
// b. 初始容量 = 哈希表创建时的容量
// 默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4=16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

//最大容量 =  2的30次方（若传入的容量过大，将被最大值替换） 
static final int MAXIMUM_CAPACITY = 1 << 30;  

// 2. 加载因子(Load factor)：HashMap在其容量自动增加前可达到多满的一种尺度
// a. 加载因子越大、填满的元素越多 = 空间利用率高、但冲突的机会加大、查找效率变低（因为链表变长了）
// b. 加载因子越小、填满的元素越少 = 空间利用率小、冲突的机会减小、查找效率高（链表不长）
// 实际加载因子
final float loadFactor;
//默认装载因子 = 0.75  
static final float DEFAULT_LOAD_FACTOR = 0.75f;  

// 3. 扩容阈值（threshold）：当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表（即扩充HashMap的容量） 
// a. 扩容 = 对哈希表进行resize操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数
// b. 扩容阈值 = 容量 x 加载因子
int threshold; 

// 存储数据的Entry类型 数组，长度 = 2的幂
// HashMap的实现方式 = 拉链法，Entry数组上的每个元素本质上是一个单向链表
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;  

//HashMap内部的存储结构是一个数组，此处数组为空，即没有初始化之前的状态  
static final Entry<?,?>[] EMPTY_TABLE = {}; 

//实际存储的key-value键值对的个数
transient int size;

//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException
transient int modCount;

//默认的threshold值  
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

加载因子详述

加载因子过大

1. 填充的元素越多，空间利用率也就越高；
2. 冲突概率加大，链表变长，查找效率变小；

加载因子过小

1. 冲突概率减小，链表变短，查找效率变高；
2. 填充的元素越少，空间利用率越低；

使用建议

1. 在查找效率&空间利用率之间寻找一种平衡，即所谓的“空间效率换时间效率” or “时间效率换空间效率”；
2. 若空间内存充足，可选择“空间效率换时间效率”策略，即通过设置过小的加载因子提高查询速度，但也要考虑频繁扩容带来的性能损耗；
3. 若空间内存不足，可选择“时间效率换空间效率”策略，即通过设置过大的加载因子提高空间利用率，但牺牲了查询速率；
4. 加载因子可自定义修改，但非特殊情况不建议修改（默认值=0.75）；

构造方法

HashMap有4个构造器，其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数，会使用默认值。initialCapacity默认为16，loadFactory默认为0.75。

//计算Hash值时的key  
transient int hashSeed = 0;  

/**
 * 构造函数1：默认构造函数（无参）
 * 加载因子 & 容量 = 默认 = 0.75、16
 */  
public HashMap() {  
  // 实际上是调用构造函数3：指定“容量大小”和“加载因子”的构造函数
  // 传入的指定容量 & 加载因子 = 默认
  this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);  
} 

/**
 * 构造函数2：指定“容量大小”的构造函数
 * 加载因子 = 默认 = 0.75 、容量 = 指定大小
 */  
public HashMap(int initialCapacity) {  
  // 实际上是调用指定“容量大小”和“加载因子”的构造函数
  // 只是在传入的加载因子参数 = 默认加载因子
  this(initialCapacity, DEFAULT_LOAD_FACTOR);  
} 

/**
 * 构造函数3：指定“容量大小”和“加载因子”的构造函数
 * 加载因子 & 容量 = 自己指定
 */ 
public HashMap(int initialCapacity, float loadFactor) {  
  if (initialCapacity < 0)//参数有效性检查  
  throw new IllegalArgumentException("Illegal initial capacity: " +             initialCapacity);  
  if (initialCapacity > MAXIMUM_CAPACITY)//参数有效性检查  
  initialCapacity = MAXIMUM_CAPACITY;  
  if (loadFactor <= 0 || Float.isNaN(loadFactor))//参数有效性检查  
  throw new IllegalArgumentException("Illegal load factor: " +  
             loadFactor);  
  // 设置 加载因子
  this.loadFactor = loadFactor;  
  // 设置 扩容阈值 = 初始容量
  threshold = initialCapacity;  
  init();//init方法在HashMap中没有实际实现，不过在其子类如 linkedHashMap中就会有对应实现
}  

/**
 * 构造函数4：包含“子Map”的构造函数
 * 即 构造出来的HashMap包含传入Map的映射关系
 * 加载因子 & 容量 = 默认
 */ 
public HashMap(Map<? extends K, ? extends V> m) {  
   // 设置容量大小 & 加载因子 = 默认
  this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);  
  inflateTable(threshold);//初始化HashMap底层的数组结构  
  putAllForCreate(m);//添加m中的元素  
}

在常规构造器中，并没有马上为数组table分配内存空间（有一个入参为指定Map的构造器例外），事实上是在执行第一次put操作的时候才真正构建table数组。

put操作

源码如下：

public V put(K key, V value)
  // 1. 若哈希表未初始化（即 table为空) 
  // 则使用构造函数设置的阈值(即初始容量) 初始化数组table  
  if (table == EMPTY_TABLE) { 
  inflateTable(threshold); 
  }  
  // 2. 判断key是否为空值null
  // 2.1 若key == null，则将该键-值 存放到数组table 中的第1个位置，即table [0]
  // （本质：key = Null时，hash值 = 0，故存放到table[0]中）
  // 该位置永远只有1个value，新传进来的value会覆盖旧的value
  if (key == null)
  return putForNullKey(value);

  // 2.2 若 key ≠ null，则计算存放数组 table 中的位置（下标、索引）
  // a. 根据键值key计算hash值
  int hash = hash(key);
  // b. 根据hash值 最终获得 key对应存放的数组Table中位置
  int i = indexFor(hash, table.length);

  // 3. 判断该key对应的值是否已存在（通过遍历 以该数组元素为头结点的链表 逐个判断）
  for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  Object k;
  // 3.1 若该key已存在（即 key-value已存在 ），则用 新value 替换 旧value
  if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    V oldValue = e.value;
    e.value = value;
    e.recordAccess(this);
    return oldValue; //并返回旧的value
  }
  }
  //保证并发访问时，若HashMap内部结构发生变化，快速响应失败
  modCount++;

  // 3.2 若 该key不存在，则将“key-value”添加到table中
  addEntry(hash, key, value, i);
  return null;
}

根据源码分析所作出的流程图：

inflateTable–初始化哈希表

private void inflateTable(int toSize) {  
  
  // 1. 将传入的容量大小转化为：>传入容量大小的最小的2的次幂
  // 即如果传入的是容量大小是19，那么转化后，初始化容量大小为32（即2的5次幂）
  int capacity = roundUpToPowerOf2(toSize);

  // 2. 重新计算阈值 threshold = 容量 * 加载因子  
  threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);  

  // 3. 使用计算后的初始容量（已经是2的次幂） 初始化数组table（作为数组长度）
  // 即 哈希表的容量大小 = 数组大小（长度）
  table = new Entry[capacity]; //用该容量初始化table  
  //初始化哈希种子
  initHashSeedAsNeeded(capacity);  
}

inflateTable这个方法用于为主干数组table在内存中分配存储空间，通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂，比如toSize=13,则capacity=16;to_size=16,capacity=16;to_size=17,capacity=32。

private static int roundUpToPowerOf2(int number) {
	//若容量超过了最大值，初始化容量设置为最大值 ；否则，设置为：>传入容量大小的最小的2的次幂
	return number >= MAXIMUM_CAPACITY
			? MAXIMUM_CAPACITY
			: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

putForNullKey

private V putForNullKey(V value) {  
  // 遍历以table[0]为首的链表，寻找是否存在key==null 对应的键值对
  // 1. 若有：则用新value 替换 旧value；同时返回旧的value值
  for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
      if (e.key == null) {   
      V oldValue = e.value;  
      e.value = value;  
      e.recordAccess(this);  
      return oldValue;  
    }  
  }  
  modCount++;  

  // 2 .若无key==null的键，那么调用addEntry（），将空键 & 对应的值封装到Entry中，并放到table[0]中
  addEntry(0, null, value, 0); 
  // 注：
  // a. addEntry（）的第1个参数 = hash值 = 传入0
  // b. 即 说明：当key = null时，也有hash值 = 0，所以HashMap的key 可为null
  // c. 对比HashTable，由于HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null
  // d. 此处只需知道是将 key-value 添加到HashMap中即可
  return null;  

}

计算Hash值

// 计算Hash值：将 键key 转换成 哈希码（hash值）操作  = 使用hashCode() + 4次位运算 + 5次异或运算（9次扰动）
final int hash(Object k) {
    int h = hashSeed;
    //key是String类型的就使用另外的哈希算法
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
    h ^= k.hashCode();
    //扰动函数
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

hash方法的最后两行是真正计算hash值的算法，计算hash码的算法被称为扰动函数，所谓的扰动函数就是把所有东西杂糅到一起，可以看到这里使用了四个向右移位运算。目的就是将h的高位值与低位值混合一下，以此增加低位值的随机性。定位数组的下标是根据hash码的低位值来确定的。key的hash码是通过hashCode方法来生成的，而一个糟糕的hashCode方法生成的hash码的低位值可能会有很大的重复。为了使得hash码在数组上映射的比较均匀，扰动函数就派上用场了，把高位值的特性糅合进低位值，增加低位值的随机性，从而使散列分布的更加松散，以此提高性能。下图举了个例子帮助理解。

计算索引值（数组下标）

/**
 * 计算索引位置
 */
  static int indexFor(int h, int length) {  
	  return h & (length-1); 
	  // 将对哈希码扰动处理后的结果 与运算(&) （数组长度-1），最终得到存储在数组table的位置（即数组下标、索引）
}

h&（length-1）保证获取的index一定在数组范围内，举个例子，默认容量16，length-1=15，h=18,转换成二进制计算为:

    1  0  0  1  0
&   0  1  1  1  1
__________________
    0  0  0  1  0    = 2

最终计算出的index=2。有些版本的对于此处的计算会使用 取模运算，也能保证index一定在数组范围内，不过位运算对计算机来说，性能更高一些（HashMap中有大量位运算）

所以最终存储位置的确定流程是这样的：

addEntry–添加键值对

/**
 * 添加键值对（Entry ）到 HashMap中
 * @param hash--key对应的hash值
 * @param key--键
 * @param value--值
 * @param bucketIndex--存入数组table的索引位置-->数组下标
 */
void addEntry(int hash, K key, V value, int bucketIndex) {
     // 1. 插入前，先判断容量是否足够，若不足够，则进行扩容（2倍）、重新计算Hash值、重新计算存储数组下标
     // 如果HashMap的大小大于阀值并且哈希表对应槽位的值不为空
    if ((size >= threshold) && (null != table[bucketIndex])) {
        //因为HashMap的大小大于阀值, 表明即将发生哈希冲突, 所以进行扩容（2倍扩容）
        resize(2 * table.length);
        //重新计算该key对应的hash值
        hash = (null != key) ? hash(key) : 0;
        //重新计算该key对应的hash值的存储数组下标
        bucketIndex = indexFor(hash, table.length);
    }
    //在这里表明HashMap的大小没有超过阀值, 所以不需要扩容
    //创建1个新的数组元素(Entry)并放入数组中
    createEntry(hash, key, value, bucketIndex);
}

流程如下（键值对的添加方式–>单链表的头插法）：

resize–数组扩容

/**
 * 对哈希表进行扩容，当容量不足时（容量 > 阈值），则扩容（扩到2倍）
 */
void resize(int newCapacity) {
    // 1. 保存旧数组（old table） 
    Entry[] oldTable = table;
    // 2. 保存旧容量（old capacity ），即数组长度
    int oldCapacity = oldTable.length;
    // 3. 若旧容量已经是系统默认最大容量了，那么将阈值设置成整型的最大值，退出    
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    // 4. 根据新容量（2倍容量）新建1个数组，即新table  
    Entry[] newTable = new Entry[newCapacity];
    // 5. 将旧数组上的数据（键值对）转移到新table中，从而完成扩容
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // 6. 将当前哈希表设置为新的哈希表
    table = newTable;
    // 7. 更新哈希表阈值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

流程如下：

transfer–数据转移

 /**
   * 将旧数组上的数据（键值对）转移到新table中，从而完成扩容
   * 过程：按旧链表的正序遍历链表、在新链表的头部依次插入
   */ 
void transfer(Entry[] newTable) {
      // 1. src引用了旧数组
      Entry[] src = table; 

      // 2. 获取新数组的大小 = 获取新容量大小                 
      int newCapacity = newTable.length;

      // 3. 通过遍历 旧数组，将旧数组上的数据（键值对）转移到新数组中
      for (int j = 0; j < src.length; j++) { 
          // 3.1 取得旧数组的每个元素  
          Entry<K,V> e = src[j];           
          if (e != null) {
              // 3.2 释放旧数组的对象引用（for循环后，旧数组不再引用任何对象）
              src[j] = null; 

              do { 
                  // 3.3 遍历 以该数组元素为首 的链表
                  // 注：转移链表时，因是单链表，故要保存下1个结点，否则转移后链表会断开
                  Entry<K,V> next = e.next; 
                 // 3.4 重新计算每个元素的存储位置
                 int i = indexFor(e.hash, newCapacity); 
                 // 3.5 将元素放在数组上：采用单链表的头插入方式 = 在链表头上存放数据 = 将数组位置的原有数据放在后1个指针、将需放入的数据放到数组位置中
                 // 即 扩容后，可能出现逆序：按旧链表的正序遍历链表、在新链表的头部依次插入
                 e.next = newTable[i]; 
                 newTable[i] = e;  
                 // 3.6 访问下1个Entry链上的元素，如此不断循环，直到遍历完该链表上的所有结点
                 e = next;             
             } while (e != null);
             // 如此不断循环，直到遍历完数组上的所有数据元素
         }
     }
 }

流程如下：

createEntry–添加键值对

/**
 * 创建1个新的数组元素（Entry） 并放入到数组中
 */  
void createEntry(int hash, K key, V value, int bucketIndex) { 

    // 1. 把table中该位置原来的Entry保存  
    Entry<K,V> e = table[bucketIndex];

    // 2. 在table中该位置新建一个Entry：将原头结点位置（数组上）的键值对 放入到（链表）后1个结点中、将需插入的键值对 放入到头结点中（数组上）-> 从而形成链表
    // 即 在插入元素时，是在链表头插入的，table中的每个位置永远只保存最新插入的Entry，旧的Entry则放入到链表中（即 解决Hash冲突）
    table[bucketIndex] = new Entry<>(hash, key, value, e);  

    // 3. 哈希表的键值对数量计数增加
    size++;  
}

总结

向 HashMap 添加数据（成对 放入 键 - 值对）的全流程：

get操作

/**
 * 从HashMap中获取数据
 */ 
public V get(Object key) {  

    // 1. 当key == null时，则到 以哈希表数组中的第1个元素（即table[0]）为头结点的链表去寻找对应 key == null的键
    if (key == null)  
        return getForNullKey();

    // 2. 当key ≠ null时，去获得对应值
    Entry<K,V> entry = getEntry(key);
  
    return null == entry ? null : entry.getValue();  
}  


/**
 * 当key == null时，则到 以哈希表数组中的第1个元素（即table[0]）为头结点的链表去寻找对应 key == null的键
 */ 
private V getForNullKey() {  

    if (size == 0) {  
        return null;  
    }  

    // 遍历以table[0]为头结点的链表，寻找 key==null 对应的值
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {  

        // 从table[0]中取key==null的value值 
        if (e.key == null)  
            return e.value; 
    }  
    return null;  
}  
 
/**
 * 当key ≠ null时，去获得对应值
 */  
final Entry<K,V> getEntry(Object key) {  

    if (size == 0) {  
        return null;  
    }  

    // 1. 根据key值，通过hash（）计算出对应的hash值
    int hash = (key == null) ? 0 : hash(key);  

    // 2. 根据hash值计算出对应的数组下标
    // 3. 遍历 以该数组下标的数组元素为头结点的链表所有结点，寻找该key对应的值
    for (Entry<K,V> e = table[indexFor(hash, table.length)];  e != null;  e = e.next) {  

        Object k;  
        // 若 hash值 & key 相等，则证明该Entry = 我们要的键值对
        // 通过equals（）判断key是否相等
        if (e.hash == hash &&  
            ((k = e.key) == key || (key != null && key.equals(k))))  
            return e;  
    }  
    return null;  
}

流程如下：

其他操作

 /**
  * 判断HashMap是否为空，即无键值对；size == 0时 表示为 空 
  */
public boolean isEmpty() {  
    return size == 0;  
} 

 /**
  * 返回哈希表中所有 键值对的数量 = 数组中的键值对 + 链表中的键值对
  */
public int size() {  
    return size;  
}  

 /**
  * 清空哈希表，即删除所有键值对
  * 原理：将数组table中存储的Entry全部置为null、size置为0
  */ 
public void clear() {  
    modCount++;  
    Arrays.fill(table, null);
    size = 0;
}  

/**
 * 将指定Map中的键值对 复制到 此Map中
 */ 
public void putAll(Map<? extends K, ? extends V> m) {  
    // 1. 统计需复制多少个键值对  
    int numKeysToBeAdded = m.size();  
    if (numKeysToBeAdded == 0)  
        return; 

    // 2. 若table还没初始化，先用刚刚统计的复制数去初始化table  
    if (table == EMPTY_TABLE) {  
        inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));  
    }  
  
    // 3. 若需复制的数目 > 阈值，则需先扩容 
    if (numKeysToBeAdded > threshold) {  
        int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);  
        if (targetCapacity > MAXIMUM_CAPACITY)  
            targetCapacity = MAXIMUM_CAPACITY;  
        int newCapacity = table.length;  
        while (newCapacity < targetCapacity)  
            newCapacity <<= 1;  
        if (newCapacity > table.length)  
            resize(newCapacity);  
    }  
    // 4. 开始复制（实际上不断调用Put函数插入）  
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())  
        put(e.getKey(), e.getValue());
}  

 /**
  * 删除该键值对
  */ 
public V remove(Object key) {  
    Entry<K,V> e = removeEntryForKey(key);  
    return (e == null ? null : e.value);  
}  
  
final Entry<K,V> removeEntryForKey(Object key) {  
    if (size == 0) {  
        return null;  
    }  
    // 1. 计算hash值
    int hash = (key == null) ? 0 : hash(key);  
    // 2. 计算存储的数组下标位置
    int i = indexFor(hash, table.length);  
    Entry<K,V> prev = table[i];  
    Entry<K,V> e = prev;  
  
    while (e != null) {  
        Entry<K,V> next = e.next;  
        Object k;  
        if (e.hash == hash &&  
            ((k = e.key) == key || (key != null && key.equals(k)))) {  
            modCount++;  
            size--; 
            // 若删除的是table数组中的元素（即链表的头结点） 
            // 则删除操作 = 将头结点的next引用存入table[i]中  
            if (prev == e) 
                table[i] = next;

            //否则 将以table[i]为头结点的链表中，当前Entry的前1个Entry中的next 设置为 当前Entry的next（即删除当前Entry = 直接跳过当前Entry）
            else  
                prev.next = next;   
            e.recordRemoval(this);  
            return e;  
        }  
        prev = e;  
        e = next;  
    }  
  
    return e;  
} 

 /**
  * 判断是否存在该键的键值对；是 则返回true
  * 原理：调用get（），判断是否为Null
  */
public boolean containsKey(Object key) {  
    return getEntry(key) != null; 
} 

 /**
  * 判断是否存在该值的键值对；是 则返回true
  */   
public boolean containsValue(Object value) {  
    // 若value为空，则调用containsNullValue()  
    if (value == null)
        return containsNullValue();  
    
    // 若value不为空，则遍历链表中的每个Entry，通过equals（）比较values 判断是否存在
    Entry[] tab = table;
    for (int i = 0; i < tab.length ; i++)  
        for (Entry e = tab[i] ; e != null ; e = e.next)  
            if (value.equals(e.value)) 
                return true;//返回true  
    return false;  
}  
  
// value为空时调用的方法  
private boolean containsNullValue() {  
    Entry[] tab = table;  
    for (int i = 0; i < tab.length ; i++)  
        for (Entry e = tab[i] ; e != null ; e = e.next)  
            if (e.value == null)
                return true;  
    return false;  
}

扩容导致死循环分析

HashMap是线程不安全的，原因就是在多线程下并发执行put()操作导致触发扩容resize()，从而导致环形链表，使得在获取数据遍历链表时形成死循环。

resize()的源码前面已经分析过了，从源码可以看出在resize()过程中，在将旧数组上的数据转移到新数组上时，转移数据操作需要将旧链表正序遍历，然后在新链表的头部依次插入，即在转移数据、扩容后，容易出现链表逆序的情况。

假设重新计算存储位置后不变，即扩容前 1->2->3，扩容后 3->2->1，此时若（多线程）并发执行 put（）操作，一旦出现扩容情况，则 容易出现 环形链表，从而在获取数据、遍历链表时 形成死循环（Infinite Loop），即 死锁的状态，如下图：

注：由于 JDK 1.8 转移数据操作 = 按旧链表的正序遍历链表、在新链表的尾部依次插入，所以不会出现链表 逆序、倒置的情况，故不容易出现环形链表的情况。但 JDK 1.8 还是线程不安全，因为 无加同步锁保护。

---

HashMap-Jdk1.8

数据结构

在Jdk1.8中，优化了HashMap的数据结构，引入红黑树，即HashMap的数据结构 = 数组 + 链表 + 红黑树。

引入原因

引入红黑树的目的在于提高HashMap的性能，即解决发生哈希碰撞后，链表过长导致索引效率慢的问题。具体就是利用红黑树快速增删改查的特点，将时间复杂度从原来的O(n)降到O(log(n))。

应用场景

当链表长度>8 时，将该链表转换成红黑树；

数组元素&链表结点实现类

Jdk1.8 HashMap中的数组元素&链表结点采用Node类实现，该类源码如下：

/** 
 * Node = HashMap的内部类，实现了Map.Entry接口，本质是 = 一个映射(键值对)
 * 实现了getKey()、getValue()、equals(Object o)和hashCode()等方法
 **/  
static class Node<K,V> implements Map.Entry<K,V> {

	final int hash; // 哈希值，HashMap根据该值确定记录的位置
	final K key; // key
	V value; // value
	Node<K,V> next;// 链表下一个结点

	// 构造方法
	Node(int hash, K key, V value, Node<K,V> next) {
		this.hash = hash;
		this.key = key;
		this.value = value;
		this.next = next;
	}
	
	public final K getKey()        { return key; }   // 返回 与 此项 对应的键
	public final V getValue()      { return value; } // 返回 与 此项 对应的值
	public final String toString() { return key + "=" + value; }

	public final V setValue(V newValue) {
		V oldValue = value;
		value = newValue;
		return oldValue;
	}

	public final int hashCode() {
		return Objects.hashCode(key) ^ Objects.hashCode(value);
	}

   /** 
	* 判断2个Entry是否相等，必须key和value都相等，才返回true  
	*/
	public final boolean equals(Object o) {
		if (o == this)
			return true;
		if (o instanceof Map.Entry) {
			Map.Entry<?,?> e = (Map.Entry<?,?>)o;
			if (Objects.equals(key, e.getKey()) &&
				Objects.equals(value, e.getValue()))
				return true;
		}
		return false;
	}
}

红黑树结点实现类

/**
 * 红黑树结点 实现类：继承自LinkedHashMap.Entry<K,V>类
 */
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {  

// 属性 = 父结点、左子树、右子树、删除辅助结点 + 颜色
TreeNode<K,V> parent;  
TreeNode<K,V> left;   
TreeNode<K,V> right;
TreeNode<K,V> prev;   
boolean red;   

// 构造函数
TreeNode(int hash, K key, V val, Node<K,V> next) {  
	super(hash, key, val, next);  
}  

// 返回当前结点的根结点  
final TreeNode<K,V> root() {  
	for (TreeNode<K,V> r = this, p;;) {  
		if ((p = r.parent) == null)  
			return r;  
		r = p;  
	}  
}

重要属性

/** 
 * 主要参数 同  JDK 1.7 
 * 即：容量、加载因子、扩容阈值（要求、范围均相同）
 */

// 1. 容量（capacity）： 必须是2的幂 & <最大容量（2的30次方）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认容量 = 16 = 1<<4 = 00001中的1向左移4位 = 10000 = 十进制的2^4=16
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量 =  2的30次方（若传入的容量过大，将被最大值替换）

// 2. 加载因子(Load factor)：HashMap在其容量自动增加前可达到多满的一种尺度 
final float loadFactor; // 实际加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认加载因子 = 0.75

// 3. 扩容阈值（threshold）：当哈希表的大小 ≥ 扩容阈值时，就会扩容哈希表（即扩充HashMap的容量） 
// a. 扩容 = 对哈希表进行resize操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数
// b. 扩容阈值 = 容量 x 加载因子
int threshold;

// 4. 其他
transient Node<K,V>[] table;  // 存储数据的Node类型 数组，长度 = 2的幂；数组的每个元素 = 1个单链表
transient int size;// HashMap的大小，即 HashMap中存储的键值对的数量
 

/** 
 * 与红黑树相关的参数
 */
 // 1. 桶的树化阈值：即 链表转成红黑树的阈值，在存储数据时，当链表长度 > 该值时，则将链表转换成红黑树
 static final int TREEIFY_THRESHOLD = 8; 
 // 2. 桶的链表还原阈值：即 红黑树转为链表的阈值，当在扩容（resize（））时（此时HashMap的数据存储位置会重新计算），在重新计算存储位置后，当原有的红黑树内数量 < 6时，则将 红黑树转换成链表
 static final int UNTREEIFY_THRESHOLD = 6;
 // 3. 最小树形化容量阈值：即 当哈希表中的容量 > 该值时，才允许树形化链表 （即 将链表 转换成红黑树）
 // 否则，若桶内元素太多时，则直接扩容，而不是树形化
 // 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
 static final int MIN_TREEIFY_CAPACITY = 64;

构造函数

/**
 * 源码分析：主要是HashMap的构造函数 = 4个
 * 仅贴出关于HashMap构造函数的源码
 */
public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable{

    // 省略上节阐述的参数
    
  /**
     * 构造函数1：默认构造函数（无参）
     * 加载因子 & 容量 = 默认 = 0.75、16
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }

    /**
     * 构造函数2：指定“容量大小”的构造函数
     * 加载因子 = 默认 = 0.75 、容量 = 指定大小
     */
    public HashMap(int initialCapacity) {
        // 实际上是调用指定“容量大小”和“加载因子”的构造函数
        // 只是在传入的加载因子参数 = 默认加载因子
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
        
    }

    /**
     * 构造函数3：指定“容量大小”和“加载因子”的构造函数
     * 加载因子 & 容量 = 自己指定
     */
    public HashMap(int initialCapacity, float loadFactor) {

    	// 指定初始容量必须非负，否则报错  
   		 if (initialCapacity < 0)  
           throw new IllegalArgumentException("Illegal initial capacity: " +  
                                           initialCapacity); 

        // HashMap的最大容量只能是MAXIMUM_CAPACITY，哪怕传入的 > 最大容量
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;

        // 填充比必须为正  
    	if (loadFactor <= 0 || Float.isNaN(loadFactor))  
        	throw new IllegalArgumentException("Illegal load factor: " +  
                                           loadFactor);  
        // 设置 加载因子
        this.loadFactor = loadFactor;

        // 设置 扩容阈值
        // 注：此处不是真正的阈值，仅仅只是将传入的容量大小转化为：>传入容量大小的最小的2的幂，该阈值后面会重新计算
        this.threshold = tableSizeFor(initialCapacity); 

    }

    /**
     * 构造函数4：包含“子Map”的构造函数
     * 即 构造出来的HashMap包含传入Map的映射关系
     * 加载因子 & 容量 = 默认
     */

    public HashMap(Map<? extends K, ? extends V> m) {

        // 设置容量大小 & 加载因子 = 默认
        this.loadFactor = DEFAULT_LOAD_FACTOR; 

        // 将传入的子Map中的全部元素逐个添加到HashMap中
        putMapEntries(m, false); 
    }
}

/**
 * 将传入的容量大小转化为：>传入容量大小的最小的2的幂
 * 与JDK 1.7对比：类似于JDK 1.7 中 inflateTable()里的 roundUpToPowerOf2(toSize)
 */
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;
  return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

put操作

/**
 * 源码分析：主要分析HashMap的put函数
 */
public V put(K key, V value) {
	// 1. 对传入数组的键Key计算Hash值
	// 2. 再调用putVal（）添加数据进去
	return putVal(hash(key), key, value, false, true);
}

hash–计算Hash值

/**
 * hash(key)
 * 作用：计算传入数据的哈希码（哈希值、Hash值）
 * 该函数在JDK 1.7 和 1.8 中的实现不同，但原理一样 = 扰动函数 = 使得根据key生成的哈希码（hash值）分布更加均匀、更具备随机性，避免出现hash值冲突（即指不同key但生成同1个hash值）
 * JDK 1.7 做了9次扰动处理 = 4次位运算 + 5次异或运算
 * JDK 1.8 简化了扰动函数 = 只做了2次扰动 = 1次位运算 + 1次异或运算
 */
  // JDK 1.8实现：将 键key 转换成 哈希码（hash值）操作 = 使用hashCode() + 1次位运算 + 1次异或运算（2次扰动）
  // 1. 取hashCode值： h = key.hashCode() 
  // 2. 高位参与低位的运算：h ^ (h >>> 16)  
  static final int hash(Object key) {
	   int h;
		return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
		// a. 当key = null时，hash值 = 0，所以HashMap的key 可为null      
		// 注：对比HashTable，HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null
		// b. 当key ≠ null时，则通过先计算出 key的 hashCode()（记为h），然后 对哈希码进行 扰动处理： 按位 异或（^） 哈希码自身右移16位后的二进制
 }

putVal–存放数据到哈希表

由于数据结构中加入了红黑树，所以在存放数据到哈希表中时，需进行多次数据结构的判断：数组、红黑树、链表。

 /**
  * 存放数据到哈希表
  */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
			   boolean evict) {
	Node<K,V>[] tab; Node<K,V> p; int n, i;
	// 1. 若哈希表的数组tab为空或者长度为0，则 通过resize() 创建
    // 所以，初始化哈希表的时机 = 第1次调用put函数时，即调用resize() 初始化创建
	if ((tab = table) == null || (n = tab.length) == 0)
		n = (tab = resize()).length;
	// 2. 计算插入存储的数组索引i：根据键值key计算的hash值 得到
    // 此处的数组下标计算方式 = i = (n - 1) & hash，同JDK 1.7中的indexFor（）
	
	// 3. 插入时，需判断是否存在Hash冲突：
	// 若不存在（即当前table[i] == null），则直接在该数组位置新建结点，插入完毕
	// 否则，代表存在Hash冲突，即当前存储位置已存在结点，则依次往下判断：
	// a. 当前位置的key是否与需插入的key相同、
	// b. 判断需插入的数据结构是否为红黑树 or 链表
	if ((p = tab[i = (n - 1) & hash]) == null)
		tab[i] = newNode(hash, key, value, null);
	else {//说明待插入位置存在元素
		Node<K,V> e; K k;
		// a. 判断 table[i]的元素的key是否与 需插入的key一样，若相同则 直接用新value 覆盖 旧value
        // 判断原则：equals（）
		if (p.hash == hash &&
			((k = p.key) == key || (key != null && key.equals(k))))
			//将第一个元素赋值给e，用e来记录
			e = p;
			
		// b. 继续判断：需插入的数据结构是否为红黑树 or 链表
        // 若是红黑树，则直接在树中插入 or 更新键值对	
		else if (p instanceof TreeNode)
			e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
			
        // 若是链表,则在链表中插入 or 更新键值对
        // i.  遍历table[i]，判断Key是否已存在：采用equals（） 对比当前遍历结点的key 与 需插入数据的key：若已存在，则直接用新value 覆盖 旧value
        // ii. 遍历完毕后仍无发现上述情况，则直接在链表尾部插入数据
        // 注：新增结点后，需判断链表长度是否>8（8 = 桶的树化阈值）：若是，则把链表转换为红黑树	
		else {
            //在链表末尾插入结点
			for (int binCount = 0; ; ++binCount) {
                // 对于ii：若数组的下1个位置，表示已到表尾也没有找到key值相同结点，则新建结点 = 插入结点
                // 注：此处是从链表尾插入，与JDK 1.7不同（从链表头插入，即永远都是添加到数组的位置，原来数组位置的数据则往后移）
				if ((e = p.next) == null) {
					p.next = newNode(hash, key, value, null);
					
                    // 插入结点后，若链表结点>数阈值，则将链表转换为红黑树
					if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //链表转红黑树
						treeifyBin(tab, hash);
					break;
				}
                //遍历table[i]，判断Key是否已存在：采用equals（） 对比当前遍历结点的key 与 需插入数据的key
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
                    //相等，跳出循环
					break;
                // 更新p指向下一个结点，继续遍历	
				p = e;
			}
		}
        //表示在桶中找到key值、hash值与插入元素相等的结点，直接用新value 覆盖 旧value 并 返回旧value
		if (e != null) { // existing mapping for key
            //记录e的value
			V oldValue = e.value;
			if (!onlyIfAbsent || oldValue == null)
                //新值替换旧值
				e.value = value;
			afterNodeAccess(e);// 替换旧值时会调用的方法（默认实现为空）
            //返回旧值
			return oldValue;
		}
	}
	++modCount;
     // 插入成功后，判断实际存在的键值对数量size > 最大容量threshold
     // 若 > ，则进行扩容 
	if (++size > threshold)
		resize();
	afterNodeInsertion(evict);// 插入成功时会调用的方法（默认实现为空）
	return null;
}

/**
 * 向红黑树插入 or 更新数据（键值对）
 * 过程：遍历红黑树判断该结点的key是否与需插入的key 相同：
 * a. 若相同，则新value覆盖旧value
 * b. 若不相同，则插入
 */
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
							   int h, K k, V v) {
	Class<?> kc = null;
	boolean searched = false;
	TreeNode<K,V> root = (parent != null) ? root() : this;
    //从根结点开始查找合适的插入位置（与二叉搜索树查找过程相同）
	for (TreeNode<K,V> p = root;;) {
		int dir, ph; K pk;
		if ((ph = p.hash) > h)
			dir = -1;//dir小于0，接下来查找当前结点的左孩子
		else if (ph < h)
			dir = 1;//dir大于0，接下来查找当前结点的右孩子
		else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            //这里代表hash值相同，key相同
			return p;
			
        /**
         *要进入下面这个else if,代表有以下几个含义:
         *1、当前结点与待插入结点　key　不同,　hash 值相同;
         *2、ｋ是不可比较的，即ｋ并未实现comparable<K>接口
         * （若 k 实现了comparable<K>　接口，comparableClassFor（k）返回的是ｋ的class,而不是null）
         * 或者compareComparables(kc, k, pk)返回值为 0
         * (pk 为空　或者　按照 k.compareTo(pk) 返回值为０，
         * 返回值为０可能是由于ｋ的compareTo 方法实现不当引起的，compareTo 判定相等，而上个 else if　中　equals 判定不等)
         */		 
		else if ((kc == null &&
				  (kc = comparableClassFor(k)) == null) ||
				 (dir = compareComparables(kc, k, pk)) == 0) {
            //在以当前结点为根的整个树上搜索是否存在待插入的结点（只会搜索一次）	 
			if (!searched) {
				TreeNode<K,V> q, ch;
				searched = true;
				if (((ch = p.left) != null &&
					 (q = ch.find(h, k, kc)) != null) ||
					((ch = p.right) != null &&
					 (q = ch.find(h, k, kc)) != null))
					return q;
			}
            //如果仍未比较出大小，就需要进行仲裁了，仲裁方法为 tieBreakOrder
			dir = tieBreakOrder(k, pk);
		}

		TreeNode<K,V> xp = p;
		if ((p = (dir <= 0) ? p.left : p.right) == null) {
            //找到了待插入的位置，xp 为待插入结点的父结点
            //注意TreeNode结点中既存在树状关系，也存在链式关系，并且是双端链表
			Node<K,V> xpn = xp.next;
			TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
			if (dir <= 0)
				xp.left = x;
			else
				xp.right = x;
			xp.next = x;
			x.parent = x.prev = xp;
			if (xpn != null)
				((TreeNode<K,V>)xpn).prev = x;
            //插入结点后进行二叉树的平衡操作	
			moveRootToFront(tab, balanceInsertion(root, x));
			return null;
		}
	}
}

/**
 * 将普通结点链表转换成树形结点链表
 * 树化要满足两个条件：
 * 1. 链表长度大于等于 TREEIFY_THRESHOLD
 * 2. 桶数组容量大于等于 MIN_TREEIFY_CAPACITY
 * 第一个条件比较好理解，加入第二个条件，个人觉得原因如下：
 * 当桶数组容量比较小时，键值对结点 hash 的碰撞率可能会比较高，进而导致链表长度较长。
 * 这个时候应该优先扩容，而不是立马树化。毕竟高碰撞率是因为桶数组容量较小引起的，这个是主因。
 * 容量小时，优先扩容可以避免一些不必要的树化过程。
 * 同时，桶容量较小时，扩容会比较频繁，扩容时需要拆分红黑树并重新映射。所以在桶容量比较小的情况下，将长链表转成红黑树是一件吃力不讨好的事。
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
	int n, index; Node<K,V> e;
	// 如果 tab.length 小于 MIN_TREEIFY_CAPACITY， 优先进行扩容而不是树化
	if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
		resize();
	else if ((e = tab[index = (n - 1) & hash]) != null) {
	    // hd 为头结点（head），tl 为尾结点（tail）
		TreeNode<K,V> hd = null, tl = null;
		do {
            // 将普通结点替换成树形结点
			TreeNode<K,V> p = replacementTreeNode(e, null);
			if (tl == null)
				hd = p;
			else {
				p.prev = tl;
				tl.next = p;
			}
			tl = p;
		} while ((e = e.next) != null);// 将普通链表转成由树形结点链表
		if ((tab[index] = hd) != null)
            // 将树形链表转换成红黑树
			hd.treeify(tab);
	}
}

流程图如下：

resize–扩容

/**
 * 扩容
 * 该函数有2种使用情况：1.初始化哈希表 2.当前数组容量过小，需扩容
 */
final Node<K,V>[] resize() {
    // 扩容前的数组（当前数组）
	Node<K,V>[] oldTab = table;
	// 扩容前的数组的容量 = 长度
	int oldCap = (oldTab == null) ? 0 : oldTab.length;
	/// 扩容前的数组的阈值
	int oldThr = threshold;
	int newCap, newThr = 0;
	// 如果 table 不为空，表明已经初始化过了
	if (oldCap > 0) {
	    //若扩容前的数组容量超过最大值，则不再扩容
		if (oldCap >= MAXIMUM_CAPACITY) {
			threshold = Integer.MAX_VALUE;
			return oldTab;
		}
		//若未超过最大值，则扩容为原来的2倍
		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
        /*
         * 初始化时，将 threshold 的值赋值给 newCap，
         * HashMap 使用 threshold 变量暂时保存 initialCapacity 参数的值
         */ 
		newCap = oldThr;
	else {
        /*
         * 调用无参构造方法时，桶数组容量为默认容量，
         * 阈值为默认容量与默认负载因子乘积
         */
		newCap = DEFAULT_INITIAL_CAPACITY;
		newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
	}
	//计算新的resize上限
	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) {
        // 把每个bucket都移动到新的buckets中
		for (int j = 0; j < oldCap; ++j) {
			Node<K,V> e;
			if ((e = oldTab[j]) != null) {
			    // 清除原来table[i]中的值
				oldTab[j] = null;
				if (e.next == null)
					newTab[e.hash & (newCap - 1)] = e;
				else if (e instanceof TreeNode)
				//如果e是红黑树结点，走红黑树替换方式
					((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
				else {// 如果 table[j] 后是一个链表 ，将原链表拆分为两条链，分别放到newTab中 
					Node<K,V> loHead = null, loTail = null;
					Node<K,V> hiHead = null, hiTail = null;
					Node<K,V> next;
					do {
						next = e.next;
						// 原索引，(e.hash & oldCap) == 0 说明 在put操作通过 hash & newThr
                        //计算出的索引值等于现在的索引值。
						if ((e.hash & oldCap) == 0) {
							if (loTail == null)
								loHead = e;
							else
								loTail.next = e;
							loTail = e;
						}
						// 原索引+oldCap，不是原索引，就移动原来的长度
						else {
							if (hiTail == null)
								hiHead = e;
							else
								hiTail.next = e;
							hiTail = e;
						}
					} while ((e = next) != null);
					//原索引放到bucket里
					if (loTail != null) {
						loTail.next = null;
						newTab[j] = loHead;
					}
					// 原索引+oldCap放到bucket里
					if (hiTail != null) {
						hiTail.next = null;
						newTab[j + oldCap] = hiHead;
					}
				}
			}
		}
	}
	return newTab;
}

// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 这个函数的功能是对红黑树进行rehash 操作(拆分红黑树)
 * 重新映射红黑树的逻辑和重新映射链表的逻辑基本一致。不同的地方在于，重新映射后，会将红黑树拆分成两条由 TreeNode 组成的链表。
 * 如果链表长度小于 UNTREEIFY_THRESHOLD，则将链表转换成普通链表。否则根据条件重新将 TreeNode 链表树化。
 */
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
	TreeNode<K,V> b = this;
	// Relink into lo and hi lists, preserving order
	TreeNode<K,V> loHead = null, loTail = null;
	TreeNode<K,V> hiHead = null, hiTail = null;
	int lc = 0, hc = 0;
	//由于TreeNode 结点之间存在双端链表的关系，可以利用链表关系进行 rehash
	for (TreeNode<K,V> e = b, next; e != null; e = next) {
		next = (TreeNode<K,V>)e.next;
		e.next = null;
		if ((e.hash & bit) == 0) {
			if ((e.prev = loTail) == null)
				loHead = e;
			else
				loTail.next = e;
			loTail = e;
			++lc;
		}
		else {
			if ((e.prev = hiTail) == null)
				hiHead = e;
			else
				hiTail.next = e;
			hiTail = e;
			++hc;
		}
	}
    
	// 如果 loHead 不为空，且链表长度小于等于 6，则将红黑树转成链表
	if (loHead != null) {
		if (lc <= UNTREEIFY_THRESHOLD)
			tab[index] = loHead.untreeify(map);
		else {
			tab[index] = loHead;
			/* 
             * hiHead == null 时，表明扩容后，
             * 所有结点仍在原位置，树结构不变，无需重新树化
             */
			if (hiHead != null) 
				loHead.treeify(tab);
		}
	}
	// 与上面类似
	if (hiHead != null) {
		if (hc <= UNTREEIFY_THRESHOLD)
			tab[index + bit] = hiHead.untreeify(map);
		else {
			tab[index + bit] = hiHead;
			if (loHead != null)
				hiHead.treeify(tab);
		}
	}
}

/**
 *红黑树链化
 */
final Node<K,V> untreeify(HashMap<K,V> map) {
    Node<K,V> hd = null, tl = null;
    // 遍历 TreeNode 链表，并用 Node 替换
    for (Node<K,V> q = this; q != null; q = q.next) {
        // 替换结点类型
        Node<K,V> p = map.replacementNode(q, null);
        if (tl == null)
            hd = p;
        else
            tl.next = p;
        tl = p;
    }
    return hd;
}

Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
    return new Node<>(p.hash, p.key, p.value, next);
}

流程如下：

resize()方法中比较重要的是链表和红黑树的 rehash 操作，rehash 的实现原理如下：

在扩容的时候，一般是把长度扩为原来2倍，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。

如下图所示，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。

元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

因此，在扩充HashMap的时候，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：

这个算法很巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的结点分散到新的槽中了。

get操作

/**
 *从HashMap中获取数据
 */
public V get(Object key) {
	Node<K,V> e;
    // 1. 计算需获取数据的hash值
    // 2. 通过getNode（）获取所查询的数据
    // 3. 获取后，判断数据是否为空
	return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
 * 获取所要查询的数据
 */
final Node<K,V> getNode(int hash, Object key) {
	Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
	// 1. 计算存放在数组table中的位置
	if ((tab = table) != null && (n = tab.length) > 0 &&
		(first = tab[(n - 1) & hash]) != null) {
		//根据当前传入的hash值以及参数key获取一个结点即为first,如果匹配的话返回对应的value值
        // a. 先在数组中找，若存在，则直接返回
		if (first.hash == hash && // always check first node
			((k = first.key) == key || (key != null && key.equals(k))))
			return first;
        // b. 若数组中没有，则到红黑树中寻找	
		if ((e = first.next) != null) {
			if (first instanceof TreeNode)
				return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // c. 若红黑树中也没有，则通过遍历，到链表中寻找	
			do {
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					return e;
			} while ((e = e.next) != null);
		}
	}
	return null;
}

流程如下：

HashMap Jdk1.7和Jdk1.8的区别

数据结构

添加数据

获取数据

扩容机制

---

ConcurrentHashMap-Jdk1.7

数据结构

ConcurrentHashMap采用分段锁的设计Segment + HashEntry的方式进行实现，采用table数组＋单向链表的数据结构，结构如下：

重要属性

//默认ConcurrentHashMap的大小
static final int DEFAULT_INITIAL_CAPACITY = 16;

//默认加载因子，用于表示segment中包含的HashEntry元素的个数与HashEntry[]数组长度的比值。
//当某个segment中包含的HashEntry元素的个数超过了HashEntry[]数组的长度与装载因子的乘积时，将触发扩容操作。
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//默认支持的最大并发数，该值表示segment[]数组的长度，也就是锁的总数。
static final int DEFAULT_CONCURRENCY_LEVEL = 16;

//ConcurrentHashMap的最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

//segment分段锁的初始容量也是最小容量(即segment中HashEntry的初始容量)
static final int MIN_SEGMENT_TABLE_CAPACITY = 2;

//最大segment数(segments数组的最大长度)
static final int MAX_SEGMENTS = 1 << 16; // slightly conservative

//重试加锁次数：在执行size()和containsValue(value)操作时,ConcurrentHashMap的做法是先尝试 RETRIES_BEFORE_LOCK 次(默认2次)
//通过不锁住segment的方式来统计、查询各个segment，如果2次执行过程中，容器的modCount发生了变化，则再采用加锁的方式来操作所有的segment
static final int RETRIES_BEFORE_LOCK = 2;

//分段锁的掩码，用来计算key所在的segment在segments的数组下标
final int segmentMask;

//分段锁偏移量,用来查找segment在内存中的位置
final int segmentShift;

//segment数组，Segment 类继承于 ReentrantLock 类，从而使得 Segment 对象能充当锁的角色。
final Segment<K,V>[] segments;

重要对象

Segment

Segment 类继承于 ReentrantLock 类，从而使得 Segment 对象能充当锁的角色，并且是一个可重入锁。每个 Segment 对象维护其包含的若干个桶(即HashEntry[])。

static final class Segment<K,V> extends ReentrantLock implements Serializable {

	private static final long serialVersionUID = 2249069246763182397L;

	//最大自旋次数，若是单核则为1，多核则为64。该字段用于scanAndLockForPut、scanAndLock方法
	static final int MAX_SCAN_RETRIES =
		Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;

    /**
     * table 是由 HashEntry 对象组成的数组
     * 如果散列时发生碰撞，碰撞的 HashEntry 对象就以链表的形式链接成一个链表
     * table 数组的元素代表散列映射表的一个桶
     * 每个 table 守护整个 ConcurrentHashMap 数据总数的一部分
     * 如果并发级别为 16，table 则维护 ConcurrentHashMap 数据总数的 1/16 
     */
	transient volatile HashEntry<K,V>[] table;

	//segment中HashEntry的总数
	transient int count;

	//segment中数据被更新的次数
	transient int modCount;

	//元素的阀值，当table中包含的HashEntry元素的个数超过本变量值时，触发table的扩容
	transient int threshold;

	//加载因子
	final float loadFactor;	
}

HashEntry

HashEntry封装了key-value对，是一个单向链表结构，每个HashEntry结点都维护着next HashEntry结点的引用。

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

	HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
		this.hash = hash;
		this.key = key;
		this.value = value;
		this.next = next;
	}
}

初始化

public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
	if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
		throw new IllegalArgumentException();
	//保证最大并发不超过MAX_SEGMENTS(1 << 16)
	if (concurrencyLevel > MAX_SEGMENTS)
		concurrencyLevel = MAX_SEGMENTS;
	// Find power-of-two sizes best matching arguments
	int sshift = 0;
	int ssize = 1;
	//循环判断保证ssize是2的幂(即Segment数组的长度)
	//循环完sshift = 4,ssize = 16
	while (ssize < concurrencyLevel) {
		++sshift;
		ssize <<= 1;//ssize = size << 1
	}
	//segmentShift最后为28
	this.segmentShift = 32 - sshift;
	//segmentMask最后为15
	this.segmentMask = ssize - 1;
	//ConcurrentHashMap初始容量不超过MAXIMUM_CAPACITY(1 << 30)
	if (initialCapacity > MAXIMUM_CAPACITY)
		initialCapacity = MAXIMUM_CAPACITY;
	//根据ConcurrentHashMap总容量initialCapacity除以Segments[]数组的长度得到单个分段锁segment中HashEntry[]的大小
	int c = initialCapacity / ssize;
	//保证分段锁segment的总容量c不小于初始的容量
	if (c * ssize < initialCapacity)
		++c;
	//cap为Segments[]数组中分段锁segment的HashEntry[]的大小,保证为2的幂
	int cap = MIN_SEGMENT_TABLE_CAPACITY;
	while (cap < c)
		cap <<= 1;
	// create segments and segments[0]
	//记住这里★
	//创建一个s0,然后初始化到Segments[0]中
	Segment<K,V> s0 =
		new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
						 (HashEntry<K,V>[])new HashEntry[cap]);
	//创建Segments[]数组
	Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
	UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
	this.segments = ss;
}

根据用户创建new ConcurrentHashMap(....)时，传递的值或者默认值进行ConcurrentHashMap的初始化。
创建一个Segments[]数组，最大数组长度是16，不可以扩容。
Segments[i]的默认大小为2，负载因子为0.75，得出初始阈值为1.5，也就插入第一个元素不会触发扩容，插入第二个进行一次扩容。
初始化了 Segments[0]，其他位置还是null。

put操作

public V put(K key, V value) {
	Segment<K,V> s;
	//判断value是否为null,如果为null则抛出空指针异常 
	if (value == null)
		throw new NullPointerException();
	//计算key的HASH值
	int hash = hash(key);
	//无符号右移segmentShift位(默认16),然后 & segmentMask(默认15)得到segment在内存中的地址
	int j = (hash >>> segmentShift) & segmentMask;
	//判断该位置是否为null， 
	if ((s = (Segment<K,V>)UNSAFE.getObject          
		 (segments, (j << SSHIFT) + SBASE)) == null) //如果获取到的segment为null
		s = ensureSegment(j);//初始化segment
	//如果为null，初始化该位置segment[j]，通过ensureSegment(j) s = ensureSegment(j); 
	//调用Segment的put方法将数据插入到HashEntry中
	return s.put(key, hash, value, false);
}

根据hash值获取分段锁segment的内存地址，如果获取到的segment为null，则初始化。否则就是放值。整体流程如下图：

ensureSegment-初始化segment

private Segment<K,V> ensureSegment(int k) {
	//拿到当前Segments[]数组
	final Segment<K,V>[] ss = this.segments;
	//获取k所在的segment在内存中的偏移量
	long u = (k << SSHIFT) + SBASE; // raw offset
	Segment<K,V> seg;
	//获取k所在的segmen,判断segmen是否为null
	if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
		//初始化一个segment等于Segments[0]
		//Segments[0]在初始化ConcurrentHashMap时，已经初始化了一个segment放到Segments[0]。
		Segment<K,V> proto = ss[0]; // use segment 0 as prototype
		//然后就是获取Segments[0]中HashEntry数组的数据
		int cap = proto.table.length;
		float lf = proto.loadFactor;
		int threshold = (int)(cap * lf);
		//初始化一个HashEntry数组,大小和Segments[0]中的HashEntry一样。
		HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
		//再次获取k所在的segment(防止其他线程已经初始化好)
		if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) { // recheck
			//如果还是null，创建一个segment并通过cas设置到对应的位置
			Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
			// 使用 while 循环，内部用 CAS，当前线程成功设值或其他线程成功设值后，退出
			while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
				if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
					break;
			}
		}
	}
	return seg;
}

根据k的hash值，获取segment，如何获取不到则就初始化一个和Segment[0]一样大小的segment。并通过CAS操作，初始化到Segments[]中。

put-放值

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
	//尝试获取segment的锁
	//失败就通过自旋去获取锁,超过自旋最大次数时,就将操作放入到Lock锁的队列中
	HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
	V oldValue;
	//走到这里的线程一定获取到锁,没获取到的都放到了Lock的队列中
	try {
		//拿到segment中的HashEntry数组
		HashEntry<K,V>[] tab = table;
		//得到key所在HashEntry数组的下标
		int index = (tab.length - 1) & hash;
		//获取key所在的HashEntry数组某个位置的头结点(HashEntry是一个数组加链表结构)
		HashEntry<K,V> first = entryAt(tab, index);
		for (HashEntry<K,V> e = first;;) {
			if (e != null) {//HashEntry头结点不为null
				K k;
				//找到传入的值
				if ((k = e.key) == key ||
				        (e.hash == hash && key.equals(k))) {
					oldValue = e.value;
					//是否替换value,默认替换(有个putIfAbsent(key,value)就是不替换)
					if (!onlyIfAbsent) {
						e.value = value;
						++modCount;
					}
					break;
				}
				e = e.next;
			} else {//如果没有找到或HashEntry头结点为null
			    //判断node是否已经初始化(自旋获取锁做的这些操作,这个node要么为null要么就是新建的HashEntry)
				if (node != null)
					node.setNext(first);//头插法
				else
					node = new HashEntry<K,V>(hash, key, value, first);//头插法
				int c = count + 1;//修改segment的元素总数
				if (c > threshold && tab.length < MAXIMUM_CAPACITY)//如果超过segment的阀值并且segment没有超过最大容量,rehash
					//扩容
					rehash(node);
				else
				    //更新HashEntry数组，把新的结点放在tab的index上面
					setEntryAt(tab, index, node);
				++modCount;
				count = c;
				oldValue = null;
				break;
			}
		}
	}
	finally {
		unlock();//释放锁
	}
	return oldValue;
}

首先是尝试获取segment的锁，获取到向下执行，获取不到就通过自旋操作去获取锁。
拿到锁之后，找到k所在的HashEntry数组的下标，然后获取头结点。向下遍历头结点，查找到就更新（默认），没查找到就新建一个HashEntry，通过头插法放入HashEntry数组，最后更新HashEntry。

scanAndLockForPut-获取锁

private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
	//获取k所在的segment中的HashEntry的头结点(segment中放得是HashEntry数组,HashEntry又是个链表结构)
	HashEntry<K,V> first = entryForHash(this, hash);
	HashEntry<K,V> e = first;
	HashEntry<K,V> node = null;
	int retries = -1; // negative while locating node
	while (!tryLock()) {//尝试获取k所在segment的锁。成功就直接返回、失败进入while循环进行自旋尝试获取锁
		HashEntry<K,V> f; // to recheck first below
		if (retries < 0) {
			if (e == null) {//所在HashEntry链表不存在，则根据传过来的key-value创建一个HashEntry
				if (node == null) // speculatively create node
				    //初始化node
					node = new HashEntry<K,V>(hash, key, value, null);
				retries = 0;
			} else if (key.equals(e.key))//找到要放得值,则设置segment重试次数为0
				retries = 0;
			else //从头结点往下寻找key对应的HashEntry
				e = e.next;
		} else if (++retries > MAX_SCAN_RETRIES) {//超过最大重试次数就将当前操作放入到Lock的队列中，改为阻塞锁获取，保证能获取成功
			lock();
			break;
		} else if ((retries & 1) == 0 &&
		           (f = entryForHash(this, hash)) != first) {//如果retries为偶数,就重新获取HashEntry链表的头结点
			e = first = f; // re-traverse if entry changed
			retries = -1;
		}
	}
	return node;
}

拿到k所在的segment的HashEntry的头结点(想想segment中的数据结构)，首先尝试获取segment的锁。

1. 获取失败

   • • 如果头结点为null，则将传进来的key-value新建一个HashEntry，同时设置retries为0，从而再次去尝试获取segment的锁；
     • 如果头结点不为null，并且头结点的key == 传进来的key，设置retries为0，从而再次去尝试获取segment的锁；
     • 如果头结点不为null，并且头结点的key != 传进来的key 则获取头结点的下一个结点，再次尝试获取segment的锁；
   • 如果retries > MAX_SCAN_RETRIES 则调用reentrantlock的lock方法，将当前操作放入到lock队列中跳出while循环；
   • 如果retries为偶数，则再次获取对应segment的头结点，判断是否有变化，有就重新获取头结点；

2. 获取成功：直接返回null

rehash-扩容

private void rehash(HashEntry<K,V> node) {//node为待新加入的结点
	//获取当前segment的HashEntry数组
	HashEntry<K,V>[] oldTable = table;
	//获取原HashEntry数组的长度
	int oldCapacity = oldTable.length;
	//新HashEntry数组的长度 = 原HashEntry数组长度*2
	int newCapacity = oldCapacity << 1;
	//重新计算新HashEntry数组的阀值
	threshold = (int)(newCapacity * loadFactor);
	//创建新HashEntry数组
	HashEntry<K,V>[] newTable =
	    (HashEntry<K,V>[]) new HashEntry[newCapacity];
	//新HashEntry数组的掩码(用来计算元素在新数组中的下标位置)
	int sizeMask = newCapacity - 1;
	//遍历原HashEntry数组中的元素(segment中是一个HashEntry数组，结构是数组加链表)
	for (int i = 0; i < oldCapacity ; i++) {
		//获取原HashEntry[i]位置的头结点HashEntry
		HashEntry<K,V> e = oldTable[i];
		//判断当前结点是否为空
		if (e != null) {
			//获取当前结点的下一个结点
			HashEntry<K,V> next = e.next;
			//重新计算当前结点在新HashEntry数组中的下标
			int idx = e.hash & sizeMask;
			//如果下一个结点为空，则原HashEntry数组这个位置就一个元素，直接放到新HashEntry数组就行
			if (next == null)   //  Single node on list
				newTable[idx] = e;
			//下个结点不为空
			else { // Reuse consecutive sequence at same slot
				//这里就是找到某个结点，从这个结点往下，都会在新数组的某个坐标下，形成新的链表
				//原:
				//HashEntry:[0] [1]...
				//里面的值:  1
				//			 2
				//			 3
				//			 4
				//			 5
				//			 6
				//新:
				//HashEntry:[0] [1]...
				//里面的值:  4
				//			 5
				//			 6
				//这里最后lastRun就是4 ,idx就是新数组的下标0
				HashEntry<K,V> lastRun = e;
				int lastIdx = idx;
				//找到第一个后续结点新的index不变的结点
				for (HashEntry<K,V> last = next;
				        last != null;
				        last = last.next) {
					int k = last.hash & sizeMask;
					if (k != lastIdx) {
						lastIdx = k;
						lastRun = last;
					}
				}
				//然后把4结点放到新数组中，这样4,5,6就都过去了
				newTable[lastIdx] = lastRun;
				// Clone remaining nodes
				//剩下的就是解决1,2,3了,遍历原HashEntry数组,直到等于4为止
				//这些结点采用头插法放到新HashEntry数组中
				for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
					V v = p.value;
					int h = p.hash;
					int k = h & sizeMask;
					HashEntry<K,V> n = newTable[k];//头插法
					newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
				}
			}
		}
	}
	//将待新加入的元素放到新数组(头插法)
	int nodeIndex = node.hash & sizeMask; // add the new node
	node.setNext(newTable[nodeIndex]);
	newTable[nodeIndex] = node;
	//segment的数组指到新数组
	table = newTable;
}

原HashEntry数组扩大一倍，然后遍历原HashEntry数组，找到某个结点lastRun，从这个结点开始往下，都会放到新HashEntry数组的某个槽下面。
接下来就是遍历剩下的数据，然后采用头插法，放到新数组中。最后就是将待新加入的结点，放到新数组中。

get操作

public V get(Object key) {
	Segment<K,V> s; // manually integrate access methods to reduce overhead
	HashEntry<K,V>[] tab;
	//key的hash值
	int h = hash(key);
	//计算出k所在的segment所在的内存地址
	long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
	//通过CAS操作获取segment,判断都不为null
	if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
	        (tab = s.table) != null) {
		//再通过CAS操作，获取的key所在的HashEntry[]数组的下标，获取到就返回，没有就返回null
		for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
		                        (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
		        e != null; e = e.next) {
			K k;
			if ((k = e.key) == key || (e.hash == h && key.equals(k)))
				return e.value;
		}
	}
	return null;
}

计算 hash 值，找到 segment 数组中的具体位置,使用Unsafe获取对应的Segment,根据 hash 找到数组中具体的位置,从链表头开始遍历整个链表（因为Hash可能会有碰撞，所以用一个链表保存），如果找到对应的key，则返回对应的value值，否则返回null。

注：get操作不需要锁，由于其中涉及到的共享变量都使用volatile修饰，volatile可以保证内存可见性，所以不会读取到过期数据。

remove操作

public V remove(Object key) {
	int hash = hash(key);
	//key的hash值，获取segment
	Segment<K,V> s = segmentForHash(hash);
	return s == null ? null : s.remove(key, hash, null);
}

final V remove(Object key, int hash, Object value) {
	//尝试获取segment锁
	if (!tryLock())
		//失败就自旋
		scanAndLock(key, hash);
	//执行到这里一定获取了segment锁
	V oldValue = null;
	try {
		//获取segment的HashEntry[]数组
		//获取key所在的下标，然后获取头结点
		HashEntry<K,V>[] tab = table;
		int index = (tab.length - 1) & hash;
		HashEntry<K,V> e = entryAt(tab, index);
		HashEntry<K,V> pred = null;
		while (e != null) {
			K k;
			HashEntry<K,V> next = e.next;
			//判断当前结点e是不是要删除的数据
			if ((k = e.key) == key ||
			        (e.hash == hash && key.equals(k))) {//key相同
				V v = e.value;
				//如果没有传value，或者value相同
				if (value == null || value == v || value.equals(v)) {
					if (pred == null)//要删除结点的前一个结点为null
						setEntryAt(tab, index, next);//直接赋值
					else
						pred.setNext(next);//直接将当前结点的前一个结点的next设置成当前结点的下一个结点。
					++modCount;
					--count;
					oldValue = v;
				}
				break;
			}
			//前结点不是要找的结点,遍历下一个
			pred = e;
			e = next;
		}
	}
	finally {
		unlock();
	}
	return oldValue;
}

找到key所在HashEntry[]数组的下标，然后遍历链表，找到结点。将当前结点的上一个结点的next设置成当前结点的下一个结点。

size操作

public int size() {
	final Segment<K,V>[] segments = this.segments;
	int size;
	boolean overflow; // // 是否溢出
	long sum;         // 存储本次循环过程中计算得到的modCount的值
	long last = 0L;   // 存储上一次遍历过程中计算得到的modCount的和
	int retries = -1; // first iteration isn't retry
	try {
		for (;;) {
			//判断retries是否等于RETRIES_BEFORE_LOCK(值为2)
			//也就是默认有两次的机会，是不加锁来求size的
			if (retries++ == RETRIES_BEFORE_LOCK) {
				for (int j = 0; j < segments.length; ++j)
					ensureSegment(j).lock(); // force creation
			}
			sum = 0L;
			size = 0;
			overflow = false;
			//遍历Segments[]数组获取里面的每一个segment，然后对modCount进行求和
			//这个for嵌套在for(;;)中，默认会执行两次，如果两次值相同，就返回
			//如果两次值不同，就进入到上面的if中，进行加锁。之后在进行求和
			for (int j = 0; j < segments.length; ++j) {
				Segment<K,V> seg = segmentAt(segments, j);
				if (seg != null) {
					sum += seg.modCount;
					int c = seg.count;
					if (c < 0 || (size += c) < 0)
						overflow = true;
				}
			}
			if (sum == last)
				break;
			last = sum;
		}
	}
	finally {
	    //由于只有在retries等于RETRIES_BEFORE_LOCK时才会执行强制加锁，并且由于是用的retries++，
        //所以强制加锁完毕后，retries的值是一定会大于RETRIES_BEFORE_LOCK的，
        //这样就防止正常遍历而没进行加锁时进行锁释放的情况
		if (retries > RETRIES_BEFORE_LOCK) {
			for (int j = 0; j < segments.length; ++j)
				segmentAt(segments, j).unlock();
		}
	}
	return overflow ? Integer.MAX_VALUE : size;
}

1. 先尝试RETRIES_BEFORE_LOCK次( 即2次 )不加锁的情况下，将segment[]数组中每个segment的count累加，同时也会将每个segment的modCount进行累加。如果两次不加锁的操作后，modCountSum值是一样的，这说明在这两次累加segmentcount的过程中ConcurrentHashMap没有发生结构性变化，那么就直接返回累加的count值;
2. 如果在两次累加segment的count操作期间ConcurrentHashMap发生了结构性改变，则会通过将所有的segment都加锁，然后重新进行count的累加操作。在完成count的累加操作后，释放所有的锁。最后返回累加的count值。
3. 如果累加的count值大于了Integer.MAX_VALUE，则返回Integer.MAX_VALUE。

---

ConcurrentHashMap-Jdk1.8

数据结构

Java7中ConcurrentHashMap是采用了数组+链表的数据结构。要知道链表的查找效率是低下的，其平均的查找时间是O(logn)，其中n是链表的长度。当链表较长时，查找可能会成为哈希表的性能瓶颈。

针对这个问题，Java8中对ConcurrentHashMap的数据结构进行了优化，采用了数组+链表+红黑树的数据结构。当数组中某个链表的长度超过一定的阈值之后，会将其转换成红黑树，以提高查找效率。当红黑树结点数少于一定阈值后，还能降红黑树逆退化成链表。下图是Java8 ConcurrentHashMap的数据结构示意图：

Java8中取消了Java7中的分段锁设计，而采用了 CAS + synchronized 来保证并发安全性。

重要属性

// 最大容量
private static final int MAXIMUM_CAPACITY = 1 << 30;
// 初始容量
private static final int DEFAULT_CAPACITY = 16;
// 数据最大长度
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 默认并发度
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
// 默认加载因子
private static final float LOAD_FACTOR = 0.75f;
// 链表转红黑树的阀值，大于8时
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转链表的阀值，小于等于6（tranfer时，lc、hc=0两个计数器分别++记录原bin、新binTreeNode数量，<=UNTREEIFY_THRESHOLD 则untreeify(lo)）。
// 【仅在扩容tranfer时才可能树转链表】
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
private static final int MIN_TRANSFER_STRIDE = 16;
private static int RESIZE_STAMP_BITS = 16;
// 2^15-1，help resize的最大线程数
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
// 32-16=16，sizeCtl中记录size大小的偏移量
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
static final int MOVED     = -1; // 表示正在转移
static final int TREEBIN   = -2; // 表示已经转换成树
static final int RESERVED  = -3; // hash for transient reservations
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
transient volatile Node<K,V>[] table;//默认没初始化的数组，用来保存元素
private transient volatile Node<K,V>[] nextTable;//转移的时候用的数组
// 可用处理器数量
static final int NCPU = Runtime.getRuntime().availableProcessors();

/**
 * 用来控制表初始化和扩容的，默认值为0，当在初始化的时候指定了大小，这会将这个大小保存在sizeCtl中，大小为数组的0.75
 * 正数或0代表hash表还没有被初始化，这个数值表示初始化或下一次进行扩容的大小
 * 当为负的时候，说明表正在初始化或扩容，
 *     -1表示初始化
 *     -(1+n) n:表示活动的扩容线程
 */
private transient volatile int sizeCtl;

重要类

Node-构成元素的基本类

最核心的内部类，它包装了key-value键值对，所有插入ConcurrentHashMap的数据都包装在这里面。它与HashMap中的定义很相似，但是有一些差别它对value和next属性设置了volatile同步锁(与JDK7的Segment相同)，它不允许调用setValue方法直接改变Node的value域，它增加了find方法辅助map.get()方法。

static class Node<K,V> implements Map.Entry<K,V> {
	final int hash;  //key的hash值
	final K key;     //key
	volatile V val;  //value
	volatile Node<K,V> next;  //表示链表中的下一个结点

	Node(int hash, K key, V val, Node<K,V> next) {
		this.hash = hash;
		this.key = key;
		this.val = val;
		this.next = next;
	}

	public final K getKey()       { return key; }
	public final V getValue()     { return val; }
	public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
	public final String toString(){ return key + "=" + val; }
	public final V setValue(V value) {
		throw new UnsupportedOperationException();
	}

	public final boolean equals(Object o) {
		Object k, v, u; Map.Entry<?,?> e;
		return ((o instanceof Map.Entry) &&
				(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
				(v = e.getValue()) != null &&
				(k == key || k.equals(key)) &&
				(v == (u = val) || v.equals(u)));
	}

	/**
	 * Virtualized support for map.get(); overridden in subclasses.
	 */
	Node<K,V> find(int h, Object k) {
		Node<K,V> e = this;
		if (k != null) {
			do {
				K ek;
				if (e.hash == h &&
					((ek = e.key) == k || (ek != null && k.equals(ek))))
					return e;
			} while ((e = e.next) != null);
		}
		return null;
	}
}

TreeNode-树结点类

树节点类，另外一个核心的数据结构。当链表长度过长的时候，会转换为TreeNode。
但是与HashMap不相同的是，它并不是直接转换为红黑树，而是把这些结点包装成TreeNode放在TreeBin对象中，由TreeBin完成对红黑树的包装。
而且TreeNode在ConcurrentHashMap继承自Node类，而并非HashMap中继承成自LinkedHashMap.Entry<K,V>类，也就是说TreeNode带有next指针，这样做的目的是方便基于TreeBin的访问。

static final class TreeNode<K,V> extends Node<K,V> {
	TreeNode<K,V> parent;  // red-black tree links
	TreeNode<K,V> left;
	TreeNode<K,V> right;
	TreeNode<K,V> prev;    // needed to unlink next upon deletion
	boolean red;

	TreeNode(int hash, K key, V val, Node<K,V> next,
			 TreeNode<K,V> parent) {
		super(hash, key, val, next);
		this.parent = parent;
	}

	Node<K,V> find(int h, Object k) {
		return findTreeNode(h, k, null);
	}

	/**
	 * Returns the TreeNode (or null if not found) for the given key
	 * starting at given root.
	 */
	final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
		if (k != null) {
			TreeNode<K,V> p = this;
			do  {
				int ph, dir; K pk; TreeNode<K,V> q;
				TreeNode<K,V> pl = p.left, pr = p.right;
				if ((ph = p.hash) > h)
					p = pl;
				else if (ph < h)
					p = pr;
				else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
					return p;
				else if (pl == null)
					p = pr;
				else if (pr == null)
					p = pl;
				else if ((kc != null ||
						  (kc = comparableClassFor(k)) != null) &&
						 (dir = compareComparables(kc, k, pk)) != 0)
					p = (dir < 0) ? pl : pr;
				else if ((q = pr.findTreeNode(h, k, kc)) != null)
					return q;
				else
					p = pl;
			} while (p != null);
		}
		return null;
	}
}

TreeBin-树的头结点

这个类并不负责包装用户的key、value信息，而是包装的很多TreeNode节点。它代替了TreeNode的根节点，也就是说在实际的ConcurrentHashMap“数组”中，存放的是TreeBin对象，而不是TreeNode对象，这是与HashMap的区别。另外这个类还带有了读写锁。在构造TreeBin节点时，仅仅指定了它的hash值为TREEBIN常量，这也就是个标识。

static final class TreeBin<K,V> extends Node<K,V> {
	TreeNode<K,V> root;
	volatile TreeNode<K,V> first;
	volatile Thread waiter;
	volatile int lockState;
	// values for lockState
	static final int WRITER = 1; // set while holding write lock
	static final int WAITER = 2; // set when waiting for write lock
	static final int READER = 4; // increment value for setting read lock
}

ForwardingNode-转移的时候放在头部的结点

一个用于连接两个table的节点类。它包含一个nextTable指针，用于指向下一张表。而且这个节点的key value next指针全部为null，它的hash值为-1. 这里面定义的find的方法是从nextTable里进行查询节点，而不是以自身为头节点进行查找。其中存储nextTable的引用。只有table发生扩容的时候，ForwardingNode才会发挥作用，作为一个占位符放在table中表示当前节点为null或则已经被移动。

static final class ForwardingNode<K,V> extends Node<K,V> {
	final Node<K,V>[] nextTable;
	ForwardingNode(Node<K,V>[] tab) {
		super(MOVED, null, null, null);
		this.nextTable = tab;
	}
}

3个原子操作

在ConcurrentHashMap中使用了unSafe方法，通过直接操作内存的方式来保证并发处理的安全性，使用的是硬件的安全机制。

/*
 * 用来返回节点数组的指定位置的节点的原子操作
 */
@SuppressWarnings("unchecked")
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
	return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}

/*
 * 利用CAS算法设置i位置上的Node节点（将c和table[i]比较，相同则插入v）。
 */
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
									Node<K,V> c, Node<K,V> v) {
	return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
/*
 * 设置节点位置的值，仅在上锁区被调用  
 */
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
	U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}

构造器

//空的构造
public ConcurrentHashMapDebug() {
}
//如果在实例化对象的时候指定了容量，则初始化sizeCtl
public ConcurrentHashMapDebug(int initialCapacity) {
	if (initialCapacity < 0)
		throw new IllegalArgumentException();
	int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
			   MAXIMUM_CAPACITY :
			   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
	this.sizeCtl = cap;
}
//当出入一个Map的时候，先设定sizeCtl为默认容量，在添加元素
public ConcurrentHashMapDebug(Map<? extends K, ? extends V> m) {
	this.sizeCtl = DEFAULT_CAPACITY;
	putAll(m);
}

在任何一个构造方法中，都没有对存储Map元素Node的table变量进行初始化。而是在第一次put操作的时候在进行初始化。

put操作

/*
 * 单纯的调用putVal方法，并且putVal的第三个参数设置为false
 * 当设置为false的时候表示这个value一定会设置
 * true的时候，只有当这个key的value为空的时候才会设置
 */
public V put(K key, V value) {
	return putVal(key, value, false);
}

/*
 * 当添加一对键值对的时候，首先会去判断保存这些键值对的数组是不是初始化了，
 * 如果没有的话就初始化数组
 * 然后通过计算hash值来确定放在数组的哪个位置
 * 如果这个位置为空则直接添加，如果不为空的话，则取出这个节点来
 * 如果取出来的节点的hash值是MOVED(-1)的话，则表示当前正在对这个数组进行扩容，复制到新的数组，则当前线程也去帮助复制
 * 最后一种情况就是，如果这个节点，不为空，也不在扩容，则通过synchronized来加锁，进行添加操作
 * 然后判断当前取出的节点位置存放的是链表还是树
 * 如果是链表的话，则遍历整个链表，取出来每个节点的key与要放的key进行比较，如果key相等，并且key的hash值也相等的话，
 * 则说明是同一个key，则新值替换旧值，否则的话则添加到链表的末尾
 * 如果是树的话，则调用putTreeVal方法把这个元素添加到树中去
 * 最后在添加完成之后，会判断在该节点处共有多少个节点（注意是添加前的个数），如果达到8个以上了的话，
 * 则调用treeifyBin方法来尝试将处的链表转为树，或者扩容数组
 */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    //K,V都不能为空，否则的话抛出异常
	if (key == null || value == null) throw new NullPointerException();
	//取得key的hash值
	int hash = spread(key.hashCode());
	//用来计算在这个结点总共有多少个元素，用来控制扩容或者转移树
	int binCount = 0;
	for (Node<K,V>[] tab = table;;) {
		Node<K,V> f; int n, i, fh;
		//如果数组为空或数组长度为0
		if (tab == null || (n = tab.length) == 0)
		    //第一次put的时候table没有初始化则初始化table
			tab = initTable();
		
		//找该 hash 值对应的数组下标，得到第一个节点 f
		else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
		
			//如果这个位置没有元素的话，则通过cas的方式尝试添加，注意这个时候是没有加锁的
			//创建一个Node添加到数组中，null表示的是下一个节点为空
			if (casTabAt(tab, i, null,
						 new Node<K,V>(hash, key, value, null)))
				break;                   // no lock when adding to empty bin
		}
		/*
		 * 如果检测到某个节点的hash值是MOVED，则表示正在进行数组扩张的数据复制阶段，
		 * 则当前线程也会参与去复制，通过允许多线程复制的功能，依此来减少数组的复制所带来的性能损失
		 */
		else if ((fh = f.hash) == MOVED)
		    //数据迁移
			tab = helpTransfer(tab, f);
		else {
		     /*
			  * 如果在这个位置有元素的话，就采用synchronized的方式加锁，
			  * 如果是链表的话(hash大于0)，就对这个链表的所有元素进行遍历，
			  * 如果找到了key和key的hash值都一样的节点，则把它的值替换掉；
			  * 如果没找到的话，则添加在链表的最后面
			  * 否则，是树的话，则调用putTreeVal方法添加到树中去
			  *  
			  * 在添加完之后，会对该节点上关联的的数目进行判断，
			  * 如果在8个以上的话，则会调用treeifyBin方法，来尝试转化为树，或者是扩容
			  */
			V oldVal = null;
			synchronized (f) {
				if (tabAt(tab, i) == f) {//再次取出要存储的位置的元素，跟前面取出来的比较
					if (fh >= 0) {//取出来的元素的hash值大于0说明是链表，当转换为树之后，hash值为-2
						//用于累加，记录链表长度
						binCount = 1;
						for (Node<K,V> e = f;; ++binCount) {//遍历这个链表
							K ek;
							//要存的元素的hash，key跟要存储的位置的节点的相同的时候，替换掉该节点的value即可
							if (e.hash == hash &&
								((ek = e.key) == key ||
								 (ek != null && key.equals(ek)))) {
								oldVal = e.val;
								//当使用putIfAbsent的时候，只有在这个key没有设置值的时候才设置
								if (!onlyIfAbsent)
									e.val = value;
								break;
							}
							Node<K,V> pred = e;
							//如果不是同样的hash，同样的key的时候，则判断该节点的下一个节点是否为空
							if ((e = e.next) == null) {
								//为空的话把这个要加入的节点设置为当前节点的下一个节点
								pred.next = new Node<K,V>(hash, key,
														  value, null);
								break;
							}
						}
					}
					else if (f instanceof TreeBin) {//表示已经转化成红黑树类型了
						Node<K,V> p;
						binCount = 2;
						//调用putTreeVal方法，将该元素添加到树中去
						if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
													   value)) != null) {
							oldVal = p.val;
							if (!onlyIfAbsent)
								p.val = value;
						}
					}
				}
			}
			//说明上面在做链表操作
			if (binCount != 0) {
			    //判断是否要将链表转成红黑树，临界值和HashMap一样，也是8
				if (binCount >= TREEIFY_THRESHOLD)
				    // 这个方法和 HashMap 中稍微有一点点不同，那就是它不是一定会进行红黑树转换，
                    // 如果当前数组的长度小于 64，那么会选择进行数组扩容，而不是转换为红黑树
					treeifyBin(tab, i);
				if (oldVal != null)
					return oldVal;
				break;
			}
		}
	}
	addCount(1L, binCount);
	return null;
}

initTable-数组初始化

/**
 * 初始化数组table，
 * 如果sizeCtl小于0，说明别的数组正在进行初始化，则让出执行权
 * 如果sizeCtl大于0的话，则初始化一个大小为sizeCtl的数组
 * 否则的话初始化一个默认大小(16)的数组
 * 然后设置sizeCtl的值为数组长度的3/4
 */
private final Node<K,V>[] initTable() {
	Node<K,V>[] tab; int sc;
	//第一次put的时候，table还没被初始化，进入while
	while ((tab = table) == null || tab.length == 0) {    
		//sizeCtl初始值为0，当小于0的时候表示在别的线程在初始化表或扩容
		if ((sc = sizeCtl) < 0)                            
			Thread.yield(); // lost initialization race; just spin
		//CAS一下，将sizectl设置为-1，代表抢到了锁
		else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
			try {
				if ((tab = table) == null || tab.length == 0) {
				    //指定了大小的时候就创建指定大小的Node数组，否则创建默认大小(16)的Node数组
					int n = (sc > 0) ? sc : DEFAULT_CAPACITY; 
					//初始化数组，长度为16，或初始化时提供的长度
					@SuppressWarnings("unchecked")
					Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
					 // 将这个数组赋值给 table，table 是 volatile 的
					table = tab = nt;
					 // 如果 n 为 16 的话，那么这里 sc = 12，其实就是 0.75 * n
					sc = n - (n >>> 2);
				}
			} finally {
			    //初始化后，sizeCtl长度为数组长度的3/4
				sizeCtl = sc;            
			}
			break;
		}
	}
	return tab;
}

主要就是初始化一个合适大小的数组，然后会设置 sizeCtl。初始化方法中的并发问题是通过对 sizeCtl 进行一个 CAS 操作来控制的。

treeifyBin-链表转红黑树

private final void treeifyBin(Node<K,V>[] tab, int index) {
	Node<K,V> b; int n, sc;
	if (tab != null) {
	    // MIN_TREEIFY_CAPACITY 为 64
        // 所以，如果数组长度小于 64 的时候，其实也就是 32 或者 16 或者更小的时候，会进行数组扩容
		if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
			tryPresize(n << 1);//数组扩容
		// b是头结点	
		else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
			synchronized (b) {
				if (tabAt(tab, index) == b) {
				    // 下面就是遍历链表，建立一颗红黑树
					TreeNode<K,V> hd = null, tl = null;//hd 树的头结点
					for (Node<K,V> e = b; e != null; e = e.next) {
						TreeNode<K,V> p =
							new TreeNode<K,V>(e.hash, e.key, e.val,
											  null, null);
						//把Node组成的链表，转化为TreeNode的链表，头结点任然放在相同的位置					  
						if ((p.prev = tl) == null)
							hd = p;//设置head
						else
							tl.next = p;
						tl = p;
					}
					 // 将红黑树设置到数组相应位置中
					setTabAt(tab, index, new TreeBin<K,V>(hd));
				}
			}
		}
	}
}

treeifyBin 不一定就会进行红黑树转换，也可能是仅仅做数组扩容。

tryPresize-扩容

private final void tryPresize(int size) {
    // c：size 的 1.5 倍，再加 1，再往上取最近的 2 的 n 次方。
	// 如果给定的大小大于等于数组容量的一半，则直接使用最大容量，否则使用tableSizeFor算出来
	int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
		tableSizeFor(size + (size >>> 1) + 1);
	int sc;
	while ((sc = sizeCtl) >= 0) {
		Node<K,V>[] tab = table; int n;
		/*
		 * 如果数组table还没有被初始化，则初始化一个大小为sizeCtrl和刚刚算出来的c中较大的一个大小的数组
		 * 初始化的时候，设置sizeCtrl为-1，初始化完成之后把sizeCtrl设置为数组长度的3/4
		 * 为什么要在扩容的地方来初始化数组呢？这是因为如果第一次put的时候不是put单个元素，
		 * 而是调用putAll方法直接put一个map的话，在putALl方法中没有调用initTable方法去初始化table，
		 * 而是直接调用了tryPresize方法，所以这里需要做一个是不是需要初始化table的判断
		 */
		if (tab == null || (n = tab.length) == 0) {
			n = (sc > c) ? sc : c;
			//初始化tab的时候，把sizeCtl设为-1
			if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
				try {
					if (table == tab) {
						@SuppressWarnings("unchecked")
						Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
						table = nt;
						sc = n - (n >>> 2);
					}
				} finally {
					sizeCtl = sc;
				}
			}
		}
		/*
		 * 一直扩容到的c小于等于sizeCtl或者数组长度大于最大长度的时候，则退出
		 * 所以在一次扩容之后，不是原来长度的两倍，而是2的n次方倍
		 */
		else if (c <= sc || n >= MAXIMUM_CAPACITY)
			break;
		else if (tab == table) {
			int rs = resizeStamp(n);
			/*
			 * 如果正在扩容Table的话，则帮助扩容
			 * 否则的话，开始新的扩容
			 * 在transfer操作，将第一个参数的table中的元素，移动到第二个元素的table中去，
			 * 虽然此时第二个参数设置的是null，但是，在transfer方法中，当第二个参数为null的时候，
			 * 会创建一个两倍大小的table
			 */
			if (sc < 0) {
				Node<K,V>[] nt;
				if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
					sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
					transferIndex <= 0)
					break;
				/*
				 * transfer的线程数加一,该线程将进行transfer的帮忙
				 * 在transfer的时候，sc表示在transfer工作的线程数
				 */	
				if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
					transfer(tab, nt);
			}
			 /*
			  * 没有在初始化或扩容，则开始扩容
			  */
			else if (U.compareAndSwapInt(this, SIZECTL, sc,
										 (rs << RESIZE_STAMP_SHIFT) + 2))
				transfer(tab, null);
		}
	}
}

这个方法的核心在于 sizeCtl 值的操作，首先将其设置为一个负数，然后执行 transfer(tab, null)，再下一个循环将 sizeCtl 加 1，并执行 transfer(tab, nt)，之后可能是继续 sizeCtl 加 1，并执行 transfer(tab, nt)。所以，可能的操作就是执行 1 次 transfer(tab, null) +多次 transfer(tab, nt)，这里怎么结束循环的需要看完 transfer 源码才清楚。

transfer-数据迁移

/**
 * 把数组中的节点复制到新的数组的相同位置，或者移动到扩张部分的相同位置
 * 在这里首先会计算一个步长，表示一个线程处理的数组长度，用来控制对CPU的使用，
 * 每个CPU最少处理16个长度的数组元素,也就是说，如果一个数组的长度只有16，那只有一个线程会对其进行扩容的复制移动操作
 * 扩容的时候会一直遍历，知道复制完所有节点，没处理一个节点的时候会在链表的头部设置一个fwd节点，这样其他线程就会跳过他，
 * 复制后在新数组中的链表不是绝对的反序的
 */
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
	int n = tab.length, stride;
	// stride 在单核下直接等于 n，多核模式下为 (n>>>3)/NCPU，最小值是 16
    // stride 可以理解为”步长“，有 n 个位置是需要进行迁移的，
    //   将这 n 个任务分为多个任务包，每个任务包有 stride 个任务
	if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
		stride = MIN_TRANSFER_STRIDE; // subdivide range
	/*
	 * 如果复制的目标nextTab为null的话，则初始化一个table两倍长的nextTab
	 * 此时nextTable被设置值了(在初始情况下是为null的)
	 * 因为如果有一个线程开始了表的扩张的时候，其他线程也会进来帮忙扩张，
	 * 而只是第一个开始扩张的线程需要初始化下目标数组
	 */
	if (nextTab == null) {            // initiating
		try {
		    //容量翻倍
			@SuppressWarnings("unchecked")
			Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
			nextTab = nt;
		} catch (Throwable ex) {      // try to cope with OOME
			sizeCtl = Integer.MAX_VALUE;
			return;
		}
		// nextTable 是 ConcurrentHashMap 中的属性
		nextTable = nextTab;
		// transferIndex 也是 ConcurrentHashMap 的属性，用于控制迁移的位置
		transferIndex = n;
	}
	int nextn = nextTab.length;
	// ForwardingNode-->正在被迁移的 Node
    // 这个构造方法会生成一个Node，key、value 和 next 都为 null，关键是 hash 为 MOVED
    // 后面会看到，原数组中位置 i 处的节点完成迁移工作后，
    // 就会将位置 i 处设置为这个 ForwardingNode，用来告诉其他线程该位置已经处理过了
    // 所以它其实相当于是一个标志。
	ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
	// advance 指的是做完了一个位置的迁移工作，可以准备做下一个位置的了
	boolean advance = true;
	boolean finishing = false; // to ensure sweep(清扫) before committing nextTab,在完成之前重新在扫描一遍数组，看看有没完成的没
	// i 是位置索引，bound 是边界，注意是从后往前
	for (int i = 0, bound = 0;;) {
		Node<K,V> f; int fh;
		// advance 为 true 表示可以进行下一个位置的迁移了
        // 简单理解：i 指向了 transferIndex，bound 指向了 transferIndex-stride
		while (advance) {
			int nextIndex, nextBound;
			if (--i >= bound || finishing)
				advance = false;
			// 将 transferIndex 值赋给 nextIndex
            // 这里 transferIndex 一旦小于等于 0，说明原数组的所有位置都有相应的线程去处理了	
			else if ((nextIndex = transferIndex) <= 0) {
				i = -1;
				advance = false;
			}
			// nextBound 是这次迁移任务的边界，注意，是从后往前
			else if (U.compareAndSwapInt
					 (this, TRANSFERINDEX, nextIndex,
					  nextBound = (nextIndex > stride ?
								   nextIndex - stride : 0))) {
				bound = nextBound;
				i = nextIndex - 1;
				advance = false;
			}
		}
		if (i < 0 || i >= n || i + n >= nextn) {
			int sc;
			// 所有的迁移操作已经完成
			if (finishing) {
				nextTable = null;
				// 将新的 nextTab 赋值给 table 属性，完成迁移
				table = nextTab;
				// 重新计算 sizeCtl：n 是原数组长度，所以 sizeCtl 得出的值将是新数组长度的 0.75 倍
				sizeCtl = (n << 1) - (n >>> 1);
				return;
			}
			// sizeCtl 在迁移前会设置为 (rs << RESIZE_STAMP_SHIFT) + 2
            // 然后，每有一个线程参与迁移就会将 sizeCtl 加 1，
            // 这里使用 CAS 操作对 sizeCtl 进行减 1，代表做完了属于自己的任务
			if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
				if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
					return;
				// 到这里，说明 (sc - 2) == resizeStamp(n) << RESIZE_STAMP_SHIFT，
                // 也就是说，所有的迁移任务都做完了，也就会进入到上面的 if(finishing){} 分支了	
				finishing = advance = true;
				i = n; // recheck before commit
			}
		}
		// 如果位置 i 处是空的，没有任何节点，那么放入刚刚初始化的 ForwardingNode ”空节点“
		else if ((f = tabAt(tab, i)) == null)
			advance = casTabAt(tab, i, null, fwd);
		// 该位置处是一个 ForwardingNode，代表该位置已经迁移过了	
		else if ((fh = f.hash) == MOVED)
			advance = true; // already processed
		else {
		    // 对数组该位置处的结点加锁，开始处理数组该位置处的迁移工作
			synchronized (f) {
				if (tabAt(tab, i) == f) {
					Node<K,V> ln, hn;
					// 头结点的 hash 大于 0，说明是链表的 Node 节点
					if (fh >= 0) {
                        // 需要将链表一分为二，找到原链表中的 lastRun，
						// 然后 lastRun 及其之后的节点是一起进行迁移的lastRun 之前的节点需要进行克隆，然后分到两个链表中
						int runBit = fh & n;
						Node<K,V> lastRun = f;
						/*
						 * lastRun 表示的是需要复制的最后一个节点
						 * 每当新节点的hash&n -> b 发生变化的时候，就把runBit设置为这个结果b
						 * 这样for循环之后，runBit的值就是最后不变的hash&n的值
						 * 而lastRun的值就是最后一次导致hash&n 发生变化的节点(假设为p节点)
						 * 为什么要这么做呢？因为p节点后面的节点的hash&n 值跟p节点是一样的，
						 * 所以在复制到新的table的时候，它肯定还是跟p节点在同一个位置
						 * 在复制完p节点之后，p节点的next节点还是指向它原来的节点，就不需要进行复制了，自己就被带过去了
						 * 这也就导致了一个问题就是复制后的链表的顺序并不一定是原来的倒序
						 */
						for (Node<K,V> p = f.next; p != null; p = p.next) {
							int b = p.hash & n;  //n的值为扩张前的数组的长度
							if (b != runBit) {
								runBit = b;
								lastRun = p;
							}
						}
						if (runBit == 0) {
							ln = lastRun;
							hn = null;
						}
						else {
							hn = lastRun;
							ln = null;
						}
						/*
						 * 构造两个链表，顺序大部分和原来是反的
						 * 分别放到原来的位置和新增加的长度的相同位置(i/n+i)
						 */
						for (Node<K,V> p = f; p != lastRun; p = p.next) {
							int ph = p.hash; K pk = p.key; V pv = p.val;
							if ((ph & n) == 0)
							    /*
								 * 假设runBit的值为0，
								 * 则第一次进入这个设置的时候相当于把旧的序列的最后一次发生hash变化的节点(该节点后面可能还有hash计算后同为0的节点)设置到旧的table的第一个hash计算后为0的节点下一个节点
								 * 并且把自己返回，然后在下次进来的时候把它自己设置为后面节点的下一个节点
								 */
								ln = new Node<K,V>(ph, pk, pv, ln);
							else
							    /*
								 * 假设runBit的值不为0，
								 * 则第一次进入这个设置的时候相当于把旧的序列的最后一次发生hash变化的节点(该节点后面可能还有hash计算后同不为0的节点)设置到旧的table的第一个hash计算后不为0的节点下一个节点
								 * 并且把自己返回，然后在下次进来的时候把它自己设置为后面节点的下一个节点
								 */
								hn = new Node<K,V>(ph, pk, pv, hn);
						}
						// 其中的一个链表放在新数组的位置 i
						setTabAt(nextTab, i, ln);
					   // 另一个链表放在新数组的位置 i+n	
						setTabAt(nextTab, i + n, hn);
						// 将原数组该位置处设置为 fwd，代表该位置已经处理完毕，
                        // 其他线程一旦看到该位置的 hash 值为 MOVED，就不会进行迁移了
						setTabAt(tab, i, fwd);
						// advance 设置为 true，代表该位置已经迁移完毕
						advance = true;
					}
					else if (f instanceof TreeBin) {
					     // 红黑树的迁移
						TreeBin<K,V> t = (TreeBin<K,V>)f;
						TreeNode<K,V> lo = null, loTail = null;
						TreeNode<K,V> hi = null, hiTail = null;
						int lc = 0, hc = 0;
						for (Node<K,V> e = t.first; e != null; e = e.next) {
							int h = e.hash;
							TreeNode<K,V> p = new TreeNode<K,V>
								(h, e.key, e.val, null, null);
							if ((h & n) == 0) {
								if ((p.prev = loTail) == null)
									lo = p;
								else
									loTail.next = p;
								loTail = p;
								++lc;
							}
							else {
								if ((p.prev = hiTail) == null)
									hi = p;
								else
									hiTail.next = p;
								hiTail = p;
								++hc;
							}
						}
						// 如果一分为二后，节点数≤6，那么将红黑树转换回链表
						ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
							(hc != 0) ? new TreeBin<K,V>(lo) : t;
						hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
							(lc != 0) ? new TreeBin<K,V>(hi) : t;
						// 将ln放置在新数组的位置i	
						setTabAt(nextTab, i, ln);
						// 将hn放置在新数组的位置i+n
						setTabAt(nextTab, i + n, hn);
						//将原数组该位置处设置为 fwd，代表该位置已经处理完毕，
                        //其他线程一旦看到该位置的 hash 值为 MOVED，就不会进行迁移了
						setTabAt(tab, i, fwd);
						// advance 设置为 true，代表该位置已经迁移完毕
						advance = true;
					}
				}
			}
		}
	}
}

此方法支持多线程执行，外围调用此方法的时候，会保证第一个发起数据迁移的线程，nextTab 参数为 null，之后再调用此方法的时候，nextTab 不会为 null。

先理解下并发操作的机制。原数组长度为 n，所以我们有 n 个迁移任务，让每个线程每次负责一个小任务是最简单的，每做完一个任务再检测是否有其他没做完的任务，帮助迁移就可以了，而 Doug Lea 使用了一个 stride，简单理解就是步长，每个线程每次负责迁移其中的一部分，如每次迁移 16 个小任务。所以，我们就需要一个全局的调度者来安排哪个线程执行哪几个任务，这个就是属性 transferIndex 的作用。

第一个发起数据迁移的线程会将 transferIndex 指向原数组最后的位置，然后从后往前的 stride 个任务属于第一个线程，然后将 transferIndex 指向新的位置，再往前的 stride 个任务属于第二个线程，依此类推。当然，这里说的第二个线程不是真的一定指代了第二个线程，也可以是同一个线程，这个读者应该能理解吧。其实就是将一个大的迁移任务分为了一个个任务包。

putTreeVal-插入树结点

final TreeNode<K,V> putTreeVal(int h, K k, V v) {
  Class<?> kc = null;
  boolean searched = false;
  for (TreeNode<K,V> p = root;;) {
      int dir, ph; K pk;
      if (p == null) {
          // 当前桶为空，则直接创建一个新的节点
          first = root = new TreeNode<K,V>(h, k, v, null, null);
          break;
      }
      else if ((ph = p.hash) > h)
          // hash值大于当前key的，在左子树
          dir = -1;
      else if (ph < h)
          // hash值小于当前key的，在右子树
          dir = 1;
      else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
          // 等于，则比较key是否相等
          return p;
      else if ((kc == null &&
                (kc = comparableClassFor(k)) == null) ||
               (dir = compareComparables(kc, k, pk)) == 0) {
        // 如果hash值相等，那么就比较下是否是String或者实现了Comparable接口
        // 如果等出现二次碰撞，则左右子树都搜索
          if (!searched) {
              TreeNode<K,V> q, ch;
              searched = true;
              // 找到对应的节点
              if (((ch = p.left) != null &&
                   (q = ch.findTreeNode(h, k, kc)) != null) ||
                  ((ch = p.right) != null &&
                   (q = ch.findTreeNode(h, k, kc)) != null))
                  // 找到直接返回即可
                  return q;
          }
          // 假如没有找到，则根据类名、System.identityHashCode比较来确定到底放在左右哪边
          dir = tieBreakOrder(k, pk);
      }

      TreeNode<K,V> xp = p;
      // 根据比较的大小dir来确定插入左子树还是右子树
      if ((p = (dir <= 0) ? p.left : p.right) == null) {
          TreeNode<K,V> x, f = first;
          first = x = new TreeNode<K,V>(h, k, v, f, xp);
          if (f != null)
              f.prev = x;
          if (dir <= 0) // <=0 左子树
              xp.left = x;
          else // >0 右子树
              xp.right = x;
          if (!xp.red)
              x.red = true;
          else {
              // 加锁，调整平衡
              lockRoot();
              try {
                  root = balanceInsertion(root, x);
              } finally {
                  unlockRoot();
              }
          }
          break;
      }
  }
  assert checkInvariants(root);
  return null;
}

// 多次冲突碰撞之后，就用此来决定谁大谁小，以区分在左还是在右子树上
static int tieBreakOrder(Object a, Object b) {
  int d;
  if (a == null || b == null ||
      (d = a.getClass().getName().
       compareTo(b.getClass().getName())) == 0)
      d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
           -1 : 1);
  return d;
}

get操作

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        // 判断头结点是否就是我们需要的节点
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        // 如果头结点的 hash 小于 0，说明 正在扩容，或者该位置是红黑树
        else if (eh < 0)
            // 参考 ForwardingNode.find(int h, Object k) 和 TreeBin.find(int h, Object k)
            return (p = e.find(h, key)) != null ? p.val : null;

        // 遍历链表
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

1. 计算 hash 值;
2. 根据 hash 值找到数组对应位置: (n - 1) & h;
3. 根据该位置处结点性质进行相应查找
   1. 如果该位置为 null，那么直接返回 null 就可以了;
   2. 如果该位置处的节点刚好就是我们需要的，返回该节点的值即可;
   3. 如果该位置节点的 hash 值小于 0，说明正在扩容，或者是红黑树;
   4. 如果以上 3 条都不满足，那就是链表，进行遍历比对即可;