作为重要的常用集合，HashMap主要是提供键值对的存取，通过key值可以快速找到对应的value值。Hash表是通过提前设定好的规则计算一个元素的hash值来找到他在数组中的存储位置进行快速定位，假设有一个大小为10的数组，可以设定简单的计算规则为元素转为int后mod 10，由此元素的hash值一定会落在大小为10的数组内。由于不同元素可能会计算出相同的hash值，如例子中1和11都应该在下标为1的位置，这就是hash值的冲突。为了解决这个问题有几种常用的策略： 链表法，先加入11存储在A[1]的位置，然后加入1，检查A[1]已经有数了，将1连接到11的后面形成链表。 开放地址法，检查到冲突后根据一定规则去检查另外的位置是否有空可以存储新的元素。根据探测方法的不同，常见的有线性探测法，按照A[1], A[2]…的顺序检查，以及平方探测法，按照A[1], A[1+1^2], A[1+2^2]… 再hash法，按照另外的计算公式重新计算hash值知道不再冲突。 　　由此引入一个hash表的属性——负载因子，负载因子=存储的元素个数/数组大小。很显然，链表法由于冲突位置链无限延长的特点，若不加以限制负载因子可以超过1，负载因子越大代表表中的数据越密集。 　　HashMap的key和value值都可以为null，get操作时若找不到对应的key值会返回null，具体见下方的例子： View Code 　　因为篇幅加难度的原因TreeNode部分的分析见Java HashMap类源码解析(续)-TreeNode 　　首先大致翻译下note的主要内容：通常是桶式hash表（链表解决冲突），但是桶过大达到TREEIFY_THRESHOLD值的时候会转为树状TreeNode使得密度过高时的操作可以变得更快。一般对象在树中是按hashcode排序，但是对于实现了Comparable的对象是通过comapreTo来排序。由于TreeNode的大小接近普通node的两倍，当桶变小时会转回线性链表。TreeNode是JDK8引入的红黑树结构，树根通常是hash映射的第一个结点，除了Iterator.remove之外。链表在树化或是分裂时保证结点的遍历顺序是一致的。 View Code 　　然后我们来看下Node的结构。一般的箱式结点实现了Map.Entry接口，这是一个key-value键值对，内部有4个属性hash值、K、V以及指向下个结点的引用。hashCode方法是对key和value的hash值求异或，也重写了equals和toString方法。 View Code 对于HashMap自身的hash方法，这样做的目的是避免hash值高位因为表大小而永远不会被用于hash值的计算，使得分布可以更加均匀。 View Code 根据cap返回恰好大于等于该值的2的指数大小。以cap = 6175进行演示，可得n最终为8191即2^13-1，所以返回值为2^13 HashMap内部属性如下： View Code 构造函数： View Code 这里通过一个已有Map来构造时用到了putMapEntries这个方法，先来看下这个方法 View Code 可以看到其中调用了用于扩展表的resize和插入键值对的putVal。先看resize方法，这个方法在表大小超过threhold时就会被调用，作用就是扩展数组大小，并将元素复制到数组中，同时对于冲突链表不需要重新计算hash值而是会根据他们的hash值决定要不要复制到数组的高位去 View Code putVal这个方法是把值存入表中，在多个put类方法中被调用 View Code treeifyBin将指定hash值对应的位置上的链表替换为树，除非整个表的大小太小时调用resize，(n - 1) & hash等效于hash mod n，只保留hash除以n的余数作为index的值 View Code 对于移除操作会调用removeNode，这个方法在多个移除方法中被使用。若移除指定key值成功的结点会返回value值，否则返回null View Code clear方法不难理解，将表内所有元素设为null，size变为0，增加modCount View Code 寻找表内有无相等的value，遍历整个链表找到则返回true View Code key是一个set集合，value是一个collection集合，调用keySet()和values()返回的集合是对HashMap中key和value的直接引用，所以操作会直接反应在HashMap上 View Code 根据上面对putVal的分析，该方法不会改变已有的key值，返回值为旧值或null View Code 然后来看一下两个replace方法，区别在于返回值和是否检查value值 View Code computeIfAbsent这个方法的作用是若key值在map中已有非null的value值，则直接返回旧value值；若value值为null则根据mappingFunction计算出新的value值并修改map中存在的键值对，返回新value值；若不存在key值则新增一个键值对插入到key的hash值对应的table数组位置链表的头部，并返回新的value值。注意，putVal方法插入的结点是在链表尾部，而该方法是在链表头部。 View Code 然后是两个相近的方法：computeIfPresent存在key相等且value不为null的结点，计算新的value值，新value不为null则覆盖，新value为null则移除原本的结点。compute方法结合了前两者，存在key相等的结点时不考虑旧value值，新value为null则移除，不为null则覆盖value值；不存在key相等的结点时，新value值不为null则新增结点，对箱式链表插入到链表头部，插入后要检车是否需要转为树。 View Code merge这个方法和前面差不多，也是先寻找key值相同的结点，若存在则看该结点value是否为null，不为null根据function和参数中的value以及结点原本的value计算出新的value值，否则直接赋予参数中的value值。若没有找到结点，则按照参数中key和value值新建一个结点插入到树中或者箱式链表的头部。 View Code 两个批量操作不难理解，同样要保证过程中没有其他线程修改了对象的元素个数 View Code HashMap实现了clone方法，可以产生一个新的完全一样的HashMap View Code capacity这个方法先看table是否为null，不为null直接返回table.length。然后看threshold是否为0，不为0返回threshold否则返回默认容量16 View Code HashMap的序列化方法同样利用的是ObjectOutputStream View Code 序列化输入是通过ObjectInputStreams，loadFactor一定会限制在0.25-4.0之间，而threshold是根据size/loadFactor + 1.0然后计算出大于等于该值的最小2的指数次幂。 View Code 个人GitHub地址: https://github.com/GrayWind33 分类: JDK源码解析 标签: Java, HashMap, 源码解析 好文要顶 关注我 收藏该文 GrayWind 关注 - 0 粉丝 - 0 +加关注 0 0 « 上一篇：算法导论——最小生成树 » 下一篇：算法导论——单元最短路径 posted @ 2018-08-11 20:34 GrayWind 阅读(199) 评论(0) 编辑 收藏 刷新评论刷新页面返回顶部 注册用户登录后才能发表评论，请 登录 或 注册，访问网站首页。 【推荐】超50万VC++源码: 大型组态工控、电力仿真CAD与GIS源码库！ 【免费】要想入门学习Linux系统技术，你应该先选择一本适合自己的书籍 【前端】SpreadJS表格控件，可嵌入应用开发的在线Excel 【直播】如何快速接入微信支付功能 腾讯云 最新IT新闻: · 《愤怒的小鸟》将作为AR益智游戏来到Magic Leap One平台 · 巨人网络并购停摆 史玉柱质押逾七成股权存平仓风险 · 银河系总质量是多少？约为太阳质量7000亿到2万亿倍 · 王兴的另一面：饭否上看他如何读书、发问与思考 · 触宝更新招股书：IPO发行价为12-14美元 » 更多新闻... 华为云HC0917 最新知识库文章: · 为什么说 Java 程序员必须掌握 Spring Boot ？ · 在学习中，有一个比掌握知识更重要的能力 · 如何招到一个靠谱的程序员 · 一个故事看懂“区块链” · 被踢出去的用户 » 更多知识库文章... 公告 昵称：GrayWind 园龄：1年 粉丝：0 关注：0 +加关注 < 2018年9月 > 日 一 二 三 四 五 六 26 27 28 29 30 31 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 1 2 3 4 5 6 搜索 常用链接 我的随笔 我的评论 我的参与 最新评论 我的标签 我的标签 算法导论(8) 源码解析(7) Java(7) maven(2) MyBatis(2) MySQL(1) Prim(1) RESTful(1) Spring(1) SpringBoot(1) 更多 随笔分类 JDK源码解析(7) 环境搭建(6) 算法导论读书笔记(8) 随笔档案 2018年8月 (14) 2018年7月 (2) 2018年3月 (2) 2018年2月 (4) 2018年1月 (1) 文章分类 PAT(A)(10) 阅读排行榜 1. SpringBoot+MyBatis开发环境搭建并实现登录权限过滤(1649) 2. maven+SpringMVC搭建RESTful后端服务框架(852) 3. Windows环境下Git环境的搭建(569) 4. 对于数据库连接池的一些思考和MyBatis的集成与使用(542) 5. Java String类源码解析(2https://www.cnblogs.com/graywind/p/9457521.html