HashMap源码分析（一）

​ 在jdk8以前，HashMap的存储结构有两种：顺序结构和链表结构。在jdk8之后，对HashMap进行了优化（主要体现在结构和扩容算法）,添加了红黑树结构来优化对HashMap的管理。本文着重分析HashMap在树化前的逻辑。

1. 存储结构

​ 在jdk8以前，HashMap的存储结构有两种：顺序结构和链表结构，如下图所示：

结构图.png

​ 在HashMap中，维护着一个数组（之后称table）作为数据存储的基本结构，而table的每一项是一个Node<K,V>的类型，作为链表结构的头节点。调用put()方法存储（key值未存储过，替换的情况下文详细介绍）时，会先通过key值计算其HashCode码，然后将其进行一些运算（具体计算过程在下文中介绍），获得其对应的index，之后判断table的index位是否有数据，若有数据的话，就通过位于该位置的头节点开始遍历链表，并将其放在链表的下一个空位。

2. 原理

2.1 属性

​ HashMap没有从父类（AbstractMap）继承任何属性值，所有用到的属性均为其自己的属性。下面我们来看一下他们：

/**
*这个属性是HashMap的默认存储容量，为16，HashMap的容量通常为2的n次幂，有关这个规定，有人解释为是计算机进
*行2次幂的计算非常高效。但是我认为主要原因还是与HashMap的存储结构和存储方式有关（下文解释）。
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**这个属性是HashMap的最大容量，为2的30次幂。*/
static final int MAXIMUM_CAPACITY = 1 << 30;    

/** 
* 默认的负载因子，当未设置负载因子时，默认为0.75。意思是每当HashMap里的item数超过（总容量/负载因子）  
* 时，就进行扩容。
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**hashmap中存储数值的数组，在第一次使用的时候才会初始化,并且在达到阀值的时候扩容。*/
transient Node<K,V>[] table;

/**本map中存储的键值对个数*/
transient int size;

/**hashMap被结构性修改的次数*/
transient int modCount;

/**阀值，当HashMap中的键值对数达到该值时进行扩容*/
int threshold;

/**加载因子*/
final float loadFactor;

​

2.2 构造函数

​ HashMap总共有四个构造函数：

/**
* 默认的构造函数，所有值使用默认值
*
*/
public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

/**
* 指定容量大小的构造函数（注意此处的容量大小必须大于等于0，在之后会使用大于该数字的第一个2的n次幂作为最终容
* 量）
*/
public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
   
/**
* 指定容积大小和加载因子的构造函数（注意此处的容量大小必须大于等于0，在之后会使用大于该数字的第一个2的n次幂
* 作为最终容量）
*/
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;
        this.threshold = tableSizeFor(initialCapacity);//扩容阀值（就是当容量超过这个值时进行扩容，讲道理这里本应该是  this.threshold = tableSizeFor(initialCapacity) * this.loadFactor; 但是看之后代码发现阀值在table实例化的时候（resize()方法内）进行的重新赋值。
    }

/**
* 包含子map的构造函数
*/
public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

​ 我们接下来就详细看一下tableSizeFor()这个方法，看看它是怎么通过我们给它的容量，决定扩容的阀值的：

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;
    }

​ 这个方法，其实是返回大于（或等于）cap（传入参数）且最近的2的n次幂的数。可能有些难以理解，接下来我们可以看 HashMap源码注解 之 静态工具方法hash()、tableSizeFor()（四） ，博主通过图文很详细地说明了这个算法是如何进行的。

​

2.3 put实现

​ 我们来看put方法的实现：

 public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

​ 我们先看一下hash()的算法：

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

