明天来讲一个陈词滥调，都被讲烂的一个问题，网上轻易一搜hashmap，各式各样的文章，明天从源码动手带你一行一行地从新理解hashmap。然而重点是放在了自身的原理，至于多线程问题，jdk1.7，1.8的区别，会从新出一篇文章来探讨。

本文解说前默认各位小伙伴是曾经会hashmap的用法的了，怎么样都有过new HashMap<>() 的教训，着重讲的是原理。

工作原理

构造组成

put

  • 首先是或者对插入对象的key的hash指进行扰动失去新的hash值，简略来讲是为了更好的散列
  • 依据hash值找到须要插入值的下标，而后对链表进行相应的操作，在开端插入，hash抵触，转化成红黑树
  • 如果有须要，则进行扩容

get

获取值的时候就比较简单了，间接依据key的hash找到桶的下标，再遍历链表找到值就好了。

留神：key对象自身有个hash值，然而put和get的时候是通过了hash算法进行了扰动生成了新的hash值，然而对象自身的hash值不变。

成员变量

必定是挑重点的说先，其它的有了根底后能够自行去源码中查找学习，这样更有成就感。

外部类-Node

通过一开始也晓得，HashMap 是由数组加链表组成的，其实实质就是多个上面Node<K,V>组成的数组 。

<img src="http://image.imperfect.top/node-hashmap.png" alt="node-hashmap" style="zoom: 50%;" />

其实如同也没啥好讲的，晓得有这么一个类，类外面有那些成员变量就好了。

成员变量

可能有小伙伴会发现了，怎么没有capcity 容量这个成员变量呀。须要留神的是jdk1.8之后，桶数组的初始化不是在构造函数内实现的，而是在第一次put的时候实现的，所以不设capcity这个变量齐全没问题。

构造函数

构造函数大体来说有两种，一种是给成员变量赋值，一种是复制一个新的map

下面有两个函数tableSizeFor() 和putMapEntries() 有趣味的小伙伴能够去看下源码，实现比较简单，这里就不再赘述。

Put

hash()

让咱们来看下put的源码

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

首先运行的是一个hash() 的函数

static final int hash(Object key) {//hash算法    int h;    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

首先int h = key.hashCode() h是一个4字节32位的数，接着是异或上h >>> 16 最初失去了新的hash值。

h是个32位的数，那么它右移16位后，高位（前16位）位0，而x ^ 0 = x。所以整个下面一句话的作用就是保留高位，低位和高位异或，这样子能达到的指标就是扰乱了低位，且低位具备高位的一部分属性。

接下来的重点就到了putVal() ，须要分位第一次put和其它put来讲。

第一次put

第一次put时候的putVal()

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {    Node<K,V>[] tab; Node<K,V> p; int n, i;    if ((tab = table) == null || (n = tab.length) == 0)        n = (tab = resize()).length;    //.....}

当第一次put的时候，table必定是为空的，也就是if ((tab = table) == null || (n = tab.length) == 0) 判断返回为true，走到resize() 流程。

来看看第一次put的时候resize是怎么运作的

通过源码能够看到真正的table数组是在第一次put中的putVal() 中的resize() 时才初始化。

失常put

看源码，首先会有一个依据hash计算该key应该放在哪个桶上面，n是桶数组的长度，永远是2的幂。 反映在二进制就是只有某一位是1，其它全是0。这样的状况下，n - 1就是尾部全是1，其它全是0。（n - 1） & hash就是保留hash值中数组长度低位的数，高位的数置0。

假如n = 16，那么n - 1 = 15 = 00001111，这样与上hash相当于只保留了hash的后4位。

扩容

能够发现上述源码中在最初还有一个resize() ，可见resize() 除了初始化的时候有用，更多时候是用在扩容这方面。

下面源码正文中也有写到是当k-v个数 > 扩容阈值 = table数组容量 * 负载因子（默认是0.75）的时候开始扩容，table数组变成原来的2倍，旧k-v从新散列在新数组中。

我把前面的拆开来说，因为其一是因为其奇妙，其二是因为太长了看着疲乏

能够提前说下，jdk的思维是把链表拆分成两局部进行散列。想拆成2局部必须用hash通过某种运算失去两种后果，计算机外面天然就想到了0，1。一个数和另一个数失去0和1，所以能够想到&运算，且其中一个数只有1位是1，其它都是0。

所以算法就是那hash（留神，是扰动前的hash）& newCap 这样失去的后果就只有0和1了。

Get

相比之前的插入和扩容函数，get() 相对来说就简略了

public V get(Object key) {    Node<K,V> e;    return (e = getNode(hash(key), key)) == null ? null : e.value;}

能够看到最终是到了getNode() 函数