本文承接上文读懂Java集合(二),主要整理总结一下集合框架Map接口的常用实现。
💡图中只列出了常见的,省略了部分子接口,本文内容基于JDK 1.8
Map
存储键值对的集合,它的键和值都是无序的(特别的,LinkedHashMap是有序的),存储的键不可重复,值可以重复,其中HashTable不允许null key和null value,TreeMap不允许null key.
此处的有序指插入与取出的顺序是一致的
HashMap
平时使用最为频繁,面试几乎必问的问题,因为它牵涉到了许多知识点,作为开发人员必须非常了解.后续我还得在专门整理一篇详细的HashMap源码分析,还好多自己不是很理解😂.
对Map接口基于哈希表的一种实现,键值元素可包含null
,它基于数组+链表+红黑树实现,初始化时可以指定大小和装载因子,未指定默认大小为16,默认装载因子0.75f,非线程安全。
Cloneable和Serializable作用
HashMap实现了Cloneable和Serializable接口,但是这两个接口是空的,这是为什么呢?这是因为Cloneable和Serializable都是标记型的接口,它们内部都没有方法和属性.实现 Cloneable来表示该对象能被克隆,能使用Object.clone()方法;实现 Serializable来表示该对象能被序列化
所有方法
方法 | 描述 |
---|---|
public int size() |
返回Map集合大小 |
public boolean isEmpty() |
判断Map元素是否为空 |
public V get(Object key) |
根据key获得相应的value值 |
final Node<K,V> getNode(int hash, Object key) |
根据hash和key获得相应的Node对象(静态内部类) |
public boolean containsKey(Object key) |
判断给定的键key是否存在 |
public V put(K key, V value) |
添加一对key-value |
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) |
给定hash和其他信息添加一对key-value |
final Node<K,V>[] resize() |
ensureCapacity (int minCapacity) 增加这个的容量 实例,以确保它至少可以保存由最小容量参数指定的元素数 |
final void treeifyBin(Node<K,V>[] tab, int hash) |
forEach ( Consumer <? super E > action) 对象的每个元素执行给定的操作 直到所有元素都处理完毕,或者操作抛出异常 |
public void putAll(Map<? extends K, ? extends V> m) |
get (int index) 返回此列表中指定位置的元素 |
public V remove(Object key) |
indexOf ( Object o) 返回此列表中指定元素的第一个匹配项的索引,如果此列表不包含该元素,则返回 -1 |
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) |
指定哈希值、键值和匹配模式移除元素 |
public void clear() |
清空集合 |
public boolean containsValue(Object value) |
判断给定的值value是否存在 |
public Set<K> keySet() |
返回集合所有key的Set集合对象 |
public Collection<V> values() |
返回集合所有value的Collection集合对象 |
public Set<Map.Entry<K,V>> entrySet() |
返回集合对应的Set集合对象 |
public V getOrDefault(Object key, V defaultValue) |
返回指定键对应的值,没找到返回默认值 |
public V putIfAbsent(K key, V value) |
如果给定的键值不存在,将给定键值添加到集合 |
public boolean replace(K key, V oldValue, V newValue) |
给定键值和新的值将旧值替换为新值 |
public V replace(K key, V value) |
给定键值将指定的键对应的值替换为新值 |
public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) |
没搞懂 |
public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) |
没搞懂 |
public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) |
没搞懂 |
public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) |
如果指定的键尚未与值关联或与 null 关联,则将其与给定的非空值关联 |
public void forEach(BiConsumer<? super K, ? super V> action) |
对此集合中的每个元素执行给定的操作,直到处理完所有元素或该操作引发异常为止 |
public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) |
将每个元素的值替换为调用给定函数的结果,直到所有元素都得到处理或该函数引发异常 |
public Object clone() |
返回此集合的浅拷贝 |
private void writeObject(java.io.ObjectOutputStream s) |
用于HashMap序列化 |
private void readObject(java.io.ObjectInputStream s) |
用于HashMap序列化 |
数据结构
从网上找来一张图,直观展示 HashMap 结构:数组+链表+红黑树,不难发现,数组内的元素和链表节点都是Node<K,V>对象
HashMap的扩容机制
首先需要明白的是为什么需要扩容呢.直接固定数组长度,然后有冲突使用链表或者红黑树不是也可以吗.
的确可以这么处理,但是这样做的话当元素很多的时候哈希冲突导致的链化会影响查询效率,而扩容操作可以极大缓解这一问题.为了减少频繁扩容操作导致的效率问题,通常是建议初始化时传入容量参数的.
扩容时机
肯定是在put操作时需要进行扩容,分为两种情况:
- HashMap 中 put 第一个元素,初始化数组 table。
- HashMap 中的元素数量大于阈值 threshold。
关键源码resize()
1 |
|
可以看到,HashMap扩容分为两个步骤:1.计算获得新容量、新扩容阈值及新容量的空数组;2.新旧数组元素迁移,这里才是真正的扩容操作; 看完源代码几个问题萦绕心头:
-
为什么Node数组和阈值初始化不是放在构造函数里而是放在了扩容方法resize()里实现? JDK1.8之前倒是直接在构造函数里初始化的,那么这里改动了肯定有优化的考量,具体是为什么呢,还在寻找答案…
-
正常的扩容翻倍操作中为什么要加如下判断才进行阈值的翻倍?
1 |
|
要知道该条件无论是否成立newCap = oldCap << 1
都会执行的,(newCap = oldCap << 1) < MAXIMUM_CAPACITY
在绝大部分情况都会成立,那么需要思考的就是增加oldCap >= DEFAULT_INITIAL_CAPACITY
这一条件的原因.
经过实践发现:
1 |
|
- 初始化后扩容阈值threshold=2,首次put操作扩容后容量为newCap=2,threshold=1,然后添加第一个元素,size=1.
- 添加完第二个元素,size=2,2>threshold(1)触发扩容,如果没加
oldCap >= DEFAULT_INITIAL_CAPACITY
判断新容量newCap=2«1=4,阈值threshold=1«1=2,这跟容量*负载因子=阈值是不相符的. - 那在这里直接newThr=(float)newCap * loadFactor不好吗,为什么还得放在newThr == 0时进行处理,初步理解是为了减少代码量,并且直接在原阈值的基础上使用位移操作比乘法计算效率是更高的.
以上是自己思考的结果,无法确定是否完全正确😂
计算新容量、新阈值
首次扩容
因为四个构造方法都没有对数组table
进行初始化,在第一次put操作时才会对table
进行初始化.
- 除了
new HashMap()
,其他构造方法都对threshold
进行了初始化,此时新容量newCap=oldThr=threshold
,此时新容量不一定等于new一个HashMap指定的容量initialCapacity
,而是与tableSizeFor(int cap)
方法有关,它总是2的幂次方,新阈值threshold=newCap*loadFactor
- 使用
new HashMap()
时newCap=DEFAULT_INITIAL_CAPACITY=16,threshold=12
.
非首次
- 先判断旧的数组容量是否达到最大值,如果达到返回旧数组不进行后续扩容操作
-
扩容后小于最大容量并且旧容量>=16时,新扩容阈值为旧扩容阈值的两倍,需要注意的是,不管条件是否成立,
newCap = oldCap << 1
这一赋值一定会执行,即此时扩容是肯定的,条件不成立时新扩容阈值如下:1
2
3
4
5if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); }
数组迁移
1 |
|
这里牵涉到hash寻址算法、高低位拆分扩容和与(&)操作等,其中高低位拆分扩容是关键.以前没看过源码的时候以为扩容就是单纯的数组扩容,然后后面多出的空位可以添加新的元素,原来不仅如此还需要对链表进行拆分并将它们重新索引到新的下标.
高低位拆分扩容
进行高低位拆分是为了降低原链表的长度,缓解哈希冲突导致的查询效率的下降.那么为什么根据(e.hash & oldCap) 等于0或1
就可以将原先的一条链表拆分成两条,然后存储到不同数组索引下面,这点还没弄明白…
LinkedHashMap
LinkedHashMap继承自HashMap,除了重写部分方法,其他都是直接使用的HashMap的方法.相较HashMap的区别就是多了一个双向链表,并且它是有序的,因为它的遍历是对双向链表的遍历,因此如果需要有序的HashMap可以使用LinkedHashMap
数据结构
LinkedHashMap=HashMap+双向链表,每次putVal()操作时,如果添加成功都会把当前Node对象加入到双向链表中去
LinkedHashMap的有序其实包括2种:
- 插入顺序:很好理解,就是按插入顺序储存,当accessOrder = false时成立。
- 访问顺序:当accessOrder = true时,被访问的元素会放到链表的尾端,其他元素顺序不变。
关键源码
1 |
|
LinkedHashMap并没有重写putVal()
方法,而是重写了afterNodeInsertion()
、afterNodeAccess()
和afterNodeRemoval()
方法,这三个方法在HashMap中是空的.
访问顺序的遍历问题
所有集合在迭代器模式中遍历输出时是不允许修改集合结构的,也就是说LinkedHashMap在迭代遍历时同其他集合一样无法使用remove、put这种改变链表长度的方法
由于访问顺序的特殊性,每次有get操作获取元素时,被访问的元素会放到链表的尾端,因此LinkedHashMap在这种模式下迭代遍历时不能使用get方法,这样会改变了链表的结构,会抛出ConcurrentModificationException
异常.
TreeMap
可以看到TreeMap与其他实现类相比多出了一个实现的接口NavigableMap
,并且它继承自SortedMap
接口.TreeMap不允许null key(未自定义比较器并对null处理),允许重复的null value,由于其底层数据结构是一颗平衡二叉查找树(红黑树),因此它是有序的(默认根据key自然排序),同样它是非线程安全的.
数据结构
TreeMap的底层数据结构是红黑树,红黑树是一种平衡二叉搜索树.
1 |
|
添加节点
1 |
|
根据源码可以看出,put操作分为插入数据和调整红黑树两步.
插入数据
分为两种情况:
- 一种是树为空,直接把新节点赋值给根节点就行
- 另一种是树非空,则需要循环遍历树中的节点,将新插入的key与其比较,比它小往左子树走,比它大往右子树走,若相等则覆盖原先的value值;遍历完成后若没有相同key的情况,将新节点插入到最后遍历到的那个节点的左边或者右边.不难发现,新节点的一定是插入到原先叶子节点上的.
- 特别的,在进行元素的比较时有两种情况:
- 传入了自定义比较器,使用比较器重写的compare方法
- 未传入比较器时先判断key是否为null,是的话直接抛出异常,否则将key强转成Comparable对象,未实现Comparable接口的对象会抛出异常.
调整红黑树
1 |
|
自然排序
Comparable接口强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序
例如String实现了Comparable接口,可以看到它会逐个字符比较,负数表示小于,正数表示大于,0为相等. 如果key是自定义的类,既没有实现Comparable接口,也没有传入比较器,TreeMap是无法添加的.
1 |
|
定制排序
那么如果不想使用上面那种排序比较方式呢,比如我想小于的时候返回正数,反之返回负数,如果是自己写的类还好,随便怎么实现Comparable接口,像String这种写好的类呢,方法也是有的,定义一个Comparator比较器,声明新TreeMap时将这个定制器作为参数传入即可.
1 |
|
HashTable
Hashtable是遗留类,很多映射的常用功能与HashMap类似,不同的是它承自Dictionary类,底层结构是数组+链表,并且是线程安全的,任一时间只有一个线程能写Hashtable,并发性不如ConcurrentHashMap。Hashtable不建议在新代码中使用,不需要线程安全的场合可以用HashMap替换,需要线程安全的场合可以用ConcurrentHashMap替换.
需要注意的是,Hashtable所有操作方法都使用synachronized关键字上锁了,包括get()、pulVal()、remove()、clear()等等.
ConcurrentHashMap
ConcurrentHashMap不允许null key和null value,它使用synachronized关键字+CAS实现了线程安全,数据结构与HashMap一样,都是数组+链表+红黑树.因此如果要使用线程安全的HashMap,一般使用这个.
与HashTable实现线程安全不同的是,它没有对整个方法使用synachronized,而是在putVal()中的关键代码中使用synachronized,并且对关键属性如数组table使用volatile关键字修饰保证可见性,从而能够实现读写一致而不用所有方法都加锁,相对HashTable更为轻量.