HasMap源码解析（jdk1.8对比jdk1.7）

  在日常开发中如果需要存储的数据是键值对的形式，那么我们首先想到的数据结构肯定是HashMap了，当然还有HashTable。如果是在Android开发中则建议使用SparseArray和ArrayMap来替代HashMap，不过这里主要是针对HashMap不同版本进行源码解析。正因为HashMap的重要性，所以在面试过程中则可能会被频繁的问到。如果对HashMap的源码没有一定的了解可能就直接GG了。

  在阅读源码之前还是需要对HashMap的使用有一点的了解才行，不过HashMap的基本使用还是很简单，这里简单的说一下。首先new一个对象出来，然后通过new出来的对象直接调用put、remove、get、entrySet等方法对数据进行增删查改等操作。比如下面就是往一个HashMap对象中添加键值对：

HashMap<String,String> map = new HashMap<String,String>();
map.put("姓名","若曲一风");
map.put("性别","男");
复制代码

二、HashMap数据结构

  在jdk1.7和jdk1.8上HashMap存储数据的方式基本上来说是类似的，都是采用数组加链表的方式来实现。不过他们也存在很大的区别：

（1）在jdk1.8上，如果数组上某一个下标的链表节点树大于等于了8之后该坐标下的链表就会转换为红黑树；

（2）在jdk1.7上，链表节点采用的是头插法，因为设计HashMap的人认为后插入进来的数据被访问的可能性更大，不过这在多线程下就可能会出现循环链表的情况；在jdk1.8上将头插法改为了尾插法，这是因为在将链表转换为红黑树的过程中可以直接按照链表顺序进行节点的获取；当然这样做的目的也能够避免在多线程操作下出现循环链表的情况。不过在多线程下HashMap并不安全，而应该使用ConcurrenHashMap，有兴趣的可以百度一下；

（3）当然除了上述两个比较大的区别外，还有resize的方式等，这个后续会逐步的讲解。

二、HashMap之jdk1.8版本源码解析

1、基本属性值

  在正式开始源码解析之前了解一下其中的部分属性值，能够更好的去理解源码的逻辑实现。

1.1 常量

1.2 变量

2、构造函数

  HashMap为我们提供了三种构造函数用于构造一个新的HashMap对象，一般来说我们会根据自己的需要来使用不同的构造函数，

2.1 无参构造函数

  该构造函数中并没有做过多的初始化工作，仅仅只是初始化了负载因子为0.75。

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
}
复制代码

2.2 有参构造函数

  有参构造方法有两种，分别一个参数的和两个参数的，其中只有一个参数的构造方法会调用到两个参数的构造方法中，因此我们只需要去看一下两个参数的构造方法就ok了。

public HashMap(int initialCapacity, float loadFactor) {
    //只允许初始化大小等于0
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    //HashMap中数组最大为2的30次方
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    //该值在第一个put数据进来的时候会用于初始化数组大小
    //那么tableSizeFor这个方法又是干嘛的我们来看看
    this.threshold = tableSizeFor(initialCapacity);
}
/**
* 假设我们这里传入的cap ＝ 5，我们看看下面的位运算最后结果是啥：
* （1）5的二进制是0000 0101然后再减1的二进制是0000 0100
* （2）将4向又移一位再与4进行或运算值为 0000 0110 = 0000 0100 | 0000 0010
* （3）再将6向右移动两位再与6进行或运算值为0000 0111=0000 0110 | 0000 0001
* （4）后面的移动8位移动16位对于当前值就没有意义了。最后返回的结果是则是
*  0000 0111 + 1 = 7 + 1 = 0000 1000
* （5）会发现在HashMap中会将用户初始化的数组大小通过位移的方式转换为2幂
*  这在初始化数组的时候会作为数组的初始大小
**/
 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;
}
复制代码

  在前面的学习我们知道，如果在初始化HashMap的时候没有指定初始化大小，那么默认大小就是16。如果用户需要初始化数组大小，即使不是2幂，也会通过位移的方式转换为2的幂的形式。这是因为这样能够有效降低Hash冲突，并且让Node节点能够均匀的分布在HashMap中数组的每个下标位置。

