一、简介

HashMap是Java程序员使用频率最高的用于映射(键。值对)处理的数据类型。随着JDK（Java Developmet Kit）版本的更新，JDK1.8对HashMap底层的实现进行了优化，要想使用好它，首先你要了解它的原理以及底层的实现

二、HashMap的数据结构

我们通过上图可以看出来，HashMap底层是通过数组+链表+树来实现的。实际上每个节点存放数据的话是一个Node，我们来看一下Node 在jdk 1.8中具体的代码

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是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。上图中的每个黑色圆点就是一个Node对象。废话不多说我们先来介绍一下HashMap中最重要的三个方法，put、get、以及扩容。先了 解一下工作原理，具体的细节我们会通过源码来分析。

我们平时使用 map.put("lisnail","程序猿")内部是如何工作的呢。首先会调用Key 的hashCode()方法得到hashCode值。然后再通过hash算法的高位运算和取模来确定该key 所对应桶的位置。有时两个key会定位到相同的位置，那么就表示Hash发生了碰撞。然后将冲突的元素插入到链表的末尾。map.get("lisnail") 又是怎么工作的呢。首先也会通过hash值来确定桶的位置，找到位置 以后，然后会通过equals(key)具体的来确定是哪个值。HashMap 是如何进行扩容的呢。那首先要认识几个参数

//所能容纳 key-value 个数的极限，当Map 的size > threshold 会进行扩容int threshold;//HashMap 默认的桶数组的大小static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16//负载因子，在扩容的时候用到static final float DEFAULT_LOAD_FACTOR = 0.75f;

我们在往HashMap中put数据的时候，会检查size的大小，如果size > threshold 的话，会进行扩容操作，扩容后的 哈希桶数组大小是原来的两倍，那么threshold也变成了原来的两倍。值得我们注意的是，在HashMap中 ，哈希桶数组的大小永远是2的n次方。这是一种非常规的设计，常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数的。Hashtable初始化桶大小为11，为什么HashMap采用这种非常规的设计呢？主要是为了在取模和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。

这里存在一个问题，即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。于是，在JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能

三、HashMap源码分析

HashMap的源码确实挺多的，内容有限，我们就根据key获取哈希桶数组索引位置、put方法，get方法的详细执行、扩容过程，这个几个具有代表性的点来看一下源码的具体实现。

确定哈希桶数组索引位置

不管是增加、删除、查找，都需要定位到哈希桶的数组位置，这是很关键的一步，前面也说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍历链表，大大优化了查询的效率。下面就来看一下源码

//JDK1.8的Hash算法static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}//这部分代码虽然在 JDK1.8中没有了,但是实现原理是一样的，这是Jdk1.7中又的代码static int indexFor(int h, int length) { return h & (length-1);}

这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。