​ 从这里我们发现最后算出的hash码又让他的高16位和低16位做了一次异或运算，这是个扰动函数，目的是为了加大低位的随机性。我们继续往下看：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;//tab:当前table    p:指定index的Node  n:tab长度     i:index
        if ((tab = table) == null || (n = tab.length) == 0)//若table为空，则通过resize()初始化，并拿到tab长度
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)//若index位置的链表为空，则创建新链表头节点放入
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;//e:链表的当前node k:node的当前key
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))//若链表头节点的hash值、key都与放置的键值对的key相等，则获取该头节点
                e = p;
            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);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);//转换treenode（先记住，下文分析）
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))//若链表子节点的hash值、key都与放置的键值对的key相等，则获取该子节点（获取方法写在该循环第一个if中）
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                //若有key相同，则修改其中的value即可
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);//给子类扩展的方法，此类中为空方法
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)//若map中的键值对数量超过阀值，则扩容
            resize();
        afterNodeInsertion(evict);//给子类扩展的方法，此类中为空方法
        return null;
    }

​ 从代码中我们可以知道，HashMap计算index的算法为：

i = (n - 1) & hash

​ 那么它又是如何保证我们得到的index在table的范围内呢？
​ n是table的大小，要求其必须满足2的n次幂，所以，将其转化成二进制数为“0…10…0”，从右到左数第i位为1(i>=0)，其余的位置为0，对其进行-1的操作后，就会变成“0…1…”，从第(i-1)位开始，右边全为1，这就是说任何数和它做与运算时，都不考虑这个数高于i的位上的数，所得出的结果一定是小于n的数。

2.4 get实现

​ 我们接着看get()方法的实现：

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

​ 再往下看：

final Node<K,V> getNode(int hash, Object key) {//前面我们可以知道，这个hash是通过key计算出hashCode并进行高16位和低16位异或后的产物
    //tab:table first:链表的头节点 e:遍历用的节点 n:table长度 k:key
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {//若table已初始化并且index位的头节点不为空
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))//找value的判断有三个，hash值是否相等(必须)，key的引用地址是否相等和key值是否相等(满足任意一个)
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))//遍历链表子节点
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

2.5 HashMap的扩容

​ 接下来，我们进入最重要的一个环节，也是许多面试官喜欢问的问题，HashMap的扩容。话不多说，我们直接上源码：

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;//获取扩容前的table
        int oldCap = (oldTab == null) ? 0 : oldTab.length;//获取之前table的容量
        int oldThr = threshold;//获取之前的阀值
        int newCap, newThr = 0;//声明新的容量和大小
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {//当之前的长度达到最大容量的时候，不进行扩容，该咋咋
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)//新的容量等于double oldCap，若小于最大容量并且旧容量大于等于默认容量的话，double threshold。这么计算的原因是：oldThr = oldCap * threshold, newThr = newCap * threshold = oldCap * 2 * threshold = oldThr * 2
                newThr = oldThr << 1; // double threshold
        }//接下来两个else都是初始化table的操作
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;//若之前的threshold不为空，则是因为实例化HashMap时传入了初始容量（详见构造函数），这时拿到传入后经过计算的容量
        else {               // zero initial threshold signifies using defaults
            //使用默认容量和默认阀值
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {//当table为空时的初始化阀值
            float ft = (float)newCap * loadFactor;//计算出理论上的阀值
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);//判断最大容量相关逻辑
        }
        threshold = newThr;//这是最后获得到的阀值
        @SuppressWarnings({"rawtypes","unchecked"})//屏蔽掉IDE可能报的警报
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//new一个新的table
        table = newTab;//再把table指向新table，为什么不直接 table = (Node<K,V>[])new Node[newCap]?
        if (oldTab != null) {//遍历赋值
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;//将旧的table空间释放
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;//重新计算index
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;//扩容后不用移位的头节点和子节点
                        Node<K,V> hiHead = null, hiTail = null;//扩容后需要移位的头节点和子节点
                        Node<K,V> next;//next节点
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {//这里也是一个重点，因为oldCap是2的n次幂，所以这个式子只拿了扩容后最高位的数，若为0，则说明扩容后通过计算得出的index不变，不需要移位，若为1，则将该位移动到其该去的位置上
                                //若为0，则说明该节点不用移位，将其放到不用移位的链表下
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {//若为1，则说明该节点需要移位，将其放到需要移位的链表下
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {//放置不用移位的链表头节点
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {//放置需要移位的链表头节点
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }