经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » Java相关 » Java » 查看文章
jdk源码浅读-HashMap
来源：cnblogs　　作者：姓码名农小小　　时间：2018/11/9 11:24:08　　对本文有异议

在Java语言中使用的最多的数据结构大概右两种，第一种是数组，比如Array，ArrayList，第二种链表，比如ArrayLinkedList，基于数组的数据结构特点是查找速度很快，时间复杂度为 O（1），但是删除的速度比较慢，因为每次删除元素的时候需要把后面的所有的元素都要相应的往前移动一位，最坏的情况删除第一个元素，时间复杂度为O(n)。基于链表实现的数据结构的特点是删除的速度比较快，但是查找的速度比较慢，每次查找数据的时候都需要从链表头部开始往下遍历，链表查找最坏时间是O(n)。HashMap 就整合和了数组和链表的有点而设计出来的，它的查找速度为 O(1) + O(a),a为链表长度，事实上hashMap的hash算法能够很好的避免了在插入数据的碰撞问题，所以链表的长度基本不会很长，所以hashMap的查找速度还是很快的。一般地，我们平衡一种结构的性能是看平均时间复杂度的，在 jdk1.8以前hashMap在最糟糕的情况下查找的时间复杂度为 O(1) +O(n) ,n 为数据的大小。在jdk1.8时sun公司对hashMap进行了优化，hashMap的存储结构由原来的数组+链接的结构改成 数组+链表+红黑树的形式。时间复杂度由O(1) + O(n) 降为 O(1) + O(logn)。下面的源码都是基于jdk1.8的。

HashMap中几个重要的参数：

1、threshold ： 数组的大小，默认长度为16，可以在构造函数中指定初始化大小，但是必须是2的n次方，具体原因在下面将会说到。注意：该值是指数组的大小，并不是指HashMap中已经存放了的数据量，存放的数据的大小总是小于等于 threshold * loadFactor。

2、loadFactor： 负载因子，默认值为0.75。当HashMap中存储的数据大于阈值（threshold * loadFactor）时，threshold会进行翻倍，执行resize方法，对原数组中所有的元素进行一次重新hash计算，根据hash计算得出的下表放在新的数组中。负载因子的设计是为了减少在put操作时发生的碰撞，因为当我们put的数据越来越多的时候，数组中空的位置也会越来越少，那么发生碰撞的概率也随之增大，碰撞的次数越多对性能由一定的影响。一般地我们不需要对这个值进行设置，使用默认值就可以了。

3、TREEIFY_THRESHOLD：转换红黑树的阈值，默认值为8。即当数组中链表的长度达到这个值之后，链表就是转换成红黑树，以提高性能。

4、UNTREEIFY_THRESHOLD：红黑树转链表的阈值，默认值为6。

HashMap结构

HashMap是以key-value的形式存储数组中，将数据存在Node节点中，每个Node节点存储了一个key，对应的value和指向下一个Node的指针。HashMap的结构为数组+链表（红黑树），链表为单向链表。结构如下：

或：

HashMap原理：

HashMap在进行put（key，value）操的时候，我们源码

  1. /**
  2.      * Associates the specified value with the specified key in this map.
  3.      * If the map previously contained a mapping for the key, the old
  4.      * value is replaced.
  5.      *
  6.      * @param key key with which the specified value is to be associated
  7.      * @param value value to be associated with the specified key
  8.      * @return the previous value associated with <tt>key</tt>, or
  9.      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
  10.      *         (A <tt>null</tt> return can also indicate that the map
  11.      *         previously associated <tt>null</tt> with <tt>key</tt>.)     */public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
  12.     }
  1.     /**
  2.      * Implements Map.put and related methods
  3.      *
  4.      * @param hash hash for key
  5.      * @param key the key
  6.      * @param value the value to put
  7.      * @param onlyIfAbsent if true, don't change existing value
  8.      * @param evict if false, the table is in creation mode.
  9.      * @return previous value, or null if none     */final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  10.                    boolean evict) {
  11.         Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)
  12.             n = (tab = resize()).length;/**
  13.          * 通过位与的方式来确定下标位置，判断当前下标位置是否为空，如果为空直接放入到该位置上
  14.          * 不为空则通过equals方法来寻找当前位置上面的元素，如果有相同的key，则将覆盖掉，如果没有则将node放置在对应
  15.          * 位置上面         */if ((p = tab[i = (n - 1) & hash]) == null)//直接放到数组中tab[i] = newNode(hash, key, value, null);else {//当前位置不为空Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))//已存在相同的key的数据，将其覆盖e = p;else if (p instanceof TreeNode)//当前位置是红黑树，将Node节点放到红黑树中e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//为链表的情况for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {
  16.                         p.next = newNode(hash, key, value, null);//链表的长度超过转换红黑数的阈值，则将该链表转成红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                            treeifyBin(tab, hash);break;
  17.                     }if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))//覆盖相同key的nodebreak;
  18.                     p = e;
  19.                 }
  20.             }if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)
  21.                     e.value = value;
  22.                 afterNodeAccess(e);return oldValue;
  23.             }
  24.         }++modCount;//快速失败机制if (++size > threshold)//每次插入数据都要判断一下当前存储的数据是否需要扩容            resize();
  25.         afterNodeInsertion(evict);return null;
  26.     }

