Java集合Map源码解读

# Java集合Map源码解读

# 概述

这篇文章会简单得阅读一下Java集合中关于Map的几个主要实现：HashMap、Hashtable、ConcurrentHashMap的源码，源码的阅读基于JDK 1.7/1.8，重点是了解他们各自的底层结构以及之间的区别。

这里简单总结一下他们之间的底层结构以及之间区别，后面阅读源码时可以带着目的去阅读。

# HashMap与Hashtable的区别

都是无序存储、唯一的key值，value可以重复。
底层数据结构：HashMap在JDK 1.7 之前底层采用的是链表散列（数组+链表），而到JDK 1.8之后，主要在解决哈希冲突发生了较大变化（看下面的源码），并且引入了红黑树：当链表长度大于阈值（默认8）并且数组长度大于64，这个时候会将链表转换为红黑树，以减少搜索时间。而Hashtable没有这种机制。
线程是否安全：HashMap不是线程安全的，如果在并发操作可能会抛出"concurrentModificationException"，HashTable是线程安全的，内部的方法基本被synchronized修饰。
Null key和Null value的处理不同：HashMap可以存储Null的key-value，而Hashtable不可以保存Null的key-value，否则会抛出"NullPointerException"。
初始化容量以及扩容机制不同：
- HashMap分两种情况：如果创建时不指定初始容量，HashMap 默认的初始化⼤⼩为16，之后每次扩容变为原来的 2 倍；Hashtable 默认的初始⼤⼩为11，之后每次扩容变为原来的2n+1。如果创建时指定初始容量，HashMap 会将其扩充为 2 的幂次⽅⼤⼩（主要是为tableSizeFor⽅法提供保证，详见源码）。也就是说 HashMap 的容量始终为2 的幂次⽅⼤⼩。
- 而Hashtable则会直接使⽤你给定的⼤⼩。

如果在面试中能够回答出上诉内容，已经是非常不错了，说明基础很扎实。当然上面的区别的基于JDK 8的背景，现在Java的发展很快，很难保证后续这一块还会不会有变化。此外，有些面试官还喜欢将HashMap与HashSet进行对比，这里我就不详细说了，感兴趣的可以网上搜索相关文章，因为我是打算将Set另起一篇章去说。

# Hashtable与ConcurrentHashMap区别

如果面试中被问了这个问题，大多数是为了考察两者实现线程安全方式的区别。此外，也有可能会问到HashMap的多线程死循环（JDK1.7以及之前）问题，但这不是本文的重点，感兴趣的可以阅读这篇文章 (opens new window)，总的来说，并发情况下推荐使用ConcurrentHashMap。

底层数据结构：
- Hashtable底层采用的数据结构类似JDK1.7之前的HashMap，也就是数组+链表。
- ConcurrentHashMap在JDK 1.7以及之前，底层采用的是分段数组（Segment数组+HashEntry数组）+链表，JDK 1.8之后也同HashMap一样发生了变化，底层采用了数组（Node数组）+链表/红黑树，相比JDK 1.7，取消了 Segment 分段锁，而是采用CAS和synchronized保证并发安全。（更详细见下文源码分析）
实现线程安全方式不同：
- Hashtable使用synchronized保证线程安全，这是个重量级锁，并发效率并不会很高。例如，当⼀个线程访问同步⽅法时，其他线程访问同步⽅法，可能会进⼊阻塞或轮询状态。
- ConcurrentHashMap在JDK 1.7以及之前采用的是Segment分段锁实现并发安全，即对数组进⾏了分割分段( Segment )，每个分段一把锁，多线程访问容器⾥不同数据段的数据，就不会存在锁竞争，提⾼并发访问率；在JDK 1.8之后进一步提高并发效率，废弃了Segment分段锁，引入Node数组+链表/红黑树数据结构，使用synchronized和CAS机制来达到并发安全（在JDK1.6后对synchronized做了很多优化，锁升级等）。

关于这两者实现线程安全对方式，通常在面试中会经常被问到，如果对于上述的某些概念觉得比较抽象，可以参阅下文的源码阅读配图。

