JDK容器学习之Map: HashMap,TreeMap,LinkedHashMap对比小结

HashMap, TreeMap, LinkedHashMap 对比

1. 存储结构

HashMap 存储结构: 数组 + 链表 + 红黑树

LinkedHashMap 存储结构 和HashMap 相同,区别是维护一个根据插入顺序保持的双向链表

TreeMap 存储结构: 红黑树


2. 是否有序

HashMap 无序

LinkedHashMap 根据插入先后顺序确定遍历顺序

TreeMap 有序,根据Key进行比较获取先后顺序


3. 迭代

HashMap 迭代

  • 从头开始遍历数组
  • 若数组中该索引处为null,或者Node的next指向null,则扫描数组的下一位
  • 若数组中该索引处非null,切Node的next指向另一个Node,则依次扫描Node的next元素,直到为null

示意图如下:

LinkedHashMap 迭代

  • 扫描内部的双向链表
  • 从head指向的Node节点出发,依次扫描 after指向的下一个Node节点,直到最后一个

TreeMap 迭代

因为TreeMap是红黑树,左孩子 < 根 < 右孩子,

所以按照树的中序遍历方式进行扫描,即先获取树的左孩子,然后是根,最后是右孩子

示意图如下:


4. 应用场景&使用小建议

  1. HashMap, LinkedHashMap, TreeMap 非线程安全,因此都不适用于多线程环境下
  2. 希望有序的Map,考虑采用 LinkedHashMap, TreeMap
  • 有自己的排序需求场景的,可以使用TreeMap
  • 根据塞入Map的先后顺序进行排序的,可以使用 LinkedHashMap
  1. 其他普通kv接口存储,尽量采用 HashMap
  • 若能确定Map的元素个数,在初始化时,显示指定容量大小,避免频繁的数组扩容
  • key的hash尽量分散,避免出现大量的hash碰撞(一般不自己覆盖 key的 hashcode 方法,这个问题不太大)
  1. 有自定义排序需求时,使用 TreeMap
  • 尽量保证结构的稳定,不会频繁出现添加删除的情况(因为会导致)
  • Map中不存在两个Key通过定义的比较器,返回0,即不存在类似 HashMap 的碰撞情况
  1. 根据进入Map的先后确定遍历顺序,使用 LinkedHashMap
  • 遵从 HashMap 的使用规则

相关博文

  • JDK容器学习之HashMap (一) : 底层存储结构分析
  • JDK容器学习之HashMap (二) : 读写逻辑详解
  • JDK容器学习之HashMap (三) : 迭代器实现
  • JDK容器学习之TreeMap (一) : 底层数据结构
  • JDK容器学习之TreeMap (二) : 使用说明
  • JDK容器学习之LinkedHashMap (一):底层存储结构分析
  • JDK容器学习之LinkedHashMap(二):迭代遍历的实现方式

关注更多

关注小灰灰blog

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Celebi的专栏

C/C++ 学习笔记五(结构体、字符与字符串)

工作中经常使用到C/C++,为对C有个比较深刻的了解,重新拾起学习C的任务。在看书的同时,记录下思考的过程,也记录下重要的知识点。

4800
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——IdentityHashMap

3809
来自专栏有趣的Python

4-Java常用工具类-集合

问题: 存储20名学生的学生信息。20是不变的,就是这么多。 问题: 存储商品信息。不知道自己要买多少商品。

2002
来自专栏拭心的安卓进阶之路

Java 集合深入理解(14):Map 概述

终于把 List 常用的几种容器介绍完了,接下来开始 Map 的相关介绍。 什么是 Map Java 中的 Map 接口 是和 Collection 接口 同...

2568
来自专栏互扯程序

Java常用集合源码级深度解析

Java集合工具包位于Java.util包下,包含了很多常用的数据结构,如数组、链表、栈、队列、集合、哈希表等。学习Java集合框架下大致可以分为如下五个部分:...

5006
来自专栏个人分享

LinkedHashMap的实现原理(复习)

   LinkedHashMap是Map接口的哈希表和链接列表实现,具有可预知的迭代顺序。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不...

1134
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——IdentityHashMap

1633
来自专栏java一日一条

Java和Android的LRU缓存及实现原理

Android提供了LRUCache类,可以方便的使用它来实现LRU算法的缓存。Java提供了LinkedHashMap,可以用该类很方便的实现LRU算法,Ja...

1081
来自专栏java一日一条

Java程序员们最常犯的10个错误

Arrays.asList()会返回一个ArrayList对象,ArrayList类是Arrays的一个私有静态类,而不是java.util.ArrayList...

642
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高十六】集合List接口详解

在编写java程序中,我们最常用的除了八种基本数据类型,String对象外还有一个集合类,在我们的的程序中到处充斥着集合类的身影!java中集合大家族的成员实在...

2533

扫码关注云+社区

领取腾讯云代金券