　　当我们当HashMap中put数据的时候，首先会对传进来的key进行hash计算：

  1.  /**
  2.      * Computes key.hashCode() and spreads (XORs) higher bits of hash
  3.      * to lower.  Because the table uses power-of-two masking, sets of
  4.      * hashes that vary only in bits above the current mask will
  5.      * always collide. (Among known examples are sets of Float keys
  6.      * holding consecutive whole numbers in small tables.)  So we
  7.      * apply a transform that spreads the impact of higher bits
  8.      * downward. There is a tradeoff between speed, utility, and
  9.      * quality of bit-spreading. Because many common sets of hashes
  10.      * are already reasonably distributed (so don't benefit from
  11.      * spreading), and because we use trees to handle large sets of
  12.      * collisions in bins, we just XOR some shifted bits in the
  13.      * cheapest possible way to reduce systematic lossage, as well as
  14.      * to incorporate impact of the highest bits that would otherwise
  15.      * never be used in index calculations because of table bounds.     */static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  16.     }

jdk1.8开始hash的计算比之前的简单一些，就是对key的hashCode的高16位和低16位进行异或运算。这样做的目的是让key的HashCode 的高位也有计算参与运算，这样计算出来的hash值更加均匀，put数据时能够减少碰撞，提供性能。

第二步根据key计算出来的值获取到对应的下标，这里并不是使用取模的方式来确定，因为取模的方式相对于位与运算来说性能更低下。下标的计算公式为：当前数组的长度减一 按位与 hash值，得到下标，比如当前数组长度为 16，hash值：54707624，则计算如下：（注意：位与的运算规则为，当两个数均为1时结果才为1，否则结果为0）

从上面的运算结果，可以得到一个规律，能够参与有效运算的位只有与数组长度减一的位的长度，比如 数组长度为16，那么16-1的二进制为 1111，那么不管key的hash值有多大，最终参与运算的只有后4位，根据位与运算规则，运算结果的最大值为 1111，转换成十进制后即数组的长度减一，最小值为 0000，十进制为0，即结果的范围为 0 ~ size - 1，这个取模的结果是一致的。又因为数组的长度总是2的n次方，对应的二进制 为 1，11，111 ，11111等等，这也是为什么每次扩容时都要扩大至原来的两倍的原因。那么，另外一个问题又来了，为什么一定要时2的n次方呢？其他的值可以吗？下面我们来做一个实验：

  1. public static void main(String[] args) {for (int i = 0; i < 30; i++) {
  2.             System.out.print((i & 15) + " ");
  3.         }
  4.     }
  5.  
  6. 运算结果：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13

　　当我们使用 2 的n次方-1来运算时，每个余数都有可能得到

  1. public static void main(String[] args) {for (int i = 0; i < 30; i++) {
  2.             System.out.print((i & 13) + " ");
  3.         }
  4.     }
  5. 运算结果：0 1 0 1 4 5 4 5 8 9 8 9 12 13 12 13 0 1 0 1 4 5 4 5 8 9 8 9 12 13

当我们使用 非2的n次方运算时，看运算结果可以看到，有些值是不可能得到的，这样数组的某些位置就永远为空，不仅造成空间的浪费，同时也会大大的提高碰撞的概率。根据位与运算规则，很容易想到其中的原因，首先将13转成二进制：1101，在位与运算时，那个 0 位永远不参与运算，如上面的结果一样，2，3，6等数值是没有的。当且仅当二进制数字全为1的时候，才有可能所有的位都能计算，得到的结果才会更加均匀。这个很容易理解，想一下就明白了的。

第三步，根据生成的index去数组寻找位置，如果该位置为空直接将node放进去，如果不为空则调用equals方法判断key值是否一致，一致的话就替换成新值，否则寻找下个节点，最终在插入链表的时候会判断当前链表长度是否达到了转换成红黑树的条件（默认链表长度达到8时会转）。

