HashMap部分源码的理解

上个星期在学习单列集合HashSet的时候,发现其底层的实现都是依赖于HashMap,于是就先看了看HashMap的部分源码,在jdk1.8中确实有点晦涩,建议去先去看看1.7版本（比较适合阅读）;

步入正题,我们都知道HashMap在1.7之前的实现是依赖于数组+链表,但是从1.8开始就采用数组+链表+红黑树.摸着良心说,在没看源码之前我也只知道这么点(哈哈,看完源码之后,我连这么点都忘记了,或许这就是太极.....),别看平时使用频繁但是对于实现过程却一点都不了解,你看Java面向对象的概念是不是很牛逼，底层如何实现都给你封装好了...

1、底层数据结构

数组作为一种基本的数据结构，可以根据索引查找对应的元素，为此查询与修改的效率都是非常高的，在JDK1.7之前，HsahMap底层数据结构采用数组+链表实现，在Jdk8采用数组+链表+红黑树;

首先，既然有了数组，那为什么还有使用链表呢？这个就跟如何确定HashMap对象在数组中的位置有关系，在源码中可以知道是根据 （数组.length -1） & hash(key) 得到该Node<k,v>对象存放的地址值，这样就可以将Node对象均匀的分布在数组上，但是可能会由于hashCode码不相同，经过计算之后会得到相同索引位置（哈希冲突），要是二个Node对象都需要添加到数组中的同一位置，那这个该如何实现呢？为此采用了链表结构，既然我们都摆放在数组中的同一位置，Node对象是根据key的唯一性去获取对应的value,那么是否能再多添加一个属性，记录前面或者后面Node对象，这样就可以就可以将哈希冲突的Node对象用链表挂起来了，在HsahMap中使用的是单向链表，只需要记录后一个Node对象就可以了;

那么随之又引发了另一个问题，在链表加入元素的时候，是从头部加入还是尾部加入？在jdk7的源码中实现是从头部加入，然后将链表整体下移一位。为什么要从头部加入？因为如果是在链表的尾部加入，那么就需要先遍历链表，找到尾节点，时间复杂度为O(n),但是从头节点插入，只需要将插入对象的next指向原来的头节点即可。为什么要下移？如果不下移，那么根据hash值获取到索引位置，然后遍历链表，但是链表中node对象永远都是指向下一个节点，不能向前查询，这样就会导致无法获取到想要寻找的元素；在jdk8是将node对象加入到链表的尾部，因为在加入到链表的时候，会进行遍历判断是否需要转换成红黑树，既然要遍历那就顺便给元素加到链表尾部；

为什么要动态将链表转换成红黑树？要是哈希冲突很严重，在某个链表上面的对象超过了阀值，这样就会导致在查询的时候需要去遍历很长的链表，时间复杂度为O(n),要解决查询效率的问题，那么就需要换一个数据结构来实现了，为此采用了红黑树，时间复杂度为O(logn)。那什么时候链表才转换成红红黑树？从源码中可以看出，当链表长度大于 8 且 node对象的数量大于64才会转换成红黑树，因为在当node对象的数量小于64的时候，选择扩容也可以将node对象重新均匀的分布在数组上面，当红黑树中的node对象数量少于6个，就会从树转换成链表结构，下面我们将从部分源码分析出上面的总结:

2、哈希桶与红黑树

说实话,我也不知道啥叫哈希桶,或许就是对某种数据结构的定义吧,千万不要被这高大上的名字给吓唬到,下面我们看看代码中实现所谓的实现

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);
   }
   public final V setValue(V newValue) {
       V oldValue = value;
       value = newValue;
       return oldValue;
   }
   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;
   }
}
复制代码

分析:这个Node对象中存在四个属性,分别是hash、key、value、next，至于为什么要这样设计？我们可以简单的思考下，这个hash是不是可以做为数组的索引？但是hash重复了,在数组中不可能在同一个索引放至二个对象,那么就需要链表了,既然咋们的索引相同,为了让你有个落脚的地方，那你就挂在我后面就可以了，这就是通过next记载下一个节点对象;

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);
   }
 //其它方法略  
} 
复制代码

啥？这就是哈希桶和红黑树的代码实现？一看操作猛如虎，一看战记 0-5,说是迟,那是快，几个呼吸之间,已经开始看HashMap中的成员变量了......

3、 HashMap中成员变量的含义？

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
   private static final long serialVersionUID = 362498820763181265L;
   //默认初始化容量
   static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
   //最大容量阀值
   static final int MAXIMUM_CAPACITY = 1 << 30;
   //默认加载因子
   static final float DEFAULT_LOAD_FACTOR = 0.75f;
   //链表树化的阀值
   static final int TREEIFY_THRESHOLD = 8;
   //不树化的阀指
   static final int UNTREEIFY_THRESHOLD = 6;
   //最小树化的容量
   static final int MIN_TREEIFY_CAPACITY = 64;
   //数组
   transient Node<K,V>[] table;
   //键值对
   transient Set<Map.Entry<K,V>> entrySet;
   //HashMap中元素的个数  (相当于是一个计数器)
   transient int size;
   //被修改的次数
   transient int modCount;
   //临界值 当实际大小(容量*填充比)超过临界值时，会进行扩容  容量 2的最小幂次方 
   int threshold;
   //加载因子（填充比）
   final float loadFactor;
复制代码

4、Put方法的理解

在这里我们就不讲解构造方法了,要是你细细的去品一品HashMap的源码就会发现,其主要的思想都含在Put方法中，为此我们将通过put方法去了解

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

//1、hash方法，返回一个int类型数值
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//putval方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
	//定义一个Node数组、Node对象、数组的长度、索引  
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //判断数组是否为空
    if ((tab = table) == null || (n = tab.length) == 0)
    	//初始化数组的长度
        n = (tab = resize()).length;
    //判断该数组索引对应位置上是否存在对象   索引是： (n - 1) & hash
    if ((p = tab[i = (n - 1) & hash]) == null)
    	//添加一个Node对象放在数组该索引位置上，并且Node对象的下一个节点为null
        tab[i] = newNode(hash, key, value, null);
   //否则hash冲突，需要判断是更新key对应的value还是添加新key的value,添加的时候还得判断是否需要树化     
    else {
    	//定义一个Node对象
        Node<K,V> e; K k;
        //判断是不是更新key所对应的value   先判断hash是否相同，再判断equals()是有原因的？
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //走到这里就是指添加新key，判断Node对象是否是属于树形结构    
        else if (p instanceof TreeNode)
        	//往红黑树添加元素
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //链表添加元素    
        else {
        	//遍历链表，找到该hash值相同链表下next为null的节点就是尾节点然后指向需要添加的node
            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);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //判断node对象的数量是否大于最大容量
    if (++size > threshold)
    	//扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}

//链表动态转成红黑树方法
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //判断当前哈希桶数组的长度是否小于64
        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);
        }
    }
复制代码

5、扩容长度的方法

final Node<K,V>[] resize() {
    //保存旧的哈希桶数组
    Node<K,V>[] oldTab = table;
    //保存旧的哈希桶数组的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //保存旧的哈希桶数组最大容量
    int oldThr = threshold;
    //定义新的长度与容量
    int newCap, newThr = 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; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    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) {
        //遍历旧哈希桶数组
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                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;
                    do {
                        next = e.next;
                        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;
}
复制代码

6、get方法

//基本思想：先根据  数组.length & Hash(key)获得需要查询位置在数组中索引，该位置的对象是链表还是树，然后根据key寻找对应的node对象，最后返回value   链表是遍历，树是二分查找法
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) {
    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;
}
复制代码