HashMap浅析
1. 简介
HashMap是Java编程中常用的数据结构类，属于JDK自带的非常好用的类，使用它可以解决Java编程中的很多问题。今天来聊一下其源码，了解一下好的哈希映射是如何实现的。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。哈希映射需要解决的主要有2个问题，哈希函数和解决冲突。哈希函数就是将一个映射的键值（key）通过某种计算，使其对应到数组的一个位置。解决冲突则是在多个key都被对应到同一个数组位置的时候，如何存储这些映射。
2. HashMap实现概述
JDK自带的HashMap主要使用数组，每个数组元素中，使用链表存储冲突的映射。并且数组大小可以根据加入的映射数量动态扩展大小，并且数组大小都是2的幂函数。当然，采用链表存放冲突的映射，当链表太长了之后，就会在查找key的过程消耗过多时间。JDK1.8开始引入红黑树来解决链表过长的问题，当链表长度达到设定阈值时，将线性的链表转换为红黑树，提升其查找性能。在JDK1.8中，这个阈值被设定为8。并且，当删除映射时，一颗红黑树元素少于6，就会将树结构重建为线性链表。不过需要注意的是，要转换为红黑树，不仅仅需要链表长度达到8，还需要数组的长度大于64，否则，HashMap会认为，总共最多64*8=512个元素不足以达到需要建立树结构的需要，这时候只做一下扩容操作即可。至于数组大小，如果创建HashMap的时候没有指定，默认大小是16，并且每次扩容都在原来基础上乘以2。所以，如果以初始状态算起，扩容2次之后，达到64长度的数组，如果这时候再出现链表长度达到8，就需要进行转红黑树的操作了。
2.1 哈希函数
HashMap在计算hash值的时候，首先调用了key对象的hashCode()获取其hash1值。再对hash1做二进制无符号向右移16位操作（hash1 >>> 16）得到h（将hash1高位的16位移到低位，高位补0）。再将移位后的值和hash1做按位与操作（hash1 & h），得到此映射的hash值hash2。在计算对应数组索引的时候，再用数组table的长度length减去1，和hash2做按位与操作（(table.length - 1) & hash2）得到数组索引p，table[p]就是对应存放该映射的数组元素。
2.2 解决冲突
在冲突的映射还不多的时候，采用拉链法解决冲突，具体是一个单链表，新加入的映射采用尾插法插入链表尾部。
当冲突元素也就是链表长度达到8，并且数组长度不小于64时，将当前这个冲突元素的链表转换为红黑树。关于红黑树的具体实现细节过于复杂，在这篇文章就不展开了，以免影响对HashMap的整体理解。
2.3 扩容过程
对于HashMap的扩容过程，也很简单。创建一个新的数组newTable，其大小（newCap）为之前的2倍，之前的数组大小称为oldCap，（newCap = oldCap * 2）。
如果数组元素为普通链表，则将链表分为两个链表，第一个链表是hash值与原数组长度按位与操作结果为0（(hash & oldCap) == 0），第一个链表在新数组中的索引和原数组相同（j）。第二个链表是不符合第一个链表条件的元素组成的（(hash & oldCap) != 0），第二个链表在新数组中的索引是原数组中索引加上原数组大小（j + oldCap）。
如果数组元素为红黑树，则遍历所有节点将（(hash & oldCap) == 0）的节点分到第一个链表，其余分到第二个链表。然后根据链表长度，如果链表长度小于等于6，将红黑树退化为普通链表；否则重建红黑树。
将所有原来数组中的链表都分开并存入新的数组，扩容过程就算完成了。
