Java集合框架源码剖析:LinkedHashSet 和 LinkedHashMap

总体介绍

如果你已看过前面关于HashSetHashMap,以及TreeSetTreeMap的讲解,一定能够想到本文将要讲解的LinkedHashSetLinkedHashMap其实也是一回事。LinkedHashSetLinkedHashMap在Java里也有着相同的实现,前者仅仅是对后者做了一层包装,也就是说LinkedHashSet里面有一个LinkedHashMap(适配器模式)。因此本文将重点分析LinkedHashMap

LinkedHashMap实现了Map接口,即允许放入keynull的元素,也允许插入valuenull的元素。从名字上可以看出该容器是linked listHashMap的混合体,也就是说它同时满足HashMaplinked list的某些特性。可将LinkedHashMap看作采用linked list增强的HashMap

LinkedHashMap_base.png

事实上LinkedHashMapHashMap的直接子类,二者唯一的区别是LinkedHashMapHashMap的基础上,采用双向链表(doubly-linked list)的形式将所有entry连接起来,这样是为保证元素的迭代顺序跟插入顺序相同。上图给出了LinkedHashMap的结构图,主体部分跟HashMap完全一样,多了header指向双向链表的头部(是一个哑元),该双向链表的迭代顺序就是entry的插入顺序

除了可以保迭代历顺序,这种结构还有一个好处:迭代LinkedHashMap时不需要像HashMap那样遍历整个table,而只需要直接遍历header指向的双向链表即可,也就是说LinkedHashMap的迭代时间就只跟entry的个数相关,而跟table的大小无关。

有两个参数可以影响LinkedHashMap的性能:初始容量(inital capacity)和负载系数(load factor)。初始容量指定了初始table的大小,负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时,容器将自动扩容并重新哈希。对于插入元素较多的场景,将初始容量设大可以减少重新哈希的次数。

将对象放入到LinkedHashMapLinkedHashSet中时,有两个方法需要特别关心:hashCode()equals()hashCode()方法决定了对象会被放到哪个bucket里,当多个对象的哈希值冲突时,equals()方法决定了这些对象是否是“同一个对象”。所以,如果要将自定义的对象放入到LinkedHashMapLinkedHashSet中,需要*@Override*hashCode()equals()方法。

通过如下方式可以得到一个跟源Map 迭代顺序一样的LinkedHashMap

出于性能原因,LinkedHashMap是非同步的(not synchronized),如果需要在多线程环境使用,需要程序员手动同步;或者通过如下方式将LinkedHashMap包装成(wrapped)同步的:

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

方法剖析

get()

get(Object key)方法根据指定的key值返回对应的value。该方法跟HashMap.get()方法的流程几乎完全一样,读者可自行参考前文,这里不再赘述。

put()

put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找,看是否包含该元组,如果已经包含则直接返回,查找过程类似于get()方法;如果没有找到,则会通过addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry

注意,这里的插入有两重含义

  1. table的角度看,新的entry需要插入到对应的bucket里,当有哈希冲突时,采用头插法将新的entry插入到冲突链表的头部。
  2. header的角度看,新的entry需要插入到双向链表的尾部。

LinkedHashMap_addEntry.png

addEntry()代码如下:

上述代码中用到了addBefore()方法将新entry e插入到双向链表头引用header的前面,这样e就成为双向链表中的最后一个元素。addBefore()的代码如下:

上述代码只是简单修改相关entry的引用而已。

remove()

remove(Object key)的作用是删除key值对应的entry,该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的entry,然后删除该entry(修改链表的相应引用)。查找过程跟get()方法类似。

注意,这里的删除也有两重含义

  1. table的角度看,需要将该entry从对应的bucket里删除,如果对应的冲突链表不空,需要修改冲突链表的相应引用。
  2. header的角度来看,需要将该entry从双向链表中删除,同时修改链表中前面以及后面元素的相应引用。

LinkedHashMap_removeEntryForKey.png

removeEntryForKey()对应的代码如下:

LinkedHashSet

前面已经说过LinkedHashSet是对LinkedHashMap的简单包装,对LinkedHashSet的函数调用都会转换成合适的LinkedHashMap方法,因此LinkedHashSet的实现非常简单,这里不再赘述。

打赏支持我写出更多好文章,谢谢!

打赏作者

打赏支持我写出更多好文章,谢谢!

1 3 收藏 1 评论

关于作者:CarpenterLee

中国科学院计算技术研究所在读硕士,从事高性能计算、大数据等领域。 个人主页 · 我的文章 · 7 ·    

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部