写BUG的派大星

Patrick Star

  • 首页
  • 归档

  • 搜索
设计模式 Gis Kafka Druid 微信小程序 Java 开源项目源码 物体识别 机器学习 Mybatis 微服务 Feign OpenVPN CSS Streamsets CDH SpringCloud SpringBoot maven 分布式 Shell Tree Linux js WebSocket 多线程 集群 Hadoop 大数据 JDK ElasticSearch MySQL 数据库 Redis Http Nginx

Hashmap源码解析

发表于 2020-03-19 | 分类于 Java | 0 | 阅读次数 954

简介

HashMap是Java面试中经常出现的问题,自然也需要对它的源码进行了解和掌握。

实现方式

在JDK1.7及以前,HashMap的实现方式是数组+链表,但是在JDK1.8之后对HashMap的底层进行了一些优化,变成数组+链表/红黑树的结构,在节点数小于等于6时,以数组+单向链表存储,节点数大于等于8时,则以数组+红黑树的方式存储。这样做的目的主要也是为了提高查询效率。

关于红黑树,可以查看这篇文章 :关于红黑树

源码

继承关系

HashMap的继承关系

首先先看一下HashMap的继承关系,它继承自AbstractMap,实现Map、Cloneable、Serializable接口。

这里需要说明的是AbstractMap这个类,它是提供了Map的基本实现的抽象类,即在Java中为了实现Map所写的一个便利类,也就是说如果我们需要Map的一个具体类,只要实现AbstractMap未实现的部分即可,自然也可以重写已实现的方法。

AbstractMap类的方法

默认常量

//默认初始容量为16,也就是2^4
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//最大容量,为2^30 (int的取值范围在-2^31~2^31-1)
static final int MAXIMUM_CAPACITY = 1 << 30;

//负载系数
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;

字段

//Node是Map.Entry接口的实现类,存储数据的Node数组长度是2的幂,每一个Node的本质都是一个单向列表
transient Node<K,V>[] table;

//键值对集合,是不可重复的
transient Set<Map.Entry<K,V>> entrySet;

//HashMap的大小,也就是保存的键值对数量
transient int size;

//HashMap被改变的次数
transient int modCount;

//HashMap下次扩容的大小(容量*负载系数)
int threshold;

//负载系数的常量,前面说到默认为0.75
final float loadFactor;

transient字段说明:

  1. 一旦变量被transient修饰,变量将不再是对象持久化的一部分,该变量内容在序列化后无法获得访问。
  2. transient关键字只能修饰变量,不能修饰方法和类。(本地变量是不能被transient关键字修饰的。变量如果是用户自定义类变量,则该类需要实现Serializable接口。)
  3. 实现Serializable时,被transient关键字修饰的变量不再能被序列化,但若是实现Externalizable接口,由于是在writeExternal方法中进行手工指定所要序列化的变量,这与是否被transient修饰无关,则可以被序列化。

Node[]的实现

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
		
    //Node的本质就是一个单向列表
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
	// get、set、hashCode、equals和toString方法
        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

构造方法

无参构造

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }

指定初始容量和负载系数的构造方法


public HashMap(int initialCapacity, float loadFactor) {
    //初始容量小于0的话会抛出异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
    //初始容量大于最大容量则设为最大容量
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
    //负载系数小于等于0或不是一个数的时候则抛出异常
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
    //进行初始化
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

仅指定初始容量

public HashMap(int initialCapacity) {
    //添加默认负载系数调用上面的双参数构造方法
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

使用Map集合构造

//将Map中的键值对全部放入HashMap中
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

红黑树的实现

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    //红黑树的根节点
    TreeNode<K,V> parent;  // red-black tree links
    //左子树
    TreeNode<K,V> left;
    //右子树
    TreeNode<K,V> right;
    //上一个节点
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    //是否是红树(根节点颜色)
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
    ......
}
  • 本文作者: Patrick
  • 本文链接: https://www.write1bug.cn/archives/hashmap源码解析
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# 设计模式 # Gis # Kafka # Druid # 微信小程序 # Java # 开源项目源码 # 物体识别 # 机器学习 # Mybatis # 微服务 # Feign # OpenVPN # CSS # Streamsets # CDH # SpringCloud # SpringBoot # maven # 分布式 # Shell # Tree # Linux # js # WebSocket # 多线程 # 集群 # Hadoop # 大数据 # JDK # ElasticSearch # MySQL # 数据库 # Redis # Http # Nginx
CentOS8安装JDK11
Java线程池相关(未完待续)
  • 文章目录
  • 站点概览
Patrick

Patrick

不是在改BUG,就是在写BUG。

52 日志
9 分类
36 标签
RSS
E-mail
Creative Commons
© 2018 — 2023 Patrick
人生如逆旅|我亦是行人
鲁ICP备18043140号-1