再次说明，以下所有源码如果不是特殊声明，主要来源于JDK 1.7/1.8。

# HashMap源码解读

HashMap类继承结构体系如上，继承了AbstractMap，同Java集合框架一样AbstractMap是一个模版，内部封装了很多unmodifiable map的方法，如果我们需要自定义一个Map通常继承这个类即可。

# 底层实现

# JDK 1.7及之前

在JDK 1.7及之前，HashMap的底层数据结构是链表散列（数组+链表）。

/**
* 哈希表，根据需要调整大小。长度必须总是2的幂。（数组）
*/
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

/**
* 哈希表元素（链表）
*/
static class Entry<K,V> implements Map.Entry<K,V> {
  final K key;
  V value;
  Entry<K,V> next;
  int hash;
  
  // ......
}

核心处理流程：HashMap 通过 key 的 hashCode 经过hash扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置index（n指数组的⻓度），如果当前位置存在元素的话，就判断该元素与要存⼊的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

扰动函数：也就是HashMap的hash方法，目的是为了减少碰撞。
拉链法：指数组、链表相结合，简单来说就是。创建⼀个链表数组，数组每个元素就是⼀个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
(n - 1) & hash：indexFor方法核心，数组下标的计算方法。HashMap 的⻓度之所以规定为2的幂次⽅，主要原因出于效率的考虑。一方面是因为取余(%)操作中如果除数是2的幂次则等价于与其除数减⼀的与(&)操作，也就是说当lenght=2的 n 次⽅，则hash % length == hash & (length-1)。另一方面，&操作相对于%操作运算效率更高。

以put方法为例：HashMap添加一个元素，可能会触发初始化容量或者扩容操作，这里放到后面扩容机制讲。这里关注HashMap是怎么存放k-v以及处理hash冲突的。

/**
* 将指定的值与此映射中的指定键关联。如果映射之前包含键的映射，则替换旧值。
*/
public V put(K key, V value) {
  // 如果是空数组，进行扩容初始化（后面详细说）
  if (table == EMPTY_TABLE) {
    inflateTable(threshold);
  }
  // hashTable是可以存储key或value为null值的
  if (key == null)
    // 与下面相似，这里不细说。（不会获取hash、index值，遍历table[0]链表，判断key为null）
    return putForNullKey(value);
  // 重点一，经过扰动函数，获取key的hash值
  int hash = hash(key);
  // 重点二，根据hash值，获取数组下标，其实就一行代码 return (n - 1) & hash
  int i = indexFor(hash, table.length);
  // 重点三，遍历table[i]链表，判断当前元素与要存⼊的元素的 hash 值以及 key 是否相同
  for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    Object k;
    // 相同则覆盖，返回oldValue
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
      V oldValue = e.value;
      e.value = value;
      e.recordAccess(this);
      return oldValue;
    }
  }
  
  // 线程不安全的，ConcurrentModificationException
  modCount++;
  // 走到这里，说明需要添加节点，该方法还会判断是否需要扩容
  addEntry(hash, key, value, i);
  // 添加节点成功返回的是null
  return null;
}

# JDK 1.8及以后

在JDK 1.8及以后，底层数据结构发生了些许变化，例如使用了Node链表，当然对应的put方法也发生了变化，但总的来说，变化较大的是在解决哈希冲突上：首先在链表的处理上引入了红黑树，其次hash扰动函数效率更高。

先看一下简单的hash扰动函数：官方注释对hash进行了一个解释，我这里简单总结就是两点：

防止低质量的hash函数，目的是减少冲突
Null key总是映射到散列0，即数组索引为0.

// 1.7
final int hash(Object k) {
  // 与实例关联的随机值，默认为0
  int h = hashSeed;
  if (0 != h && k instanceof String) {
    return sun.misc.Hashing.stringHash32((String) k);
  }

  h ^= k.hashCode();

  // 扰动了4次，在默认负载因子下大约为8
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
}

