乐趣区

关于java:HashMap基础知识

jiezi

明天来讲一个陈词滥调，都被讲烂的一个问题，网上轻易一搜 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() 函数

退出移动版