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

Java基础

浏览数:110

2020-5-30

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 的使用规则

相关博文

关注更多

扫一扫二维码,关注小灰灰blog

作者:小灰灰Blog