// 1.8 
static final int hash(Object key) {
  int h;
   // 扰动1次，效率高了很多
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

看完了hash扰动，再回过头看看底层数据结构变化以及put方法的变化：

// 在使用的时候初始化，同样是2的幂次方，具体区别 后面扩容机制说
transient Node<K,V>[] table;

/**
* 1.8 之后改为了Node链表
*/
static class Node<K,V> implements Map.Entry<K,V> {
  final int hash;
  final K key;
  V value;
  Node<K,V> next;
  // ......
}

/**
* 1.8 引入的红黑树，注意它也是LinkedHashMap的子类
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<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;
  // ......
}

关于put的方法，比1.7复杂了一点，主要是调用了putVal方法，思路其实与1.7大相径庭，感兴趣可以阅读下面的解析：

/**
* Map的put方法实现
* hash - key的hash值
* key - 键、value - 值
* onlyIfAbsent - 是否改变现有值（代码是!操作） ，put方法为false
* Evict - 创建模式，如果为false，表示table处于创建模式。put方法为true
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
  Node<K,V>[] tab; Node<K,V> p; int n, i;
  // 如果table为null或者空，进行resize初始化，详细放到扩容机制说
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  // 定位到数组index后，发现是元素是null，创建Node链表
  if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  // 否则处理hash冲突
  else {
    Node<K,V> e; K k;
    // 分支一：判断是否存在相同k（node），如果相同进行一个 e = p 赋值操作
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      e = p;
    // 分支二：如果是红黑树结点，那就使用putTreeVal，涉及到一些算法这里不展开描述
    else if (p instanceof TreeNode)
      e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    // 分支三：这里主要是遍历链表，进行追加操作
    else {
      for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
          p.next = newNode(hash, key, value, null);
          // 重点！！！TREEIFY_THRESHOLD = 8，如果链表长度大于8，将会尝试转换为红黑树
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
          break;
        }
        // 相同key，直接break
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        p = e;
      }
    }
    // e不为空，说明map中已经存在了这个key，根据onlyIfAbsent判断要不要覆盖，默认的put方法会覆盖
    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      // 如果onlyIfAbsent为false或者oldValue为null，会进行一个覆盖
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      // LinkedHashMap（红黑树）回调函数：将节点移动到最后
      afterNodeAccess(e);
      return oldValue;
    }
  }
  // 修改统计，并发异常控制
  ++modCount;
  // 如果添加完元素后，size 大于 扩容阈值 ，进行扩容（原容量 * 负载因子【0.75】)。resize放到扩容机制统一说
  if (++size > threshold)
    resize();
  // LinkedHashMap（红黑树）回调函数：可能删除老大
  afterNodeInsertion(evict);
  return null;
}

前面说过：当链表长度大于阈值（默认8）并且数组长度大于64，这个时候会将链表转换为红黑树，以减少搜索时间。由put的源码分支三解析可知大于阈值8成立，另一个条件数组长度大于64其实是在treeifyBin方法。

/**
* 可以将链表转红黑树的table最小表容量(树化阈值)。
* 应至少为4 * TREEIFY_THRESHOLD(8)，以避免调整大小和树化阈值之间的冲突。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 除非table数组太小（不够64），否则将转换为红黑树
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
  int n, index; Node<K,V> e;
  // 如果数组为空或者数组长度< 64, 这里是使用resize, 优先对数组扩容
  if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();
  // 否则，就是对链表进行树化操作
  else if ((e = tab[index = (n - 1) & hash]) != null) {
    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);
  }
}

关于HashMap的底层原理其实差不多就这些了，总结就不再赘述，可以自己翻看前面总结的内容。

# 扩容机制

关于扩容机制，由于1.7和1.8变化不大，拿简单的1.7源码进行解读。

# 构造函数

从默认构造函数看起：

/**
* 使用默认的初始容量(16)和默认的加载因子(0.75)构造一个空的HashMap。
*/
public HashMap() {
  // DEFAULT_INITIAL_CAPACITY = 16， DEFAULT_LOAD_FACTOR = 0.75
  this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

/**
* 构造一个带有指定初始容量和默认负载因子(0.75)的空HashMap。
*/
public HashMap(int initialCapacity) {
  this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
* 构造对象核心方法
*/
public HashMap(int initialCapacity, float loadFactor) {
  // 初始容量 < 0 ，肯定抛Exception，没啥好说的
  if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal initial capacity: " +
                                       initialCapacity);
  // 最大容量为 1 << 30
  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;
  // 这个其实是子类（例如LinkedHashMap）初始化钩子，在HashMap是个空函数，啥也没有
  init();
}

从构造函数可以看的出来，其实在创建完一个HashMap对象的时刻，都是空HashMap（初始化加载因子和扩容阈值）。

# 初始化数组

那么是什么时候，才去申请内存空间，创建底层的数组？如果你对上面的1.7的put源码还有印象，答案很明显：在第一次调用put方法的时候才对数组初始化，调用的inflateTable方法源码如下：

/**
* 扩大哈希表（数组）
*/
private void inflateTable(int toSize) {
  // 保证初始容量必须为2的幂次方，底层调用了Integer.highestOneBit方法（1.8是tableSizeFor方法）
  // 前面提到过是为了保证indexFor的高效性，即 h & (length-1);
  int capacity = roundUpToPowerOf2(toSize);
  // 更新扩容阈值（比如，默认构造器capacity=16，执行完之后 阈值为 16 * 0.75 截断取整）
  threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
  // 这里才初始化了Entry数组
  table = new Entry[capacity];
  // 延时初始化哈希掩码值
  initHashSeedAsNeeded(capacity);
}

至此，我们可以对前面概述中的结论进行一个完善：在默认初始化一个HashMap对象时，是个空HashMap并没创建table数组，仅仅初始化了加载因子和扩容阈值（指定容量）。当第一次进行put操作的时候，会对table数组进行一个初始化，默认的初始化⼤⼩为16**，如果创建时指定初始容量，HashMap 会将其扩充为2 的幂次⽅⼤⼩**。

# 扩容resize

初始化讲完了，下面再看看HashMap是如何扩容的，扩容判断主要发生在put操作需要addEntry的时候，1.7源码如下：

void addEntry(int hash, K key, V value, int bucketIndex) {
  // 如果size >= 扩容阈值（容量*0.75）并且 数组元素不为空 ，进行扩容
  if ((size >= threshold) && (null != table[bucketIndex])) {
    // 默认扩容两倍，resize是核心方法
    resize(2 * table.length);
    hash = (null != key) ? hash(key) : 0;
    bucketIndex = indexFor(hash, table.length);
  }

  createEntry(hash, key, value, bucketIndex);
}

/**
* 扩容核心方法 resize
*/
void resize(int newCapacity) {
  Entry[] oldTable = table;
  int oldCapacity = oldTable.length;
  if (oldCapacity == MAXIMUM_CAPACITY) {
    threshold = Integer.MAX_VALUE;
    return;
  }
  // 创建了新哈希表（数组）
  Entry[] newTable = new Entry[newCapacity];
  // 进行一个拷贝（for循环）
  transfer(newTable, initHashSeedAsNeeded(newCapacity));
  table = newTable;
  // 更新扩容阈值
  threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

至此，HashMap的扩容机制源码也解读完了，再细化总结一下： 当HashMap每次的put操作需要addEntry时，会判断size是否超过了扩容阈值（容量 * 0.75），如果超过了阈值则需要进行扩容，扩容大小为原来的两倍。

此外，1.8的初始化以及扩容过程与1.7基本相似，扩容核心函数也是resize，只是操作变成了Node数组以及额外要处理TreeNode，这里就不进行源码分析了，有兴趣的可以自己去阅读一下。

# Hashtable源码解读

从类的继承关系来看，Hashtable主要实现了Map接口以及继承了Dictionary抽象类，而这个抽象类并不实现Map结构。Dictionary抽象类是从JDK 1.0开始提供的，官方注释中对他的说明是：这个类已经过时了。新的实现应该实现Map接口，而不是扩展这个类。所以我们这块不用去研究它。

# 底层实现

Hashtable的底层数据结构在JDK 1.7 以及 1.8 是一样的：数组+链表，并没有像HashMap那样引入了红黑树。

/**
* 哈希表
*/
private transient Entry<K,V>[] table;

/*
* 哈希链表
*/
private static class Entry<K,V> implements Map.Entry<K,V> {
  int hash;
  final K key;
  V value;
  Entry<K,V> next;
  // ......
}

# 扩容机制

以下扩容源码版本为JDK 1.7。

# 构造函数&初始化数组

依旧从构造函数看起：

/**
* 默认创建一个初始容量为11并且负载因子为0.75的空hashtable
*/
public Hashtable() {
  this(11, 0.75f);
}

/**
* 指定容量创建一个空hashtable，负载因子默认为0.75
*/
public Hashtable(int initialCapacity) {
  this(initialCapacity, 0.75f);
}

/**
* 构造对象核心方法，指定初始容量以及加载因子
*/
public Hashtable(int initialCapacity, float loadFactor) {
  // 初始容量不能小于0
  if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal Capacity: "+
                                       initialCapacity);
  // 加载因子校验
  if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal Load: "+loadFactor);
  // 相比HashMap不同，初始容量如果是0，代码会变成1
  if (initialCapacity==0)
    initialCapacity = 1;
  this.loadFactor = loadFactor;
  // 相比HashMap不同，这里的确对哈希表进行了初始化 
  table = new Entry[initialCapacity];
  threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
  // 延时初始化哈希掩码值
  initHashSeedAsNeeded(initialCapacity);
}

/** 
* 使用Map集合转换为Hashtable
*/
public Hashtable(Map<? extends K, ? extends V> t) {
  this(Math.max(2*t.size(), 11), 0.75f);
  putAll(t);
}

由源码得知，在创建完一个Hashtable对象时，哈希表（数组）就已经创建了，他会直接使用指定的初始化容量，默认初始化为11（0会初始化为1）。也就是说，它并不会像HashMap那样对初始化容量作2的幂次方处理。

接下来，看看它是怎么扩容的？

# 扩容rehash

同HashMap一样，扩容的秘密就藏在put函数中，源码如下：

/**
* 线程安全的put方法，将指定的值与此映射中的指定键关联
*/
public synchronized V put(K key, V value) {
  // 确保value不能为空！
  if (value == null) {
    throw new NullPointerException();
  }
  // 
  Entry tab[] = table;
  // hash源码：hashSeed ^ key.hashCode()，同HashMap不一样，没有作很多的扰动
  int hash = hash(key);
  // 获取索引位置（0x7FFFFFFF 为Max INT）
  int index = (hash & 0x7FFFFFFF) % tab.length;
  // 相同key，覆盖操作
  for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
    if ((e.hash == hash) && e.key.equals(key)) {
      V old = e.value;
      e.value = value;
      return old;
    }
  }

  modCount++;
  // 元素数量超过了扩容阈值（容量 * 0.75），进行扩容
  if (count >= threshold) {
    // 扩容核心函数rehash
    rehash();

    tab = table;
    hash = hash(key);
    index = (hash & 0x7FFFFFFF) % tab.length;
  }

  // 创建新的Entry，直接赋值到对应数组位置
  Entry<K,V> e = tab[index];
  tab[index] = new Entry<>(hash, key, value, e);
  count++;
  return null;
}

根据上面源码的阅读，可知**：Hashtable不允许key或者value为null值，否则会NullPointerException，此外，hash扰动的过程也很简单暴力，而扩容触发条件同HashMap是一致的：元素数量超过了扩容阈值（容量 * 0.75），进行扩容。而扩容的核心代码则是rehash**。rehash源码如下：

/**
* 扩容核心
*/
protected void rehash() {
  int oldCapacity = table.length;
  Entry<K,V>[] oldMap = table;

  // 扩容为 原来的容量的两倍 + 1
  int newCapacity = (oldCapacity << 1) + 1;
  if (newCapacity - MAX_ARRAY_SIZE > 0) {
    if (oldCapacity == MAX_ARRAY_SIZE)
      // 如果达到了最大Size，保持最大值
      return;
    newCapacity = MAX_ARRAY_SIZE;
  }
  // 初始化新的数组
  Entry<K,V>[] newMap = new Entry[newCapacity];

  modCount++;
  // 重新计算扩容阈值
  threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
  boolean rehash = initHashSeedAsNeeded(newCapacity);

  table = newMap;
  // 后面就是迁移旧数据，作rehash处理
  for (int i = oldCapacity ; i-- > 0 ;) {
    for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
      Entry<K,V> e = old;
      old = old.next;

      if (rehash) {
        e.hash = hash(e.key);
      }
      int index = (e.hash & 0x7FFFFFFF) % newCapacity;
      e.next = newMap[index];
      newMap[index] = e;
    }
  }
}

