HashMap源码解析

本文主要记录Java中集合类HashMap的使用以及从源码（基于Java 8）的角度分析它的实现原理。

HashMap介绍

HashMap是一种通过键值对映射（key-value）的方式存储数据的一种集合对象，每个key最多只能对应一个value，HashMap的用法一般如下所示：

HashMap<String,String> map = new HashMap<>();//初始化HashMap
map.put("a","hahaha");//把“a”处映射的value设为“hahaha”
String value = map.get("a");//取出key为“a”的数据，此时value就是上面的“hahaha”

HashMap这个单词可以分两部分看，第一部分是Hash、然后是Map。在Java中Hash代表的就是hashCode，阅读过Object源码的都知道Object类中有hashCode和equals方法，设计这两个方法的目的也就是为了方便Java中哈希表集合类的使用，而Map在Java中则代表Map接口，Map接口在Java中被定义为是一个提供key和value之间映射的对象，并且同一个map中不能包含多个相同的key，每个key最多只能映射一个value，这有点类似于数据库里的主键和数据之间的映射关系，HashMap的大致结构如下图所示：

HashMap结构图

从上面的图我们可以知道HashMap底层使用数组+链表+红黑树三巨头实现的，先来看看源码中HashMap类的定义和它重要的几个属性：

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//默认的初始容量为16
  static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认负载因子为0.75
  static final int TREEIFY_THRESHOLD = 8;//链表转化为红黑树的容量阈值
  static final int UNTREEIFY_THRESHOLD = 6;//红黑树转化为链表的容量阈值
  //节点数组，用于保存所有的数据,数组的实际容量只能是2的幂次方，每次扩容增长为原来的两倍
  transient Node<K,V> [] table;
  final float loadFactor;//负载因子
  int threshold;//数组扩容的数据量阈值，值等于capacity*loadFactor
  int size;//数据量大小，注意这个不是table的长度，每put一个数据size要加1
  ...
}

首先可以看出HashMap有两个泛型K和V，其中K代表键、V代表值，并且HashMap继承了AbstractMap、实现了Map接口（这里有点疑惑为什么HashMap要重新实现Map接口，因为AbstractMap已经实现了Map接口，可能是历史遗留问题）¹，并且HashMap还支持克隆（浅拷贝）和序列化。HashMap中有一个Node数组（也就是三巨头中的数组），Node数组保存HashMap中的所有数据，要理解HashMap存储与取值过程首先要理解HashMap中的静态内部类Node、TreeNode和HashMap里面的几个重要的骚操作，首先看看Node，也就是三巨头中的链表。

静态内部类Node类解析

Node类源码如下所示：

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
  //...
  public static class Node<K,V> implements Map.Entry<K,V>{
    final K key;
    V value;
    final int hash;
    Node<K,V> next;
    //其他方法省略，就是一些很普通的针对Object类方法的重写（譬如equals和hashCode）
    ...
  }
}

由Node源码可以看出，Node是个链表，保存了key和value，并且key和hash是final的（这保证了HashMap在get的时候不会定位到错误的位置）。

静态内部类TreeNode解析

三巨头除了数组和链表之外还有红黑树，那么这个红黑树就是我们接下来要说的TreeNode，TreeNode源码大致如下：

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继承LinkedHashMap.Entry，点进LinkedHashMap.Entry类里可以知道LinkedHashMap.Entry继承HashMap.Node，所以其实TreeNode也是Node的子类，只不过多了红黑树的一些方法，这样就可以在table数组里存储红黑树的实例了。

HashMap重要骚操作

HashMap之所以高效是因为HashMap里面用到了几个骚操作（其实最主要是位操作），桶定位、tableSizeFor（找出一个比给定值更大的2的幂次方的值）和hash方法（保证散列性，降低碰撞），下面梳理下这三个骚操作。

桶定位

通过前面的分析可以知道HashMap里有一个table数组，数组长度是2的幂次方，table里的每一项我们称之为一个桶，桶定位的意思就是给定一个key，通过计算key的hash值我们可以把它定位到数组里的某一个桶，那么怎么做才简单高效呢？答案就是下面第二行代码：
```
int size = table.length;//数组长度
int index = (size - 1) & hash;//得到的index的值一定是在0-size之间
```
由于size一定是2的幂次方所以（size-1）的低位一定全是1、高位全是0，所以根据&运算符的特性我们可以得出最后index的值一定是落在0-size之间。
tableSizeFor

