HashMap源码解析

老样子话不多说先上一张UML类图

看一下里面的方法，我们抽重点的和常用的讲

HashMap的构造方法

HashMap()方法

//负载因子final float loadFactor;//默认负载因子为0.75static final float DEFAULT_LOAD_FACTOR = 0.75f;public HashMap() {	this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}

HashMap(int initialCapacity) 指定初始化容量大小其实是调用了HashMap(int initialCapacity, float loadFactor)方法

//阈值--所能容纳的key-value对极限 threshold = length * Load factorint threshold;public HashMap(int initialCapacity) {	//传入初始化容量和负载因子    this(initialCapacity, DEFAULT_LOAD_FACTOR);}//this调用的方法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;    //tableSizeFor是java8对hashMap进行的优化之一    this.threshold = tableSizeFor(initialCapacity);}//返回大于输入参数且最近的2的整数次幂的数// >>> 操作符表示无符号右移，高位取0// | 按位或运算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(Map<? extends K, ? extends V> m)

//初始化使用，长度总是 2的幂transient Node<K,V>[] table;public HashMap(Map<? extends K, ? extends V> m) {	//默认负载因子0.75    this.loadFactor = DEFAULT_LOAD_FACTOR;    putMapEntries(m, false);}final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {	//传入集合的大小    int s = m.size();    if (s > 0) {    	//说明是拷贝构造函数来调用的putMapEntries，或者构造后还没放过任何元素        if (table == null) { // pre-size        	//先不考虑容量必须为2的幂，那么下面括号里会算出来一个容量，使得size刚好不大于阈值。这样会算出小数来，作为容量就必须向上取整，所以这里要加1            float ft = ((float)s / loadFactor) + 1.0F;            //如果小于最大容量，就进行截断；否则就赋值为最大容量            int t = ((ft < (float)MAXIMUM_CAPACITY) ?                     (int)ft : MAXIMUM_CAPACITY);            //在算出来的容量t > 当前暂存的容量(容量可能会暂放到阈值上的)                  if (t > threshold)            	//用t计算出新容量，再暂时放到阈值上                threshold = tableSizeFor(t);        }        //说明table已经初始化过了；判断传入map的size是否大于当前map的threshold，如果是，必须要resize        else if (s > threshold)        	//扩容            resize();        //        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {            K key = e.getKey();            V value = e.getValue();            //可能也会触发resize            putVal(hash(key), key, value, false, evict);        }    }}//扩容（重中之重）//resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块也是JDK1.8新增的优化点final Node<K,V>[] resize() {	//非常重要的一个字段，哈希桶数组    Node<K,V>[] oldTab = table;    //原数组如果为null，则长度赋值0    int oldCap = (oldTab == null) ? 0 : oldTab.length;    int oldThr = threshold;    int newCap, newThr = 0;    //如果原数组长度大于0    if (oldCap > 0) {    	//数组大小如果已经大于等于最大值        if (oldCap >= MAXIMUM_CAPACITY) {        	//修改阈值为int的最大值，这样以后就不会扩容了            threshold = Integer.MAX_VALUE;            return oldTab;        }        //原数组长度大于等于初始化长度16，并且原数组长度扩大1倍也小于2^30次方        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                 oldCap >= DEFAULT_INITIAL_CAPACITY)            // 阀值扩大1倍            newThr = oldThr << 1; // double threshold    }    //旧阀值大于0，则将新容量直接等于旧阀值     else if (oldThr > 0) // initial capacity was placed in threshold        newCap = oldThr;    //阀值等于0，oldCap也等于0（集合未进行初始化）    else {               // zero initial threshold signifies using defaults    	//数组长度初始化为16        newCap = DEFAULT_INITIAL_CAPACITY;        //阀值等于16*0.75=12        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;    //把每个bucket都移动到新的buckets中    if (oldTab != null) {        for (int j = 0; j < oldCap; ++j) {            Node<K,V> e;            if ((e = oldTab[j]) != null) {            	//元数据j位置置为null                oldTab[j] = null;                //数组下一个引用为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;                        }                        //原索引+oldCap                        else {                            if (hiTail == null)                                hiHead = e;                            else                                hiTail.next = e;                            hiTail = e;                        }                    } while ((e = next) != null);                    //原索引放到bucket里                    if (loTail != null) {                        loTail.next = null;                        newTab[j] = loHead;                    }                    //原索引+oldCap放到bucket里                    if (hiTail != null) {                        hiTail.next = null;                        newTab[j + oldCap] = hiHead;                    }                }            }        }    }    return newTab;}

我们调用put方法的时候首先会对key进行hash确定这个Entry插入的位置，这个Entry就会插入到该位置下，当这个HashMap插入的Entry越来越多的时候就难免会发送hash冲突这样就可以用链表取解决了。当链表长度大于8，数组长度大于64就会转化成红黑树。

其实HaspMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点，每一个Entry对象通过Next指针指向下一个Entry对象，这样，当新的Entry的hash值与之前的存在冲突时，只需要插入到对应点链表即可。