由源码可知，Hashtable的扩容的变化主要是 原来的两倍 + 1，扩容过程除了这一点之外（HashMap是两倍），其他的，比如重新计算扩容阈值、申请新数组、迁移数据作rehash这些流程也基本相似。

# 线程安全实现

Hashtable是线程安全的，这个是与HashMap主要区别之一。Hashtable线程安全的方法其实就是采用synchronized关键字。例如，前面的put方法就被synchronized修饰了。线程安全源码这方面也没啥好看的了。你也可以理解为Hashtable是全表锁。

注意，在实际并发编程中，不会使用Hashtable，而是ConcurrentHashMap。因为synchronized的并发效率并不是很高，加上它与notify、notifyAll配合使用，出现的虚假唤醒等原因，所以，在实际并发编程中Hashtable使用较少。

Hashtable_lock

图片来源https://www.cnblogs.com/chengxiao/p/6842045.html

# ConcurrentHashMap源码解读

ConcurrentHashMap是线程安全的，在并发编程中使用较多的一个集合。在面试过程中，经常会对底层数据结构以及线程安全实现进行考核，至于初始化以及扩容方面与HashMap大致一致的（区别，例如初始化时多了并发级别选项，默认16）。接下来就从源码，看看这两个方面的内容：

ConcurrentHashMap类继承关系与HashMap很相似，主要的区别是ConcurrentHashMap实现了ConcurrentMap接口，而这个接口继承了Map接口。从类的关系我们大概也可以猜测到其底层结构与HashMap大致相同。

