浙江龙网

  1. 首页 > 生活百科 > >

HashMap底层原理及jdk1.8源码解读

生活百科

一、前言写在前面：小编码字收集资料花了一天的时间整理出来，对你有帮助一键三连走一波哈，谢谢啦?。?
HashMap在我们日常开发中可谓经常遇到，HashMap 源码和底层原理在现在面试中是必问的 。所以我们要掌握一下，也是作为两年开发经验必备的知识点！HashMap基于Map接口实现，元素以<Key,Value>的方式存储 ， 并且允许使用null 键和null值，因为key不允许重复，因此只能有一个键为null，另外HashMap是无序的、线程不安全的 。
HashMap继承类图快捷键Ctrl+alt+U

HashMap底层原理及jdk1.8源码解读

文章插图
二、存储结构介绍
Jdk7.0之前 数组 + 链表Jdk8.0开始 数组 + 链表 + 二叉树链表内元素个数>8个 由链表转成二叉树链表内元素个数<6个 由二叉树转成链表红黑树，是一个自平衡的二叉搜索树，因此可以使查询的时间复杂度降为O(logn)链表的长度特别长的时候 ， 查询效率将直线下降，查询的时间复杂度为 O(n)Jdk1.7中链表新元素添加到链表的头结点，先加到链表的头节点，再移到数组下标位置 。简称头插法（并发时可能出现死循环）Jdk1.8中链表新元素添加到链表的尾结点 。简称尾插法（解决了头插法死循环）
底层结构实例图
HashMap底层原理及jdk1.8源码解读

文章插图
三、源码分析之常用变量解读/** * 默认初始容量 - 必须是 2 的幂 。*/static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/** * 最大容量，如果一个更高的值被任何一个带参数的构造函数隐式指定使用 。必须是 2 <= 1<<30 的幂 。* 简单理解为：最大容量2的30次幂，如果带容量也会转化为2的次幂 */static final int MAXIMUM_CAPACITY = 1 << 30;/** * 构造函数中未指定时使用的负载因子 。经过官方测试测出减少hash碰撞的最佳值 */static final float DEFAULT_LOAD_FACTOR = 0.75f;/** * 使用红黑树的计数阈值，超过8则转化为红黑树 */static final int TREEIFY_THRESHOLD = 8;/** * 使用红黑树的计数阈值，低于6则转化为链表 */static final int UNTREEIFY_THRESHOLD = 6;/** * 链表转化为红黑树 ， 除了有阈值的限制，还有另外一个限制，需要数组容量至少达到64 ， 才会转化为红黑树 。* 这是为了避免，数组扩容和树化阈值之间的冲突 。*/static final int MIN_TREEIFY_CAPACITY = 64;/** * 在首次使用时初始化，并根据需要调整大小 。分配时 ， 长度始终是 2 的幂 。* （我们还在某些操作中允许长度为零，以允许当前不需要的引导机制） */transient Node<K,V>[] table;/** * 保存缓存的 entrySet() ， 也就是存放的键值对 */transient Set<Map.Entry<K,V>> entrySet;/** * 此映射中包含的键值映射的数量，就是数组的大小 */transient int size;/** * 记录集合的结构变化和操作次数（例如remove一次进行modCount++） 。* 该字段用于使 HashMap 的 Collection-views 上的迭代器快速失败 。如果失败也就是我们常见的CME * （ConcurrentModificationException）异常 */transient int modCount;/** * 数组扩容的大小 * 计算方法 capacity * load factor容量 * 加载因子 * @serial */int threshold;/** * 哈希表的负载因子 。* @serial */final float loadFactor;四、源码分析之构造方法解读/** * 构造一个具有指定初始容量和负载因子的构造方法 * 不建议使用这个构造方法，加载因子经过官方测试是效率最好的 ， 所以为了效率应该保持默认 */public HashMap(int initialCapacity, float loadFactor) { // 参数为负数会抛出IllegalArgumentException异常if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);// 传的值超过最大值则使用默认最大值if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);// 哈希表的负载因子 。this.loadFactor = loadFactor;// 初始化的参数默认如果不是2的次幂，直接给你转化为2的次幂// 传的参数为11，会自动转化为比参数大的最近的2的次幂的值，也就是16 。// 我们后面会详细说这个方法怎么进行转化的this.threshold = tableSizeFor(initialCapacity);}/** * 构造一个只有指定初始容量的方法 */public HashMap(int initialCapacity) {// 我们会发现还是调用上面两个参数的构造方法，自动帮我们设置了加载因子this(initialCapacity, DEFAULT_LOAD_FACTOR);}/** * 构造一个具有默认初始容量(16) 和默认负载因子(0.75)的构造方法 */public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}/** * 指定map集合，转化为HashMap的构造方法 */public HashMap(Map<? extends K, ? extends V> m) { // 使用默认加载因子this.loadFactor = DEFAULT_LOAD_FACTOR; //调用PutMapEntries()来完成HashMap的初始化赋值过程putMapEntries(m, false);}/** * 将传入的子Map中的全部元素逐个添加到HashMap中 */final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { // 获得参数Map的大?。?并赋值给sint s = m.size();// 判断大小是否大于0if (s > 0) {// 证明有元素来插入HashMap// 判断table是否已经初始化如果table=null一般就是构造函数来调用的putMapEntries，或者构造后还没放过任何元素if (table == null) { // pre-size// 如果未初始化 ， 则计算HashMap的最小需要的容量（即容量刚好不大于扩容阈值） 。这里Map的大小s就被当作HashMap的扩容阈值，然后用传入Map的大小除以负载因子就能得到对应的HashMap的容量大?。ǖ鼻癿的大小 / 负载因子 = HashMap容量）// ((float)s / loadFactor)但这样会算出小数来 ， 但作为容量就必须向上取整，所以这里要加1 。此时ft可以临时看作HashMap容量大小float ft = ((float)s / loadFactor) + 1.0F;// 判断ft是否超过最大容量大小 ， 小于则用ft，大于则取最大容量int t = ((ft < (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);// 暂时存放到扩容阈值上,tableSizeFor会把t重新计算到2的次幂给扩容数组大小if (t > threshold)threshold = tableSizeFor(t);}// 如果当前Map已经初始化,且这个map中的元素个数大于扩容的阀值就得扩容// 这种情况属于预先扩大容量，再put元素else if (s > threshold)// 后面展开说resize();// 遍历map,将map中的key和value都添加到HashMap中for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {K key = e.getKey();V value = https://www.huyubaike.com/biancheng/e.getValue();// 调用HashMap的put方法的具体实现方法putVal来对数据进行存放 。该方法的具体细节在后面会进行讲解// putVal可能也会触发resizeputVal(hash(key), key, value, false, evict);}}}

推荐阅读


上一篇：基于 Apache Hudi 极致查询优化的探索实践

下一篇：详解JS中 call 方法的实现