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. 应用场景&使用小建议
- HashMap, LinkedHashMap, TreeMap 非线程安全，因此都不适用于多线程环境下
- 希望有序的Map，考虑采用 LinkedHashMap, TreeMap
- 有自己的排序需求场景的，可以使用TreeMap
- 根据塞入Map的先后顺序进行排序的，可以使用 LinkedHashMap
- 其他普通kv接口存储，尽量采用
HashMap
- 若能确定Map的元素个数，在初始化时，显示指定容量大小，避免频繁的数组扩容
- key的hash尽量分散，避免出现大量的hash碰撞（一般不自己覆盖 key的
hashcode 方法，这个问题不太大）
- 有自定义排序需求时，使用
TreeMap
- 尽量保证结构的稳定，不会频繁出现添加删除的情况（因为会导致）
- Map中不存在两个Key通过定义的比较器，返回0，即不存在类似
HashMap 的碰撞情况
- 根据进入Map的先后确定遍历顺序，使用
LinkedHashMap
- 遵从
HashMap 的使用规则
相关博文
- JDK容器学习之HashMap (一) ： 底层存储结构分析
- JDK容器学习之HashMap (二) ： 读写逻辑详解
- JDK容器学习之HashMap (三) : 迭代器实现
- JDK容器学习之TreeMap (一) : 底层数据结构
- JDK容器学习之TreeMap (二) : 使用说明
- JDK容器学习之LinkedHashMap（一）：底层存储结构分析
- JDK容器学习之LinkedHashMap（二）：迭代遍历的实现方式
II. Java分享，关注小灰灰Blog