# 底层实现

ConcurrentHashMap底层实现在 JDK 1.7 、1.8 有较大的区别。

# JDK 1.7及之前

JDK1.7 的 ConcurrentHashMap 底层采⽤ 分段的数组（Segment + HashEntry）+链表 实现。

/**
* Segment数组，每个段都是一个专门的哈希表。
*/
final Segment<K,V>[] segments;

/**
* 1.7时，ConcurrentHashMap的底层核心实现为Segment类，继承了ReentrantLock（重点）
*/
static final class Segment<K,V> extends ReentrantLock implements Serializable {
   // ......
  
  /**
  * 每段的table数组，使用了volatile关键字 , 每个元素是个链表
  */
  transient volatile HashEntry<K,V>[] table;
  
  // ......
}

/**
* 链表
*/
static final class HashEntry<K,V> {
  final int hash;
  final K key;
  volatile V value;
  volatile HashEntry<K,V> next;
  // ......
}

# JDK 1.8及以后

JDK1.8 采⽤的数据结构跟 HashMap JDK 1.8 的结构⼀样：数组（Node）+链表/红⿊⼆叉树。（内部类也巨增，比1.7复杂多了）

/**
* 同HashMap一样，底层也是用了Node数组，但是有volatile修饰
*/
transient volatile Node<K,V>[] table;