HashMap在当初始化时用户可以传入initialCapacity参数代表初始容量，但我们知道HashMap的容量只能是2的幂次方，所以必须要有一个方法通过initialCapacity计算一个大于或等于它的数值作为数组的容量，HashMap中的静态方法tableSizeFor就是干这件事的，tableSizeFor方法源码如下：
```
public static int tableSizeFor(int cap){
  int n = cap - 1;//1
  n |= n >>> 1;//2
  n |= n >>> 2;//3
  n |= n >>> 4;//4
  n |= n >>> 8;//5
  n |= n >>> 16;//6
  return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;//7
}
```
这段代码的作用就是生成一个比cap大的或等于的最接近的2的幂次方的数值，这段代码很精妙，但也挺好理解，下面随便考虑一个数（补码表示）：
```
0010 1101//真值是+45
```
如果我们想找到一个比这个数大的2的幂次方的数该怎么办呢？其实很容易可以想到只要从左到右找到第一个1存在的位置，然后左移一位，最后低位全部清0就行（当然这里不能超过int类型最大值的限制），具体过程如下：
```
0010 1101
0101 1010//左移一位
0100 0000//低位全部清0，此时结果是64，符合要求
```
原理很简单，HashMap实现时采用了另一种思路，要实现低位全部清0，那么只要低位全部为1并且高位全部是0之后再加上1就行了，所以得出了上述代码，至于第一步要减去1的理由是如果传入的cap已经是2的幂次方了，不减去1得到的结果是cap*2，不符合大于或等于的最接近的2的幂次方这个要求。
hash方法

HashMap的hash方法没有直接使用key的hashCode，而是自己有一个hash方法，所有的key都要经过这个hash方法后存储到Node中去，hash方法源码如下：
```
public static int hash(Object key){
  	int h;
		return key == null ? 0:(h = key.hashCode())^(h >>> 16);
}
```
这段代码的作用是输入一个key，如果key为null则返回0，如果不是则把key的高16位不变，低16位与高16位异或然后返回异或后的结果，这样做的好处是为了让高位与低位都参与到hash计算中去，降低hash碰撞的概率。降低hash碰撞的好处就是可以降低时间复杂度，HashMap最好的情况就是数组里面的桶里只有单个元素（既不是链表也不是红黑树），这样查找的时间复杂度可以降到O(1)。通过降低hash碰撞的概率，可以达到基本上每个桶上只有一个元素的状态，此时效率自然就提升了。

通过前面的分析可以大致得到HashMap的内部结构和一些重要的骚操作了，接下来就进入正题，HashMap到底是怎么存储和获取数据的呢？

resize方法

通过前面的分析我们知道HashMap中的table是有容量限制的，如果一直使用默认的容量，当数据越来越多时，hash碰撞就会越来越严重，效率也就越来越慢，那么为了解决这个问题就有必要对table进行扩容。HashMap中的扩容动作一般是在新增数据时也就是put方法调用时执行的，put数据时扩容一般有两种情况：

put时发现table为null或者table长度为空
put数据完成后发现HashMap的size大于threshold（也就是阈值）

扩容方法也就是resize方法伪代码如下（忽略最大值处理）：

Node<K,V> resize(){
  Node<K,V> newTable = table;
  int oldCap = table == null ? 0 : table.size();//获取当前数组容量
  int oldThr = threshold;//获取当前阈值
  int newCap,newThr = 0;//定义新的容量和新的阈值
  if(oldCap > 0){
    newCap = oldCap << 1;//扩容为原来的两倍
    newThr = newCap * loadFactor;//阈值也变为原来的两倍
  }else if(oldThr > 0){
    newCap = oldThr;//这种情况一般是用户初始化HashMap时自己定义了初始容量
  }else{
    //用户使用的是默认构造函数
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = newCap * DEFAULT_LOAD_FACTOR;
  }
  if(newThr == 0){
    newThr = newCap * loadFactor;
  }
  threshold = newThr;//重新赋值阈值
  //遍历整个table，做移动数据等操作，这里省略
  return newTable;
}

