Java集合03——你不得不了解的Map
2020-03-06 本文已影响0人
Java面典
Map 在面试中永远是一个绕不开的点，本文将详细讲解Map的相关内容。关注公众号「Java面典」了解更多 Java 知识点。
Map
- Map 是一个键值对（key-value）映射接口；
- 映射中不能包含重复的键，每个键最多只能映射到一个值；
- Map 允许以键集（keySet()）、值集（valueSet()）或键-值映射关系集（entrySet()）的形式查看某个映射的内容。
HashMap
特点
- 根据 key 的 hashCode 存储数据，大多数情况下（hash冲突时除外）可以直接定位到值；
- HashMap具有较快的随机读取速度，遍历速度不可控；
- 一个 HashMap 对象中最多只允许一条记录的键为 null，允许多条记录的值为 null；
- HashMap是非线程安全的。
实现
HashMap.png
可以看出 HashMap 其实是一个数组 + 单向链表组成。
容量
- capacity：当前数组容量（默认16），始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍；
- loadFactor：负载因子，默认为 0.75；
- threshold：扩容阈值，等于 capacity * loadFactor。
Java8实现
Java8HashMap.png
从 Java8 开始，Java 对 HashMap 的实现有了一定的改变，开始引入红黑树，所以其结构变成了 数组 + 链表 + 红黑树组成。
原因：当发生 hash 冲突时，在链表中查询 Node 的时间复杂度为 O(n)，为了降低时间复杂度，引入红黑树，时间复杂度变为 O(logN)。
容量：除了Java7中的容量相关参数外，Java8为了引入红黑树，还引入了另外几个容量相关的变量。
- static final int TREEIFY_THRESHOLD = 8：链表转树阈值。当链表长度 > 该值时，则将链表转换成红黑树；
- static final int UNTREEIFY_THRESHOLD = 6：树还原链表阈值。当红黑树内节点数量 < 6时，则将红黑树转换成链表；
- static final int MIN_TREEIFY_CAPACITY = 64：最小树化阈值。当哈希表中的容量 > 该值时，才允许链表转化为红黑树。否则将直接扩容。为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD。
ConcurrentHashMap
特点
- ConcurrentHashMap 其实就是一个线程安全的HashMap；
- ConcurrentHashMap key 和 value 均不允许为 null。
网上关于key 和 value 不允许为 null 的解释是这样描述的：如果map.get(key)return null，则无法检测到该键是否显式映射到 null 该键。在非并行映射中，您可以通过进行检查 map.contains(key)，但在并行映射中，两次调用之间的映射可能已更改。
实现
ConcurrentHashMap.png
- ConcurreuntHashMap 实现和 HashMap 差不多的，但是为了支持并发操作，引入了 Segment，ConcurreuntHashMap 由一个 Segment 数组组成；
- Segment 通过继承 ReentrantLock 来进行加锁，Segment 数组就相当于是 ConcurreuntHashMap 的分段锁，每次操作只用锁住对应的 Segment 就行了；
- Segment 内部由 HashMap 组成；
- concurrencyLevel：并行级别，默认16。其实就是 ConcurreuntHashMap 由长度为 16 的 Segment 组成，所以可以理解为 ConcurreuntHashMap 默认同时可以支持最多 16 个线程并发写。Segment 数组可以在初始化的时候指定，初始化后不可扩容。
Java8实现
Java8 ConcurrentHashMap.png
和 HashMap 一样， ConcurrentHashMap 在 Java8 中也引入了红黑树的机制。在这里就不再赘述了。
LinkedHashMap
LinkedHashMap.png
LinkedHashMap 是 HashMap 的一个子类，它记录了元素插入的顺序，能够保证在使用迭代器遍历的时候，先插入的元素先获取。也可在构造时带参数，按照访问次序排序。
WeakHashMap
特点
- WeakHashMap 键值都可以是null；
- WeakHashMap 的键是“弱键”。当某个键不再正常使用时，会被从 WeakHashMap 中被自动移除。
弱键原理
- 弱键通过 WeakReference 和 ReferenceQueue 实现，
- WeakHashMap 的 key 是 WeakReference 类型的， ReferenceQueue是一个队列，它会保存被GC回收的“弱键”；
- 当某“弱键”不再被其它对象引用，并被GC回收时，这个“弱键”也同时会被添加到 ReferenceQueue(queue) 队列中；
- 当再次操作 WeakHashMap 时，会先同步 table 和 queue 。table 中保存了全部的键值对，而 queue 中保存被 GC 回收的键值对；同步它们，就是删除 table 中被 GC 回收的键值对。
主要变量
- table：是一个Entry[]数组类型，用于存储键值对；
- size： 表示 WeakHashMap 的大小；
- threshold ：阈值，用于判断是否需要调整容量，threshold的值="容量*加载因子"；
- loadFactor： 加载因子；
- modCount：是用来实现fail-fast机制的
- queue：保存的是“已被GC清除”的“弱引用的键”。
TreeMap
- TreeMap 实现 SortedMap 接口，能够把它保存的记录根据键排序；
- 默认按照键值升序排序，也可指定排序的比较器；
- 在使用 TreeMap 时，key 必须实现 Comparable 接口或者在构造 TreeMap 传入自定义的 Comparator，否则会在运行时抛出 java.lang.ClassCastException 类型的异常。
Hashtable
- Hashtable 继承自 Dictionary 接口，相当于介于 HashMap 与 ConcurrentHashMap 之间的一种哈希表；
- 相较于 HashMap 而言，他是线程安全的，同时与 ConcurrentHashMap 一样，key vlaue 均不能为null；
- 相较于 ConcurrentHashMap 而言，Hashtable 不支持多线程同时操作。
- 所以在在单线程环境一般使用 HashMap，而在多线程环境中，使用 ConcurrentHashMap 。