/**
* Node链表结构
*/
static class Node<K,V> implements Map.Entry<K,V> {
  final int hash;
  final K key;
  volatile V val;
  volatile Node<K,V> next;
  // ......
}

/**
* 红黑树
*/
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;
  // ......
}

# 线程安全实现

关于线程安全的实现，ConcurrentHashMap在JDK1.7 以及 JDK 1.8 有较大区别：

# JDK 1.7及之前

在 JDK1.7 的时候， ConcurrentHashMap 线程安全采用的方案是 分段锁：对整个桶数组进⾏了分割分段( Segment )，每段数据都有一把锁，多线程访问容器⾥不同数据段的数据，就不会存在锁竞争，提⾼并发访问率。

由上面的底层实现可以知道，1.7 的ConcurrentHashMap是由Segment数组+HashEntry数组组成，并且HashEntry是链表结构。

Segment类是继承ReentrantLock的，ReentrantLock是JUC包提供的可重入锁。每个Segment对象都维护着一个HashEntry数组，每次进行put操作都会先获取Segment的锁。获取锁以及释放锁都是调用的是ReentrantLock的tryLock()以及unlock()。部分源码如下：

static final class Segment<K,V> extends ReentrantLock implements Serializable {
  
  // .......
  
  final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    HashEntry<K,V> node = tryLock() ? null :
    scanAndLockForPut(key, hash, value);
    