需要注意的是，jdk1.8以后Entry节点采用的是“头插法”，而不是“尾插法”。

public V put(K key, V value) {	//先对key进行hash,然后进行添加    return putVal(hash(key), key, value, false, true);}static final int hash(Object key) {    int h;    //1 取key的hashCode的值    //2 高位参与运算：h>>>16    //3 取模运算（在后面有用到）    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 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;    //如果table为null或者长度为0，则进行初始化    if ((tab = table) == null || (n = tab.length) == 0)        n = (tab = resize()).length;    //取模运算    if ((p = tab[i = (n - 1) & hash]) == null)    	//tab[i] 为null，直接将新的key-value插入到计算的索引i位置        tab[i] = newNode(hash, key, value, null);    else {//tab[i] 不为null，表示该位置已经有值了        Node<K,V> e; K k;        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))            //节点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);				                    //链表长度大于8，转换成红黑树                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                        treeifyBin(tab, hash);                    break;                }                //key已经存在直接覆盖value                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;    //超过最大容量，进行扩容    if (++size > threshold)        resize();    afterNodeInsertion(evict);    return null;}

我们调用get()方法的时候首先会对这个key进行hash确认他在数组上的bucket的位置，但是同一个位置可能存在多个Entry，这时就要从对应链表的头节点开始，一个个向下查找，根据equals()直到找到对应的Key值，这样就获得到了所要查找的键值对。

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) {        //根据key计算的索引检查第一个索引        if (first.hash == hash && // always check first node            ((k = first.key) == key || (key != null && key.equals(k))))            return first;        //第一个节点不为null        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;}

public V remove(Object key) {    Node<K,V> e;    return (e = removeNode(hash(key), key, null, false, true)) == null ?        null : e.value;}final Node<K,V> removeNode(int hash, Object key, Object value,                               boolean matchValue, boolean movable) {    Node<K,V>[] tab; Node<K,V> p; int n, index;    //(n - 1) & hash找到桶的位置    if ((tab = table) != null && (n = tab.length) > 0 &&        (p = tab[index = (n - 1) & hash]) != null) {        Node<K,V> node = null, e; K k; V v;         //如果键的值与链表第一个节点相等，则将 node 指向该节点        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))            node = p;        //如果桶节点的下一个节点不为空        else if ((e = p.next) != null) {        	//节点为红黑树            if (p instanceof TreeNode)            	//找到需要删除的红黑树节点                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);            else {            	//遍历链表，找到待删除的节点                do {                    if (e.hash == hash &&                        ((k = e.key) == key ||                         (key != null && key.equals(k)))) {                        node = e;                        break;                    }                    p = e;                } while ((e = e.next) != null);            }        }        //删除节点，并进行调节红黑树平衡        if (node != null && (!matchValue || (v = node.value) == value ||                             (value != null && value.equals(v)))) {            if (node instanceof TreeNode)                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);            else if (node == p)                tab[index] = node.next;            else                p.next = node.next;            ++modCount;            --size;            afterNodeRemoval(node);            return node;        }    }    return null;}

HashMap可以接受null键值和值，而HashTable则不能；

HashMap是非synchronized;HashMap很快；以及HashMap储存的是键值对等等。HashMap的工作原理 ：HashMap是基于散列法（又称哈希法）的原理，使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket（桶）位置来储存Entry对象。HashMap是在bucket中储存键对象和值对象，作为Map.Entry。并不是仅仅只在bucket中存储值。hash碰撞的原因和解决方法：

原因： 当两个对象的hashcode相同，所以它们的bucket位置相同，‘碰撞’会发生。

解决办法： Java中HashMap采用了链地址法。链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。系统将调用这个key的hashCode()方法得到其hashCode 值（该方法适用于每个Java对象），然后再通过Hash算法的后两步运算（高位运算和取模运算）来定位该键值对的存储位置（HashMap在链表中存储的是键值对），有时两个key会定位到相同的位置，表示发生了Hash碰撞。

Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高。如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组（Node[] table）占用空间又少呢？答案就是好的Hash算法和扩容机制。

使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生，提高效率。不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这样的wrapper类作为键是非常好的选择。调整hashMap大小可能出现的问题：

多线程情况下，当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在l链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。（1.8虽然对死循环这块做了优化，但是并没有对多线程做任何处理，所以任然有发生死循环的可能，俩者出现死循环的原因不同罢了）在HashMap中，哈希桶数组table的长度length大小必须为2的n次方(一定是合数)

HashMap的初始容量是2的n次幂，扩容也是2倍的形式进行扩容，是因为容量是2的n次幂，可以使得添加的元素均匀分布在HashMap中的数组上，减少hash碰撞，避免形成链表的结构，使得查询效率降低！

因为现在面试很多面试官必问HashMap，我也是专门花时间读了一下源码，可能理解的还不够透彻，希望我的一点收获可以能帮助到你们，哪怕只有一点点。