3、链表Node节点

  HashMap中键值对最终是以Node节点的形式存储在链表中，而链表又会根据不同的hash值存储在不同的数组下标中。Node节点数据结构并不复杂，主要用于存储键值对、hash值以及下一个Node节点的引用等，当然还提供了get、set以及equals等方法。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V 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 int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
    //如果key值相同，需要替换其中的value值就会调用到该方法
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    //用于判断两个node节点是否相等
    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;
    }
}
复制代码

4、put方法

  现在正式开始我们的重头戏，如何将数据插入到HashMap中。在解析源码之前不妨想一下如果自己设计一个put函数会怎样设计？无非就是如下几个步骤：

（1）判断数组是否初始化，如果没有初始化则初始化数组；

（2）通过key值的hashCode找到在数组中对应的index；

（3）判断index是否已经有node节点，如果没有说明没有发生hash冲突直接生成node节点并将node节点添加到index所对应下标。如果有则说明发生了hash冲突；

（4）遍历链表，并在遍历过程中判断是否存在key相同的node节点，如果存在则直接替换该node节点的value值，并返回旧的value。如果不存在则生成新的node节点并添加到链表尾部；并判断当前链表长度是否大于等于8，如果是则将链表转换为红黑树；

（5）如果是新建的node节点则将size+1，并判断当前size是否大于等于了阀值，如果是则说明已经达到了resize条件，将HashMap中的数组重新resize；

  接下来我们看一下它的源码。put方法的最终实现是在putVal方法中，所以我们直接看该方法源码就OK了。