    try {
      //......
    }finally {
      unlock();
    }
  }

}

java7_concurrenthashmap

图片来源：https://www.cnblogs.com/chengxiao/p/6842045.html

# JDK 1.8及以后

ConcurrentHashMap到了 JDK1.8 的时候没有继续使用 Segment 的概念，首先底层结构发生了变化，如前面所说的采用了Node数组+链表/红⿊⼆叉树，而线程安全实现则使⽤ synchronized 和 CAS 来操作，你可以理解为优化过且线程安全的 HashMap 。部分源代码如下：

transient volatile Node<K,V>[] table;

/**
** put核心代码
*/
final V putVal(K key, V value, boolean onlyIfAbsent) {
  // null值 抛出异常
  if (key == null || value == null) throw new NullPointerException();
  int hash = spread(key.hashCode());
  int binCount = 0;
  for (Node<K,V>[] tab = table;;) {
    Node<K,V> f; int n, i, fh;
    if (tab == null || (n = tab.length) == 0)
      tab = initTable();
    else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
      // cas，底层是Unsafe
      if (casTabAt(tab, i, null,
                   new Node<K,V>(hash, key, value, null)))
        break;                   // no lock when adding to empty bin
    }
    else if ((fh = f.hash) == MOVED)
      tab = helpTransfer(tab, f);
    else {
      V oldVal = null;
      // sync 修饰代码块
      synchronized (f) {
        // cas
        if (tabAt(tab, i) == f) {
         //......
        }
        //......
      }
  }
  //......
  return null;
}

java8_png

图片来源：https://javaguide.cn/java/collection/java-collection-questions-02.html

# LinkedHashMap

LinkedHashMap从类的继承体系可知，它是直接继承HashMap的，拥有HashMap的所有特性。此外，LinkedHashMap额外维护了一个双向链表，目的是保持遍历顺序和插入顺序一致。LinkedHashMap的源码并不复杂，仅为维护双向链表覆写了部分方法。

// 1.7 双向列表 头
private transient Entry<K,V> header;

// 1.8 双向列表 头 + 尾
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;

下面以 JDK 1.8 为例说明LinkedHashMap维护双向链表的一些核心说明：

Entry 继承了 HashMap的Node (1.7是Entry)，内部维护了前驱节点和后驱节点：

static class Entry<K,V> extends HashMap.Node<K,V> {
  Entry<K,V> before, after;
  Entry(int hash, K key, V value, Node<K,V> next) {
    super(hash, key, value, next);
  }
}

维护双向链表覆写了部分方法。LinkedHashMap维护双向链表设计较巧妙，主要通过重写实现（钩子函数）。它不是对put、remove这些方法复写，而是对HashMap中定义的钩子函数进行复写：afterNodeAccess、afterNodeInsertion、afterNodeRemoval等（新增是重写了newNode），put、remove方法里面则会调用这些函数（利用了多态）。

// 新增，LinkedHashMap的重写了newNode
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
  LinkedHashMap.Entry<K,V> p =
    new LinkedHashMap.Entry<K,V>(hash, key, value, e);
  linkNodeLast(p);
  return p;
}


// HashMap定义的函数，Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

关于LinkedHashMap更多可以参考这篇文章：https://blog.csdn.net/qq_26737667/article/details/105447089

上次更新: 5/28/2023, 10:57:53 PM