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

时间:2022-11-03 07:55:32


​HashMap​​​, ​​TreeMap​​​, ​​LinkedHashMap​​ 对比

1. 存储结构

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

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

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

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

TreeMap 存储结构: 红黑树

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


2. 是否有序

HashMap 无序

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

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


3. 迭代

HashMap 迭代

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

示意图如下:

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

LinkedHashMap 迭代

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

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

TreeMap 迭代

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

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

示意图如下:

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


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(二):迭代遍历的实现方式​​

II. Java分享,关注小灰灰Blog

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