HashMap源码学习

首先实现map的子类:HashMap、HashTable、TreeMap、LinkedHashMap。

这几个类中HashMap与HashTable的区别:

线程上:HashMap是线程不安全的,而HashTable是安全的。key、value的支持:HashMap的key、balue可以为空,而HashTable是key、value不可以为空的。底层数据结构:HashMap采用数组+链表+红黑树,当链表的长度>=8的时候会考虑是否转成红黑树,而HashTable则没有。初始化容量上:HashTable的初始化容量是11,同时扩容变为原来的2n+1,HashMap的初始化容量是16,同时扩容扩容成原来的2倍。而当给定初始化容量时,HashTable是直接给定初始化容量,而HashMap是将给定的初始化容量变成2的次幂。

jdk7和jdk8之间,jdk8引入了红黑树,同时jdk7中的transform( )方法变成了resize( )方法。什么是红黑树,同时数组什么时候会加入链表,链表和数组满足什么条件时,链表会变成红黑树,什么时候红黑树又会变成链表。同时如果给定初始化容量,给成怎样会才合理。

1.HashMap相关变量

//默认初始化容量2^4 =16,做左移位运算
static final int DEFAULT_INITIAL_CAPACITY=1<<4;
//最大容量 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认加载因子 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//需要变成红黑树的链表阀值 8
static final int TREEIFY_THRESHOLD = 8;
//将红黑树变成链表的阀值 6
static final int UNTREEIFY_THRESHOLD = 6;
//变成红黑树除了满足链表达到8,而且数组需要
//达到64,最小转成红黑树的数组长度64
static final int MIN_TREEIFY_CAPACITY = 64;
//数组,又称为bucket,桶,2的次幂
transient Node<K,V>[] table;
//entrySet:k、v对的集合
transient Set<Map.Entry<K,V>> entrySet;
//map的长度
transient int size;
//修改次数
transient int modCount;
//阀值  threshold = capacity*loadFactor
int threshold;
//加载因子
final float loadFactor;

2.构造函数

public HashMap(int initialCapacity,

3.方法

put方法

//如果元素属于树节点,则进行红黑树的判断,执

扩容操作

else {//否者没有进行初始容量,则

remove操作

return(e=removeNode(hash(key),key,null,false,

get操作

return (e = getNode(hash(key), key))

从里面可以收获到的一些结论:

HashMap的源码较多,且综合了数组、链表、红黑树的操作,因此不管是get还是remove还是get都需要考虑到三张数据结构的操作。同时红黑树是一种平衡二叉树,节点是黑色或者红色的,根节点为黑色的,每个红色节点的两个叶子节点都是黑色的,从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。同时当key相同时,会出现冲突,此时就需要解决hash冲突,此时就将其放入到链表中。而当链表的长度>=8时,数组长度>=64时,则变成红黑树。给定初始化容量时,给定元素个数/加载因子为最佳初始化容量,可以在源码找到这个代码。

本文分享自微信公众号 - 后端技术学习(gh_9f5627e6cc61),作者:亚洲

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • JVM学习二

    jps、jstat、jinfo、jhat、jstack、jconsole、jmap、MAT、Btrace、psi_probe监控tomcat,通过gceasy查...

    路行的亚洲
  • RocketMQ学习Broker流程、生产者和存储流程联系

    Broker作为代理,路由注册是通过Broker与nameServer的心跳功能实现的。除此之外,还联系了生产者和消费者、存储。因此可以知道Broker是非常重...

    路行的亚洲
  • RocketMQ学习5

    进行消息发送的过程首先会准备好路由信息,最终是由netty完成的,也即使用nettyRemotingClient来实现的。

    路行的亚洲
  • 为什么要使用构造方法

    wfaceboss
  • 封装RabbitMQ.NET Library 的一点经验总结

    这篇文章内容会很短,主要是想给大家分享下我最近在做一个简单的rabbitmq客户端类库的封装的经验总结,说是简单其实一点都不简单。为了节省时间我主要按照Libr...

    王清培
  • 腾讯云Yunong Xiao:无服务逐渐开始承载起企业核心业务

    据调查报告显示,无服务器架构市场规模在2018年达到42.5亿美元,预计在2023年将达到149.3亿美元,复合年增长率将达29%。成本和效率两大原因促使无服务...

    腾讯云serverless团队
  • 速读原著-TCP/IP(TFTP:简单文件传送协议)

    T F T P ( Trivial File Transfer Protocol)即简单文件传送协议,最初打算用于引导无盘系统(通常是工作站或X终端)。和将在第...

    cwl_java
  • 从SAP最佳业务实践看企业管理(129)-MM-252含委外加工的第三方订单处理

    MM 252含委外加工的第三方订单处理 分包使用分包订单处理, 您用分包订单订购最终产品.,供应商在生产中所需要的零部件在采购订单中特别加以说明。零部件被记在提...

    SAP最佳业务实践
  • 微信小程序WePY开发框架简介

    微信小程序入门门槛低、开发周期短、代码编写灵活、传播速度快等优点让微信小程序迅速火爆,开发者纷纷涌入,任何语言开发者一旦多了,就会有新的框架出来,WePY就是一...

    大公爵
  • 小白学计算机视觉:前言

    人类大部分信息都是视觉化接受的。人类对图像的理解,看起来是一件简单的事情。而对于计算机,这是一个复杂而有挑战的“活儿”。

    陆勤_数据人网

扫码关注云+社区

领取腾讯云代金券