第四步，数据put成功后判断当前存储的数据大小是否超过了 threshold * loadFactor 的值，超过了就会执行resize方法：

  1. /**
  2.      * Initializes or doubles table size.  If null, allocates in
  3.      * accord with initial capacity target held in field threshold.
  4.      * Otherwise, because we are using power-of-two expansion, the
  5.      * elements from each bin must either stay at same index, or move
  6.      * with a power of two offset in the new table.
  7.      *
  8.      * @return the table     */final Node<K,V>[] resize() {
  9.         Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {if (oldCap >= MAXIMUM_CAPACITY) {
  10.                 threshold = Integer.MAX_VALUE;return oldTab;
  11.             }else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
  12.                 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;
  13.             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  14.         }if (newThr == 0) {float ft = (float)newCap * loadFactor;
  15.             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?  (int)ft : Integer.MAX_VALUE);
  16.         }
  17.         threshold = newThr;
  18.         @SuppressWarnings({"rawtypes","unchecked"})
  19.             Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  20.         table = newTab;if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {
  21.                 Node<K,V> e;if ((e = oldTab[j]) != null) {
  22.                     oldTab[j] = null;if (e.next == null)
  23.                         newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)
  24.                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve orderNode<K,V> loHead = null, loTail = null;
  25.                         Node<K,V> hiHead = null, hiTail = null;
  26.                         Node<K,V> next;do {
  27.                             next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)
  28.                                     loHead = e;elseloTail.next = e;
  29.                                 loTail = e;
  30.                             }else {if (hiTail == null)
  31.                                     hiHead = e;elsehiTail.next = e;
  32.                                 hiTail = e;
  33.                             }
  34.                         } while ((e = next) != null);if (loTail != null) {
  35.                             loTail.next = null;
  36.                             newTab[j] = loHead;
  37.                         }if (hiTail != null) {
  38.                             hiTail.next = null;
  39.                             newTab[j + oldCap] = hiHead;
  40.                         }
  41.                     }
  42.                 }
  43.             }
  44.         }return newTab;
  45.     }

进行扩容的时候将所有的node节点进行hash计算e.hash & (newCap - 1)，这样的结果不是在原来的就是在 当前位置加原来threshold长度的位置。至此整个put操作结束。

get（Object key）的原理：

弄懂了put操作之后，其实get就很容易理解了，首先根据传入key找到index，然后再对应的位置上获取就行了。

最后，我看了HashMap源码之后，自己也手写了一个HashMap，不同之处在于我没有用到红黑树，而是使用二叉树代替，经测试插入1千万条uuid所需时间都差粗多，都是在二十几秒左右。关于二叉树与红黑树的区别可以自行百度，红黑树最主要解决的问题是在极端的情况下二叉树只有一条路径，时间复杂度位O(N),红黑树为了避免这种情况，每次都会自动调节树的深度，将最坏的情况的时间复杂度降低到O(logN)。

因为完全是手写的，所以可能代码的可读性不是很好，但是基本的功能都能够实现了。如果大家有兴趣的话，可以下载过来看一下，也欢迎大家指出错误或提意见。项目地址: https://github.com/rainple1860/MyCollection

 

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

Java热门文章

  • 【IDEA】Application context not configured for this file
  • [IDEA] chapter_reader - idea看小说插件 idea阅读插件 idea摸鱼插件
  • thrift常见异常及原因分析
  • Java 调用 PaddleDetection 模型
  • JVM 详解，大白话带你认识 JVM
  • spring-boot-2.0.3不一样系列之番外篇 - @Configuration、Condition与@Conditional
  • Java Comparator.comparing比较导致空指针异常的解决
  • Java使用EasyExcel进行单元格合并的问题详解
  • 死磕 java集合之ArrayBlockingQueue源码分析
  • Java基础之集合Set详解

    • Java推荐文章

  • 面试场景题：一次关于线程池使用场景的讨论。
  • 前端黑科技：使用 JavaScript 实现网页扫码功能
  • 聊一聊 Netty 数据搬运工 ByteBuf 体系的设计与实现
  • 简单设计一个JAVA并行处理工具类
  • 【杂谈】JPA乐观锁改悲观锁遇到的一些问题与思考
  • 认识netty的基本组件
  • Jenkins如何使用CrumbIssuer防御CSRF攻击
  • 如何平稳地从nacos迁移到r-nacos？
  • 线程池遇到父子任务，有大坑，要注意！
  • Java JVM——12. 垃圾回收理论概述

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号