/**
* hash:key值的hash值
* onlyIfAbsent:如果该值为true即使key相同也不改变原node节点
* 返回值:被修改node节点的旧value值
**/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //首先判断当前数组是否已经存在或者已经初始化了
    //如果没有则通过调用resize方法初始化数组，后续会进行讲解
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //判断key值hashcode在数组中所对应的index值是否存在元素
    //如果为null，说明没有元素直接生成新的node节点并存储到该index
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    //该else说明发生了hash冲突
    else {
        //e中的value值被新的value值替换
        Node<K,V> e; K k;
        //首先判断第一个节点的hash值是否和要插入的key值所对应的hash值相等
        //然后判断第一个节点中的key值是否和要插入的key值相等；
        //如果相等则直接将第一个node节点中的value值用新的value值替代
        //这里可以思考一下为什么会用上＝＝和equals两种方法？面试可能会问
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //判断当前存储的是不是红黑树的形式
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //如果第一个node节点中key值不和新的key相等并且当前也不是红黑树
        //则按照链表的方式进行遍历
        else {
            //遍历当前链表，binCount表示节点数，用于判断是否需要转换为红黑树
            //同时在遍历的过程中判断node节点中key值是否和新的key相同
            //如果存在则记录该node节点并结束遍历
            for (int binCount = 0; ; ++binCount) {
                //判断是否遍历到了链表尾部,如果是则
                //生成新的node节点并插入到链表尾部
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //判断当前链表节点数是否大于等于8，这里为什么是－1
                    //是因为最后一个节点没有计算进去。如果大于等于了8则转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                //判断当前node节点中key值是否和要插入元素的key相等，如果则是则记录该节点并结束当前遍历
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //判断是否存在node节点中key值和要插入的key值相等，如果是则
        //直接替换该node节点中的value值并返回旧的value值
        if (e != null) { 
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //判断当前数组中所有链表节点树是否大于了阀值，如果是则重新resize，也就是扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
复制代码

  在源码分析过程中又这样一个问题，就是其中的key值判断为什么同时使用到了两种判断方式。其实仔细一想也就发现为什么了。首先＝＝可用于基础类型判断，如果是对象则可以判断这两个对象地址是否一样；而equals方法在每个类中可能会有不同的实现方式，比如在String中就会判断两个String对象中的内容是否相等。所以用这两种方式判断的好处是既能判断基础类型也能够判断对象是否相等。

5、resize方法

  在put过程中两次调用到了resize方法，第一个是为了初始化数组，第二次则是为了对数组进行扩容，所以我们在看这一个方法代码的时候可以分为两个逻辑部分来看会更加清晰。接下来我们对该方法进行解析。

final Node<K,V>[] resize() {
    //记录旧的数组，用于后续resize
    Node<K,V>[] oldTab = table;
    //记录当前数组长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //记录当前扩容阀值
    int oldThr = threshold;
    //新的数组长度和新的阀值
    int newCap, newThr = 0;
    //数组长度大于0说明不是初始化
    if (oldCap > 0) {
        //如果数组长度大于了允许的最大长度则不再扩容，直接返回当前数组大小
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //将原数组大小向左平移一位也就是*2,如果扩容后的大小小于允许的最大数组大小
        //并且原始数组大小大于等于16则将阀值也扩大为原来的两倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; 
    }
    //当前为初始化数组并且阀值大于0，也就是是通过有参构造函数生成的对象
    //则数组初始化大小设为了阀值，该阀值在解析构造方法时候有讲解
    else if (oldThr > 0) 
        newCap = oldThr;
    //如果是通过无参构造方法生成的对象则将数组初始化大小设置为16
    //阀值设置为12，也就是数组初始化大小*负载因子0.75
    else {            
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //newThr为0只可能是一种情况那就是进入到了第一个if语句
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    //生成新的数组
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    //如果旧数组不为null，说明是扩容调用进来的，不是初始化
    //则将旧数组中的元素重新hash到新的数组中
    if (oldTab != null) {
        //从前向后依次遍历数组元素
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //如果当前index下的元素节点只有一个元素
                //则根据新的长度重新计算元素下标
                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 { 
                    //存储低位链表头节点和尾节点
                    Node<K,V> loHead = null, loTail = null;
                    //存储高位链表头节点和尾节点
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    //从前向后遍历链表，并将根据链表中node节点的hash值将
                    //node节点分为了高位和低为，并将高位和低位node节点分别存储在不同的位置
                    //什么叫做低位节点和高位节点呢？在后面会讲解。
                    do {
                        next = e.next;
                        //如果当前node节点hash值和原数组长度&为0则为低位
                        //相反则为高位
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            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;
}
复制代码

  在解析resize过程中提到了低位节点和高位节点。那它到底是什么呢？首先高位和低位的计算方式是通过node节点中的hash值和原数组长度进行&得到的，而node节点的index值则是通过hash值与数组长度减一得到的。下面给出如下两个实际的例子来计算一下node节点的index值。假设数组长度length = 16：

（1）hashcode = 5。则index = 5 = 0101 = 0101 & 1111 = hashcode & (length - 1)；

（2）hashcode = 21。则index = 5 = 0101 = 0001 0101 & 0000 1111 = hashcode & (length - 1)；

  会发现即使hashCode不相同，但是最后计算出来的index结果却是相同的,，也就是出现了hash冲突，需要将两个节点构造为链表。我们再来看看计算高位和低位的最终结果，我们还是以上面两种情况为例：

（1）low = 0 = 0000 = 0101 & 1 0000 = hashcode & length；

（2）high = 16 = 1 0000 = 0001 0101 & 1 0000 = hashcode & length；

  这种计算方式你会发现如果node节点的hash值大于等于了数组长度则会被归类为高位，如果小于了数组长度则会被归类为低位。这样做是因为数组在扩容之后，不同node的hash值所对应的index也会随着变化。还是以上面两种情况为例，并将length变更为32，那么：

（1）index = 5 = 0101 = 0101 & 0010 0000 = hashcode & (length - 1)；

（2）index = 21 = 0001 0101 = 0001 0101 & 0001 1111 = hashcode & (length - 1)；

  所以我们得出结论，node节点hash值小于原数组长度的index值不变，而node节点hash值大于等于原数组长度的index则变为了原index值加上原数组长度。

6、获取键值

  在HashMap中提供了多种获取key、value值的方式，比如get(Object key)、keySet()、values()以及entrySet()等方法。下面我们对这几个方法的源码进行解析。

6.1 get方法

  get方法是通过一个key值获取一个value值，而最后的真正实现则是在getNode中。所以直接看getNode方法。

/**
 * 其实逻辑很简单大致分为了如下几个步骤来查找一个node节点
 * （1）判断当前table是否已经初始化并且存在数据
 * （2）根据传入key值的hash值得到要查找值的下标
 * （3）判断链表第一个node节点是否是我们要查找节点，如果是则直接返回该节点
 * （4）判断当前是否是红黑树，入股哦是红黑树则通过遍历树的方式进行查找
 * （5）依次遍历链表中的节点，并在遍历过程中判断是否是要查找对节点，如果是则直接返回该节点结束查找。
 * （6）如果没有查找到key值对应到节点则直接返回null
 **/
 final Node<K,V> getNode(int hash, Object 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) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            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;
}
复制代码

6.2 keySet、values以及entrySet方法

  三个方法本质来说都是对HashMap中的数组和链表进行遍历来获取值的，所以看源码会发现他们最终的实现都是调用的同一个方法，只是最后获取到的数据不同而已。在讲解源码之前，首先了解一下他们的使用方式：

HashMap<String,String> map = new HashMap<String,String>();
map.put("姓名","若曲一风");
map.put("性别","男");

//获取key集合迭代器，并通过迭代器获取所有key值
Iterator<String> keySet = map.keySet().iterator();
while (keySet.hasNext()){
    Log.i(TAG, "key = " + keySet.next());
}

//获取values集合迭代器，并通过迭代器获取所有的values值
Iterator<String> values = map.values().iterator();
while (values.hasNext()){
    Log.i(TAG, "value = " + values.next());
}

//获取key、value集合迭代器，并通过迭代器获取所有的key、value值
Iterator<Map.Entry<String,String>> entryIterator = map.entrySet().iterator();
while (entryIterator.hasNext()){
Map.Entry<String,String> entry = entryIterator.next();
    Log.i(TAG, "key = " + entry.getKey() + " value = " + entry.getValue());
}
复制代码

  仔细观察一下他们的使用方式，不难发现通过调用这三种方法获取到的Set集合都为我们提供了对应的迭代器来遍历HashMap，并且遍历数据的顺序都是从HashMap数组的第一个下标上的链表或者树开始依次进行遍历。看一下三种方式获取迭代器的源码：

keySet获取迭代器源码

public final Iterator<K> iterator() { 
    return new KeyIterator(); 
}
复制代码

values获取迭代器源码

public final Iterator<V> iterator() { 
    return new ValueIterator();
}
复制代码

entrySet获取迭代器源码

public final Iterator<Map.Entry<K,V>> iterator() {
        return new EntryIterator();
}
复制代码

  在获取迭代器方法中并没有做过多的事情，仅仅只是生成了一个对象而已。我们继续看一下三种不同对象的异同：

//获取key值迭代器
final class KeyIterator extends HashIterator
    implements Iterator<K> {
    public final K next() { return nextNode().key; }
}
//获取values迭代器
final class ValueIterator extends HashIterator
    implements Iterator<V> {
    public final V next() { return nextNode().value; }
}
//获取entrySet地带起
final class EntryIterator extends HashIterator
    implements Iterator<Map.Entry<K,V>> {
    public final Map.Entry<K,V> next() { return nextNode(); }
}
复制代码

  从源码的角度来看这三个真正实现迭代器的类中也没有做什么事情，仅仅只是调用了nextNode方法来获取node节点而已。不过他们都实现了HashIterator这个类，所以想都不用想最后的实现肯定在HashIterator这个类中。ok，不要停下来我们继续去看HashIterator类的源码部分：

abstract class HashIterator {
    Node<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot
    //在构造方法中会在HashMap的数组中找到第一个存在node节点的下标，也就是不为null的坐标
    HashIterator() {
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { 
            //通过while循环的方式遍历数组，当遇到数组下标没有元素的时候则直接跳过
            //存在元素的时候则跳出循环
            do {
                
            } while (index < t.length && (next = t[index++]) == null);
        }
    }
    //判断当前数组中是否存在数据
    public final boolean hasNext() {
        return next != null;
    }
    //在keySet、values和entrySet三个方法中获取到迭代器之后调用next方法都会调用到该方法中
    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        //记录当前node节点，并获取下一个需要被获取到的node节点
        if ((next = (current = e).next) == null && (t = table) != null) {
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        //返回当前节点
        return e;
    }
    ........
}
复制代码

  看完源码是不是发现迭代器的实现原理so easy，本质上就是遍历数组和遍历链表，然后将遍历到的node节点返回给用户。在看完迭代器的实现原理之后不知道大家是否遇到过这样的建议，就是一定要使用entrySet获取key、value值而不是先通过keySet获取到key值然后再通过get(key)的方式获取value值。从上面的源码就能看出因为第二种方式会两次遍历HashMap中的数组和链表。

7、删除node节点

  有了前面的基础了，其实猜也能够猜到remove方法是如何实现的。无非就是通过key对应的hash值找到对应的数组下标，然后遍历该数组下标上的链表或者树找到key值相同的node节点，然后将该node节点从树或者链表中移除，最后将size--。有兴趣的可以自己去找源码看一看，完全能够看懂。

8、红黑树

  因为篇幅有限，所以这里简单的简介一下什么是红黑树，不过并不代表它不重要，在面试过程中也可能会被高频问到，有兴趣的可以自己百度一下或者在掘金上面搜索一下。

8.1、定义

  红黑树是一种近似平衡（指所有叶子节点深度基本相同）的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一倍。

8.2、特点

（1）树中任意两条路径中的节点数相差不会超过一倍；

（2）每个节点要么是红色要么是黑色；

（3）红色节点不能连续，必须有两个黑色的子节点；

（4）对于每个节点，从该点至null的任何路径，都含有相同个数的黑色节点；

（5）每个叶节点都是黑色（NIT或者NULL节点）；

8.3、旋转方式

（1）左旋：该过程是将x的右子树绕x逆时针旋转，使得x的右子树成为x的父节点，x右子树的左节点成为x的右节点；同时修改相关节点的引用；

（2）右旋：该过程是将x的左子树绕x顺时针旋转，使得x的左子树成为x的父节点，x的左子树的右节点成为x的左节点，同时修改相关节点的引用；

  关于红黑树的讲解推荐大家一篇图解红黑树文章：

   juejin.im/post/5a27c6…

二、HashMap之jdk1.7版本源码解析

1、jdk1.7和jdk1.8上相同点

  在文章开头我们提到了他们的不同点，这里简单说一下他们的相同点：

  （1）都是会通过数组加链表的方式存储数据；

  （2）存储的节点都实现了Map.Entry类；

  （3）都提供了get、keySet、values以及entrySet等方法来获取数据并且都是在HashIterator这个类中通过遍历数组和链表的方式来获取数据;

2、源码解析

2.1、put方法

  在put方法中也涉及到了数组初始化，查找相同key值节点，数组扩容，生成新的节点然后将新的节点插入到链表头部等步骤。这期间与jdk1.8对比主要就是少了红黑树步骤。

public V put(K key, V value) {
    //首先判断是否经初始化，如果没有初始化则初始化
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    //存储key为null的情况，其实也就是将该数据存储到下标为0的位置
    if (key == null)
        return putForNullKey(value);
    //获取key值的hash值
    int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
    //获取key值的hash值对应的数组下标
    int i = indexFor(hash, table.length);
    //遍历该数组下标中的链表中是否存在和当前key值相同的node节点，如果存在
    //则直接替换该node节点中的value值，并返回旧的value值
    for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    //构造新的HashMapEntry节点用于存储key、value值并将该节点插入到链表头部
    addEntry(hash, key, value, i);
    //返回null说明不存在和要插入的key中相同的节点
    return null;
}
复制代码

2.2、inflateTable方法

  在该方法中主要是计算数组大小以及阀值，并初始化数组

private void inflateTable(int toSize) {
    //获取数组大小
    int capacity = roundUpToPowerOf2(toSize);
    //计算阀值
    float thresholdFloat = capacity * loadFactor;
    //阀值最大值是2的30次方加1
    if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
        thresholdFloat = MAXIMUM_CAPACITY + 1;
    }
    threshold = (int) thresholdFloat;
    //初始化数组
    table = new HashMapEntry[capacity];
}
复制代码

2.3、addEntry方法

  构造新的节点，并将新的节点插入到链表的头部，新建节点之前首先会判断当前达到了扩容的临界点。

void addEntry(int hash, K key, V value, int bucketIndex) {
    //如果size大于等于了阀值，则说明达到了扩容的临界值，说明需要扩容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        //将原数组大小增大为原来的两倍
        resize(2 * table.length);
        hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    //新建节点，并将新的节点插入到链表头部
    createEntry(hash, key, value, bucketIndex);
}

 void createEntry(int hash, K key, V value, int bucketIndex) {
    //获取key值对应的数组下标的节点
    HashMapEntry<K,V> e = table[bucketIndex];
    //构造一个新的节点，并将上一个当前数组下标节点作为新节点的next节点
    table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
    size++;
}
复制代码

2.4、resize方法

  首先会根据新的数组大小生成新的数组，然后根据新的数组长度以及每个节点的hash值重新计算所有节点在数组中的位置。

void resize(int newCapacity) {
    HashMapEntry[] oldTable = table;
    int oldCapacity = oldTable.length;
    //判断旧数组长度是否等于了允许的最大数组长度，如果是则不允许再扩容
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    //生成新的数组大小
    HashMapEntry[] newTable = new HashMapEntry[newCapacity];
    //遍历数组和链表中所有的节点，并计算所有节点的在数组中下标，然后将
    transfer(newTable);
    table = newTable;
    //重新计算阀值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
 //在该方法中会去遍历HashMap中所有的节点
 //然后根据新数组长度以及节点的hash值重新计算每个节点在数组中的下标
 //最后以头插法的方式存储节点
 void transfer(HashMapEntry[] newTable) {
    int newCapacity = newTable.length;
    for (HashMapEntry<K,V> e : table) {
        while(null != e) {
            HashMapEntry<K,V> next = e.next;
            int i = indexFor(e.hash, newCapacity);
            //以头插法的方式插入节点
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}
复制代码

2.5、小结

  看完整个put方法的执行流程，会发现在jdk1.8上的实现方式虽然在流程上大致相同，不过整体的实现方式却大相径庭。

（1）在jdk1.7中并没有红黑树的概念；

（2）插入元素是头插法的方式，所以在多线程下可能会导致循环链表；

（3）在resize数组的时候，是遍历数组和链表中所有的节点，并在遍历的过程中根据新的数组长度和节点的hash值重新计算节点的下标，然后以头插法的方式将节点插入到新到数组中。而在jdk1.8上则是采用的高位和低位的方式来计算节点的下标的；

2.6、获取数据

  在jdk1.7上获取数据的方式和jdk1.8上基本上来说是相同的，最后都是通过调用到HashIterator类中，依次遍历数组和链表来获取到节点信息的。所以这里就不在多讲。

三、总结

  对于jdk1.7和jdk1.8上的HashMap而言，其主要的区别就是在jdk1.8上新增了红黑树，提高了数据的查询效率，让本来需要O(n)的时间效率优化为了O(logn)；当然为了解决jdk1.7上多线程resize的时候出现循环链表的情况，将头插法变更为了尾插法。并且在jdk1.8上resize的时候采取了高位和低位的算法来计算节点在新数组中的下标位置。

  此外，他们都采用了数组加链表的方式存储数组，并且节点都实现了Map.Entry，并且在通过迭代器获取数据的时候都是通过从前向后依次遍历数组和链表中的节点来实现的。