有序的Map集合_map集合特点

有序的Map集合_map集合特点我们通常使用的Map集合是HashMap,在大多数情况下HashMap可以满足我们的要求,但是HashMap有一个缺点:HashMap是无序的,即其迭代顺序与其key或value的大小无关。而在某些情况下,如果我们需要Map集合里的元素有序,那么HashMap是不能满足我们的要求的。那么有没有有序的Map集合呢?有,Java提供了两种有序的Map集合:LinkedHashMap和TreeM…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

  我们通常使用的Map集合是HashMap,在大多数情况下HashMap可以满足我们的要求,但是HashMap有一个缺点:HashMap是无序的,即其迭代顺序与其key或value的大小无关。而在某些情况下,如果我们需要Map集合里的元素有序,那么HashMap是不能满足我们的要求的。

那么有没有有序的Map集合呢?有,Java提供了两种有序的Map集合:LinkedHashMapTreeMap

(一)LinkedHashMap

LinkedHashMap继承了HashMap,是HashMap的子类。

有序的Map集合_map集合特点

其实LinkedHashMap与HashMap区别不大,也是通过计算键的hash值,映射到hash表中,那么LinkedHashMap是如何实现有序的呢?

LinkedHashMap不仅维护着一个hash表,而且还维护着一个双向链表,而这个双向链表里的元素就是有序的。

LinkedHashMap的Entry继承于HashMap的Entry,并且增加了before和after属性。

有序的Map集合_map集合特点

 

可以看到before和after的类型都是Entry,LinkedHashMap通过before和after来构建双向链表。

LinkedHashMap的内部结构如图所示:

有序的Map集合_map集合特点

 

LinkedHashMap有两种排序方式:插入排序和访问排序(修改或访问一个元素后,将该元素移到队列末尾),默认是插入排序。使用accessOrder来标记使用哪种排序方式,accessOrder==true时,表示使用访问排序默认为false;注意:LinkedHashMap的有序不是keyvalue的自然顺序

LinkedHashMap的插入:

put():

LinkedHashMap的put方法和HashMap的相同,不过LinkedHashMap重写了newNode方法,在插入时,会判断双向链表是否为空,如果为空,则将该Entry作为头结点head,否则在双向链表末尾插入该Entry;如果更新值(key相同),则会判断accessOrder是否为true,如果为true,则将该Entry移到双向队列的尾部。

get():

LinkedHashMap在get的时候,会判断accessOrder是否为true,即是否按访问顺序排序,如果是true,则会把该Entry移到双向队列的尾部。然后再返回value。

LinkedHashMap的迭代:

LinkedHashMapIterator实现了迭代器的功能,其是对双向循环链表的遍历操作。但是这个迭代器是abstract的,不能直接被对象所用。

有序的Map集合_map集合特点

LinkedHashMap中的LinkedKeyIteratorLinkedValueIteratorLinkedEntryIterator都继承了LinkedHashMapIterator,并且实现了Iterator接口,我们可以使用上面三种迭代器来迭代keyvalueentry三种迭代器迭代的是同一个双向链表,即迭代的元素是相同的,只是返回的类型不同。

 

遍历TreeMap的键值对

LinkedHashMap map = new LinkedHashMap();
Integer integ = null;
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
    Map.Entry entry = (Map.Entry)iter.next();
    // 获取key
    key = (String)entry.getKey();
        // 获取value
    integ = (Integer)entry.getValue();
}

(二)TreeMap

TreeMap也是一个有序的Map集合,其底层是一颗红黑树,该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。

有序的Map集合_map集合特点

TreeMap的Entry结构如下:

有序的Map集合_map集合特点

可以看出来TreeMap的Entry其实是一个树节点,构建了一颗红黑树。而entry的插入,就是在红黑树中新增一个节点,并调整红黑树。

TreeMap的插入:

put():

如果Comparator 为空,会使用key进行比较,按照从小到大的次序插入到红黑树中。

如果Comparator 不为空,则根据Comparator来进行比较。

TreeMap的迭代:

有序的Map集合_map集合特点

PrivateEntryIterator实现了迭代器的功能,其是对红黑树进行遍历,返回的是红黑树中的有序序列。但是这个迭代器是abstract的,不能直接被对象所用。迭代时使用的是EntryIterator,ValueIterator,KeyIterator等迭代器。

有序的Map集合_map集合特点

除了顺序遍历,TreeMap还可以逆序遍历,由于TreeMap中的元素是从小到大的顺序排列的。因此,顺序遍历,就是从第一个元素开始,逐个向后遍历;而倒序遍历则恰恰相反,它是从最后一个元素开始,逐个往前遍历。

有序的Map集合_map集合特点

 

遍历TreeMap的键值对

TreeMap map = new TreeMap ();
Integer integ = null;
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
    Map.Entry entry = (Map.Entry)iter.next();
    // 获取key
    key = (String)entry.getKey();
        // 获取value
    integ = (Integer)entry.getValue();
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/192963.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号