通过上面的伪代码可以得到resize方法的执行流程如下所示：

HashMap结构图

通过伪代码和流程图可以得出两个结论：

HashMap在使用默认构造函数初始化时默认容量为16，阈值为16*0.75（默认负载因子）
HashMap每次扩容后容量会变为原来的两倍，并且阈值也会变为原来的两倍

put方法

话不多说，先来看伪代码：

public V put(K key,V value){
  int hash = hash(key);//通过内部hash方法获取key的hash值
  Node<K,V> p;
  if(table == null || table.length == 0){
    resize();//如果当前数组是null或者数组长度为空则进行扩容
  }
  int index = (table.length-1) & hash;
  p = table[index];//根据hash值找到Node对应的桶，并返回桶中链表的头指针或者红黑树的根节点
  if(p == null){
    //如果当前的桶内没有数据则直接新建一个Node放入桶内
    table[index] = new Node<>(hash,key,value,null);
  }else{
    //当前桶内已经有数据了
    Node<K,V> result;
    if(hash == p.hash && key.equals(p.key)){
      //如果桶内第一个元素的key和当前要找的key是一样的（hash值相等并且key的equals为true），那么说明数据已经找到，只需要把新值赋进去就行
      result = p;
    }else if(p instanceof TreeNode){
      //当前桶内数据结构是红黑树
      result = 红黑树的相关方法;
    }else{
      //当前桶内是一个链表，遍历这个链表找key是当前搜索key的节点，如果
      int count = 0;
      for(int i=0;;i++){
        if((result = p.next) == null){
          result = new Node<hash,key,value,null>;
          if(i >= TREEIFY_THRESHOLD - 1){
            //如果当前链表长度大于规定的阈值则把链表转化为树
            treeifyBin(tab, hash);
          }
          break;
        }
        if(hash == result.hash && key.equals(result.key)){
          //找到对应的数据，直接break
          break;
        }
        p = result;
      }
    }
    if(result != null){
      //当前桶内已经有这个key对应的数据
      V oldValue = result.value;
      result.value = value;//赋新值
      return oldValue;
    }
  }
  //当前桶内没有这个key对应的数据并且如果数据量大于扩容的阈值则进行一次扩容
  if(++size > threshold){
    resize();
  }
  return null;
}

流程图大致如下：

HashMap put

put方法的整个流程如上所述，没什么复杂的东西，最复杂的应该就是红黑树的一些操作，但put方法需要注意的点有几个：

Java 8开始是采用尾插法插入数据到链表中的，Java 8之前都是头插法。
put时如果是新建的Node（当前的key在HashMap中找不到对应的值）那么会判断当前table里所有数据是否大于扩容的阈值，如果大于就会进行一次扩容。
如果插入时对应的桶里的数据量大于规定的链表转红黑树的阈值则会把桶里的结构由链表转为红黑树。
put方法返回的是旧的值，而不是新的值

get方法

其实知道了put方法的原理那么get方法就很简单了，猜都能猜出来是怎么做的，get方法的伪代码如下：

public V get(K key){
  int hash = hash(key);
  int index = (table.length - 1) & hash;//找桶的位置
  Node<K,V> bucket = table[index];
  if(bucket == null){
    //没找到数据，返回null
    return null;
  }else{
    if(bucket.hash == hash && key.equals(bucket.key)){
      //桶内第一个元素就是要找的数据
      return bucket.value;
    }else if(bucket instanceof TreeNode){
      //桶内的数据结构是红黑树
     	...用红黑树的查找方法查找数据并返回值
    }else{
      //桶内数据结构是链表
      ...用链表的查找方法查找数据并返回值
    }
  }
}

总结

其实也没啥好总结的，所有注意的点都写在上面了，看源码还是得要多想多看，实在想不通可以翻翻别人写的博客，但也不能一切以别人博客上说的为准，实践出真知，切记不可焦躁。

为什么Java中的Collection类都继承了抽象类还要实现抽象类的接口?或者Why do many Collection classes in Java extend the abstract class and implement the interface as well? ↩

HashMap源码解析

HashMap介绍