首页 > 其他 > 详细

实现HashMap的顺序存储

时间:2021-09-08 20:19:33      阅读:16      评论:0      收藏:0      [点我收藏+]

从Java API知道,LinkedHashMap继承于HashMap,并且通过双向链表保存各节点的位置信息,实现了顺序存储。但是如果让你自己写一个顺序存储的HashMap,将如何下手呢?从研究LinkedHashMap的源码开始入手,究竟它比HashMap多了哪些东西,让它拥有了顺序存储的能力。

1.放入元素(put)

从放入一个元素开始,即最常见的V put(K key, V value)方法入手,LinkedHashMap并没有重写HashMap的put方法,但是它重写了最关键的Node<K, V> newNode(int hash, K key, V value, Node next)方法,该方法首先创建一个HashMap.Node的子类LinkedHashMap.Entry,它比Node多了两个指针Entry<K, V> before, after;//用于保存前后两个节点的信息:

LinkedHashMap.Entry<K, V>内部类

其次,把要放入的元素插入双向链表的表尾:

增加元素到双向链表的末尾

注意:LinkedHashMap拥有两个瞬时的属性transient LinkedHashMap.Entry<K,V> tail;//用于保存上一个元素,即表尾;transient LinkedHashMap.Entry<K, V> head;//用于保存第一个元素,即表头。

2.遍历元素(entrySet)

LinkedHashMap重写了Map接口的Set<Map.Entry<K, V> entrySet()方法,并返回自己的内部类class LinkedEntrySet extends AbstractSet<Map.Entry<K, V>>对象。它使用LinkedEntryIterator迭代器进行遍历,它继承于自己的abstract class LinkedHashIterator抽象类。该迭代器拥有两个Entry的指针next和current,并结合Entry中的before和after指针,实现了LinkedHashMap中元素的顺序遍历。

下面可以看下LinkedHashIterator的nextNode方法的实现:

LinkedHashIterator的nextNode方法

正是nextNode方法使用了LinkedHashMap.Entry<K, V>的after属性,使得iterator的遍历按照放入顺序进行的。

3.获取元素(get)

LinkedHashMap重写了Map接口的V get(Object key)方法,该方法分两个步骤:1.调用父类HashMap的getNode(hash(key),key)方法,获取value;2.如果accessOrder为true(默认为false),那么移动所访问的元素到表尾,并修改head和tail的值:

访问后重排序(accessOrder)

实现HashMap的顺序存储

原文:https://www.cnblogs.com/cqqfboy/p/15238262.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!