这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h & (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。怎么理解呢，比如说n=16 n-1的二进制为“...0001111”, n = 8 那么 n-1 的二进制 “...000111"的数，n = 4 n-1 的二进制 为 “...0011”,依次类推。这样的话，高位都是0，只有低位的1决定结果。就相当于对 h进行求模运算。通过hashCodt()的高16位异或低16位实现hash算法(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

我们来拿个例子说明，下面是我通过工具，根据jdk的源码进行的运算结果，后面一张图是我通过IDEA打断点或得到的值。结果是一样的，最后“name”这个key对应桶的index 为8.

Map map = new HashMap(); map默认哈希桶数组是16

map.put("name","lisnail");

hashCode = "name".hashCode(); 可以利用工具看到"name"的HashCode是 3373707,然后通过工具转成二进制得到下面的二进制 HashCode

0000 0000 0011 0011 0111 1010 1000 1011 hahsCode  ^ 0000 0000 0000 0000 0000 0000 0011 0011 hahsCode>>>16 ————————————————————————————————0000 0000 0011 0011 0111 1010 1011 1000 hashCode^hashCode>>>16  &0000 0000 0000 0000 0000 0000 0000 1111 HashMap.size() ————————————————————————————————0000 0000 0000 0000 0000 0000 0000 1000  转成十进制是 8

扩容机制

废话不多说，直接上代码 下面的代码是JDK 1.7的源码，我们对比着 1.7 和 1.8 来看一下 1.8中做了什么优化。

void resize(int newCapacity) { //传入新的容量Entry[] oldTable = table; //引用扩容前的Entry数组int oldCapacity = oldTable.length;if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了return;}Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组transfer(newTable); //！！将数据转移到新的Entry数组里table = newTable; //HashMap的table属性引用新的Entry数组threshold = (int)(newCapacity * loadFactor);//修改阈值}void transfer(Entry[] newTable) {Entry[] src = table; //src引用了旧的Entry数组int newCapacity = newTable.length;for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组Entry<K, V> e = src[j]; //取得旧Entry数组的每个元素if (e != null) {src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）do {Entry<K, V> next = e.next;int i = indexFor( e.hash, newCapacity ); //！！重新计算每个元素在数组中的位置e.next = newTable[i]; //标记[1]newTable[i] = e; //将元素放在数组上e = next; //访问下一个Entry链上的元素} while (e != null);}}}

newTable[i]的引用赋给了e.next，也就是使用了单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到Entry链的尾部。而且每次都会重新去计算元素的index。

我们来看一下 JDK1.8的源码

final Node<K,V>[] resize() {//旧的哈希桶数组Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;//旧的 扩容临界点大小int oldThr = threshold;int newCap, newThr = 0;//如果HashMap中有元素if (oldCap > 0) {// 超过最大值就不再扩充了，就只好随你碰撞去吧if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}// 没超过最大值，就扩充为原来的2倍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 thresholdnewCap = oldThr;else {// zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 计算新的resize上限if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}/**上面的操作可以总结为：如果是最开始还没有元素的情况下：1.你在初始化HashMap的时候传入了参数HashMap(initCapacity)那么 threshold =initCapacity * 0.752.则就按默认的算 initialCapacity = 16，threshold = 12如果已经有元素了，那么直接扩容2倍，如果oldCap >= threshold了，那么threshold也扩大两倍*/threshold = newThr;Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) {// 把每个bucket都移动到新的buckets中for (int j = 0; j < oldCap; ++j) {Node<K,V> e;//将原来map中非null的元素rehash之后再放到newTab里面去if ((e = oldTab[j]) != null) {oldTab[j] = null;//如果这个oldTab[j]就一个元素，那么就直接放到newTab里面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 {// 链表优化重hash的代码块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;elseloTail.next = e;loTail = e;}// 原索引+oldCapelse {if (hiTail == null)hiHead = e;elsehiTail.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;}

通过源码我们可以看到有这么一段(e.hash & oldCap) == 0，其实关键点就在这里。

我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位 置。我们知道index的位置= key.hash&(oldCap -1)

扩容之前 160000 0000 0011 0011 0111 1010 1011 1000 key1(key的hash&hash>>>16) 0000 0000 0011 0011 0111 1010 1010 1000 key2(key的hash&hash>>>16) &0000 0000 0000 0000 0000 0000 0000 1111 HashMap.size() key1: 1000 转成十进制 8key2: 1000 转成十进制 8扩容之后 320000 0000 0011 0011 0111 1010 1011 1000 key1(key的hash&hash>>>16) 0000 0000 0011 0011 0111 1010 1010 1000 key2(key的hash&hash>>>16) &0000 0000 0000 0000 0000 0000 0001 1111 HashMap.size() key1: 11000 转乘二进制 24=16+8key2: 1000 转乘二进制 8

我们可以看出,JDK1.8中扩容之后元素的位置，要不然是在原来的位置,要不然就是在 原来位置+扩容之前的哈希桶数组大小，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。e.hash & oldCap) == 0，这个判断条件就是看那个新增的bit位是0 还是1。这样既省去了重新计算hash值的时间，同时新增的bit位是0还是1是随机的，因此在扩容的时候把原本hash冲突的一些节点，分散到了各个桶中。

put方法

从网上找到了一个流程图，感觉很不错，就直接拿过来用了，嘿嘿.... 画的也是比较清楚的。看着流程图，再结合源码一看就明白。

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，否则执行resize()进行扩容if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;/**根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加*/if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;//如果你插入的key已经存在，就覆盖原来key 所对应的值。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);else {//循环桶对应的链表,将节点插入到链表末尾for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);//如果链表的长度大于7，就把节点转成树节点if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}//如果你插入的key已经存在，就覆盖原来key所对应的值。if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) {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方法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;//判断HashMap是否为空、桶数组中第一个Node节点是否为空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;}

其实get方法是比较简单的，只要明白如何找到桶的位置，其他的不难理解。

四、小结

(1) 扩容是一个很耗费性能的操作，我们最好在使用hashMap的时候给定HashMap一个大致的初始值。

(2) 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。

(3) HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。

参考

美团、

csnd、