大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
我们通常使用的Map集合是HashMap,在大多数情况下HashMap可以满足我们的要求,但是HashMap有一个缺点:HashMap是无序的,即其迭代顺序与其key或value的大小无关。而在某些情况下,如果我们需要Map集合里的元素有序,那么HashMap是不能满足我们的要求的。
那么有没有有序的Map集合呢?有,Java提供了两种有序的Map集合:LinkedHashMap和TreeMap;
(一)LinkedHashMap
LinkedHashMap继承了HashMap,是HashMap的子类。
其实LinkedHashMap与HashMap区别不大,也是通过计算键的hash值,映射到hash表中,那么LinkedHashMap是如何实现有序的呢?
LinkedHashMap不仅维护着一个hash表,而且还维护着一个双向链表,而这个双向链表里的元素就是有序的。
LinkedHashMap的Entry继承于HashMap的Entry,并且增加了before和after属性。
可以看到before和after的类型都是Entry,LinkedHashMap通过before和after来构建双向链表。
LinkedHashMap的内部结构如图所示:
LinkedHashMap有两种排序方式:插入排序和访问排序(修改或访问一个元素后,将该元素移到队列末尾),默认是插入排序。使用accessOrder来标记使用哪种排序方式,accessOrder==true时,表示使用访问排序,默认为false;注意:LinkedHashMap的有序不是key或value的自然顺序。
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的,不能直接被对象所用。
LinkedHashMap中的LinkedKeyIterator,LinkedValueIterator,LinkedEntryIterator都继承了LinkedHashMapIterator,并且实现了Iterator接口,我们可以使用上面三种迭代器来迭代key,value,entry。三种迭代器迭代的是同一个双向链表,即迭代的元素是相同的,只是返回的类型不同。
遍历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 进行排序,具体取决于使用的构造方法。
TreeMap的Entry结构如下:
可以看出来TreeMap的Entry其实是一个树节点,构建了一颗红黑树。而entry的插入,就是在红黑树中新增一个节点,并调整红黑树。
TreeMap的插入:
put():
如果Comparator 为空,会使用key进行比较,按照从小到大的次序插入到红黑树中。
如果Comparator 不为空,则根据Comparator来进行比较。
TreeMap的迭代:
PrivateEntryIterator实现了迭代器的功能,其是对红黑树进行遍历,返回的是红黑树中的有序序列。但是这个迭代器是abstract的,不能直接被对象所用。迭代时使用的是EntryIterator,ValueIterator,KeyIterator等迭代器。
除了顺序遍历,TreeMap还可以逆序遍历,由于TreeMap中的元素是从小到大的顺序排列的。因此,顺序遍历,就是从第一个元素开始,逐个向后遍历;而倒序遍历则恰恰相反,它是从最后一个元素开始,逐个往前遍历。
遍历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账号...