耗时3天写完的HashMap万字解析，争取一篇文章讲透它，面试官看了都直点头！ |
您所在的位置：网站首页 › hashmap的存储原理 › 耗时3天写完的HashMap万字解析，争取一篇文章讲透它，面试官看了都直点头！ |
耗时3天写完的HashMap万字解析，争取一篇文章讲透它，面试官看了都直点头！
|
写在开头 在过去的几篇博客中，我们已经将Collection下的三大接口（List，Set，Queue）学了一遍，那么今天我们即将开启Java中另一大集合类型-Map。 所谓的Map：指的是使用键值对（key-value）存储，类似于数学上的函数 y=f(x)，"x" 代表 key，"y" 代表 value，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值上的一种数据存储结构。 那么在Map的世界里，大概是这样的一个父子继承图谱（不完全），而在日常的开发过程中，使用最多且面试时被问到的频率最高的集合类型要数HashMap，那么好，接下来我们就一起以HashMap来作为开篇，来一起学习一下Map！  在这里插入图片描述 HashMapHashMap是典型的Map类型集合，包含了太多面试考点，我们尽量在这一篇文章中给讲完、讲透，所以文章会有点长，希望小伙伴们能够保持耐心阅读完，有存在问题的地方，可以提出来，咱们一起讨论，有写错的地方也请指出来，build哥有错就改！ 首先，我们先来通过一个小示例，看一下HashMap的增删改查如何使用哈 【代码示例1】 代码语言：javascript复制public class Test { public static void main(String[] args) { HashMap map = new HashMap(); //增 map.put("xiaoming", 18); map.put("xiaohua", 19); //删 map.remove("xiaohua"); //改 map.put("xiaoming", 20); //查 Integer xiaoming = map.get("xiaoming"); System.out.println("xiaoming的年龄:"+xiaoming); //遍历Map for (String s : map.keySet()) { System.out.println(s); System.out.println(map.get(s)); } } }输出： 代码语言：javascript复制xiaoming的年龄:20 xiaoming 20总体来说，HashMap的存储原理就是基于哈希表的数组，只不过这个数组的每个元素中存储的可能是键值对，可能是链表，可能是红黑树，我们在存储键值对的时候（put方法），通过计算键（key）的哈希值找到对应的数组下标，然后将对应的值(value)存入。 这里提到的哈希值可不是简单的重写hashcode()所算出的结果，而是经过扰动之后的结果，通过研究HashMap的底层我们可以获得答案！ HashMap的哈希值实现原理？穿透到HashMap的底层后，我们第一个要寻到答案的就是：哈希值的计算原理第一步：在存储键值对时，我们跟进put()方法的源码中去一探究竟。 【源码解析1】 代码语言：javascript复制public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }从put方法的底层中我们可以看到hash()方法的身影，JDK1.8中的hash方法源码如下： 【源码解析2】 代码语言：javascript复制 static final int hash(Object key) { int h; // key.hashCode()：返回散列值也就是hashcode // ^：按位异或 // >>>:无符号右移，忽略符号位，空位都以0补齐 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }在hash()方法通过一个三目运算符也进行返回值的处理，当key为null时，直接返回一个0值，否则则对key进行hashCode()散列码的计算，并将其与无符号右移16位之后的散列码异或运算。 ^ 运算符： 异或运算符是Java中的一种位运算符，它用于将两个数的二进制位进行比较，如果相同则为0，不同则为1。h >>> 16： 将散列码向右移动16位，int类型的h为32位，为2的32次方，而无符号右移，相当于处于2的16次方，因此是将原来的h值分成了两个16位的部分。经过这一道算法加工，大大的提高了hash值的扰动，使得key能够尽可能分散的存储，有效的减少了哈希碰撞。 如何计算找到key在数组中的位置？虽然在上面我们已经知道了key的哈希值计算原理，但我们仍然没有看到如何将key存入HashMap底层的数组（初始容量为16的数组）中的，我们进入到源码解析1中的putVal()中一看便知！ 【源码解析3】 代码语言：javascript复制final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // 数组 HashMap.Node[] tab; // 元素 HashMap.Node p; // n 为数组的长度 i 为下标 int n, i; // 数组为空的时候 if ((tab = table) == null || (n = tab.length) == 0) // 第一次扩容后的数组长度 n = (tab = resize()).length; // 计算节点的插入位置，如果该位置为空，则新建一个节点插入 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); }源码中通过(n - 1) & hash 获取key最终在HashMap中的存储的数组下标位置，也就是数组长度减一和hash值进行与运算。 这里其实有一个很细小的知识点，在很多Java面试时被提及，就是 为什么采用位运算而不是直接进行取余操作（符号：%）。 首先，我们先来解释一下为什么需要进行这一步的操作，在上面我们提到哈希值其实是一个int类型，4字节，范围从-2147483648 到 2147483648，这里足足有40亿个映射空间，经过右移和异或操作后，理论上的哈希碰撞（哈希碰撞）概率很小，但40亿长度的数组，得多大的内存来存储？这显然是不现实的，而又因为HashMap的初始数组长度位16，所以要进行一定的操作，让最终的结果值在0~15之间。 那么好！现在又有个问题：为什么要用与运算，而不是%呢？理由很简单：由于位运算直接对内存数据进行操作，不需要转成十进制，处理速度非常快。 什么！你不信？OK！咱们写一个测试类验证一下！ 【代码示例2】 代码语言：javascript复制public class Test { public static void main(String[] args) { test1(); test2(); } public static void test1() { int number = Integer.MAX_VALUE; int a = 1; long start = System.currentTimeMillis(); for (int i = 1; i < number; i++) { a %= i; } long end = System.currentTimeMillis(); System.out.println("第1种" +(end - start) + "毫秒"); } public static void test2() { int number = Integer.MAX_VALUE; int a = 1; long start2 = System.currentTimeMillis(); for (int i = 1; i < number; i++) { a &= i; } long end2 = System.currentTimeMillis(); System.out.println("第2种" + (end2 - start2) + "毫秒"); } }输出： 代码语言：javascript复制第1种9290毫秒 第2种565毫秒结果很明显，&运算的耗时要远远小于取余%！ 现在我们解释了选取&的原因，那怎么样采用实现取余数的操作呢？当b为2的幂次方时，伟大的前人们发现了这个公式：a%b = a&(b-1)验证计算：  到这里，key的值在HashMap中的位置存储就讲完啦。 JDK1.8中为什么由数组+链表改为数组+链表+红黑树？我们在上面所看到的源码其实都是JDK1.8的，在此之前的HashMap底层采用的是数组+链表形式，我们以JDK1.7为例，当存入一个键值对，会通过扰动函数（hash()）尽可能减少碰撞，找到数组对应位置后，若无元素，则直接存入键值对，若有元素，则判断和存入的key值是否相同（重写equals()方法），若相同，则进行值覆盖，若不相同，则通过 拉链法 解决冲突。 所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。  相较于JDK1.7而言，1.8的升级除了优化了hash()方法外，最主要的是在解决哈希冲突的方式上进行了大改造，发生冲突时依旧采用链表向后存储，但当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。  之所以选择红黑树，是为了解决二叉查找树在某些场合下退化成一个线性结构的缺陷。 我们可以继续查看底层putVal()的部分源码片段 【源码解析4】 代码语言：javascript复制// 遍历链表 for (int binCount = 0; ; ++binCount) { // 遍历到链表最后一个节点 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 如果链表元素个数大于等于TREEIFY_THRESHOLD（8） if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st // 红黑树转换（并不会直接转换成红黑树） treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; }可以看到，当链表的元素个数大于等于8时，调用 treeifyBin(tab, hash)向红黑树转换，那我们继续跟入这个方法查看。 【源码解析5】 代码语言：javascript复制final void treeifyBin(Node[] tab, int hash) { int n, index; Node e; // 判断当前数组的长度是否小于 64 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) // 如果当前数组的长度小于 64，那么会选择先进行数组扩容 resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { // 否则才将链表转换为红黑树 TreeNode hd = null, tl = null; do { TreeNode p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) hd.treeify(tab); } }在treeifyBin方法中，先进行数组长度的判断，当长度小于64的时候 ，会先进行数组的扩容，当长度大于等于64时，才将链表转换为红黑树。 HashMap的扩容机制？上面提到了扩容，我们从源码中可以看到，HashMap的扩容是通过resize()方法实现，我们继续跟进源码去看。 【源码解析6】 代码语言：javascript复制final Node[] resize() { Node[] oldTab = table; // 获取原来的数组 table int oldCap = (oldTab == null) ? 0 : oldTab.length; // 获取数组长度 oldCap int oldThr = threshold; // 获取阈值 oldThr int newCap, newThr = 0; if (oldCap > 0) { // 如果原来的数组 table 不为空 if (oldCap >= MAXIMUM_CAPACITY) { // 超过最大值就不再扩充了，就只好随你碰撞去吧 threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap = DEFAULT_INITIAL_CAPACITY) newThr = oldThr 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = 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); } threshold = newThr; // 将新阈值赋值给成员变量 threshold @SuppressWarnings({"rawtypes","unchecked"}) Node[] newTab = (Node[])new Node[newCap]; // 创建新数组 newTab table = newTab; // 将新数组 newTab 赋值给成员变量 table if (oldTab != null) { // 如果旧数组 oldTab 不为空 for (int j = 0; j < oldCap; ++j) { // 遍历旧数组的每个元素 Node e; if ((e = oldTab[j]) != null) { // 如果该元素不为空 oldTab[j] = null; // 将旧数组中该位置的元素置为 null，以便垃圾回收 if (e.next == null) // 如果该元素没有冲突 newTab[e.hash & (newCap - 1)] = e; // 直接将该元素放入新数组 else if (e instanceof TreeNode) // 如果该元素是树节点 ((TreeNode)e).split(this, newTab, j, oldCap); // 将该树节点分裂成两个链表 else { // 如果该元素是链表 Node loHead = null, loTail = null; // 低位链表的头结点和尾结点 Node hiHead = null, hiTail = null; // 高位链表的头结点和尾结点 Node next; do { // 遍历该链表 next = e.next; if ((e.hash & oldCap) == 0) { // 如果该元素在低位链表中 if (loTail == null) // 如果低位链表还没有结点 loHead = e; // 将该元素作为低位链表的头结点 else loTail.next = e; // 如果低位链表已经有结点，将该元素加入低位链表的尾部 loTail = e; // 更新低位链表的尾结点 } else { // 如果该元素在高位链表中 if (hiTail == null) // 如果高位链表还没有结点 hiHead = e; // 将该元素作为高位链表的头结点 else hiTail.next = e; // 如果高位链表已经有结点，将该元素加入高位链表的尾部 hiTail = e; // 更新高位链表的尾结点 } } while ((e = next) != null); // if (loTail != null) { // 如果低位链表不为空 loTail.next = null; // 将低位链表的尾结点指向 null，以便垃圾回收 newTab[j] = loHead; // 将低位链表作为新数组对应位置的元素 } if (hiTail != null) { // 如果高位链表不为空 hiTail.next = null; // 将高位链表的尾结点指向 null，以便垃圾回收 newTab[j + oldCap] = hiHead; // 将高位链表作为新数组对应位置的元素 } } } } } return newTab; // 返回新数组 }这个方法还是比较复杂的，由此可以看出HashMap的扩容还是比较耗时的，会伴随着数组的重新分配，旧数组的拷贝，数组容量的判断等等。 这里面我们可以发现每次新数组长度 newCap，是由oldCap |
【本文地址】
今日新闻 |
推荐新闻 |