浅笑博客
这么说这些寒酸、贫弱、简陋、可怜的积蓄就是你的全部财产?
浅笑博客
Java进阶学习——集合框架之图
Java进阶学习——集合框架之图

关于Java集合框架的介绍,上节已有详细说明。本节主要对Java集合框架的第二个容器——图进行深入学习和介绍。

图(Map)

图是一种按照键值存储条目的容器。键值类似下标,在List中,下标即整数,而在Map中,键值可以是任意类型的对象。且在Map中要求不能有重复的键值。每个键值对应一个值,与其构成一个条目,存储在图中。

图有3中类型:

散列图( HashMap )

链式散列图(LinkedHashMap)

树形图(TreeMap)

关于图(Map)的框架,我画了一张关系图, 以方便了解集合框架图中各类与接口之间的相互关系 :

http://blog.qianxiao.fun/wp-content/uploads/2020/05/Map-1024x400.png

其中椭圆表示接口、虚线圆角矩形表示抽象类、实线圆角矩形表示具体类。实线箭头表示继承,虚线箭头表示实现接口。

Map接口提供了查询、更新和获取集合值和键值的方法。查询如isEmpty、containsKey、containsValue等,更新如put、remove、clear等方法,用于获取键的规则集的KeySet方法、用于获取值的集合的values方法以及用于获取键值对Entry对象的集合的方法entrySet方法。

AbstractMap是实现了Map接口部分方法(除entrySet方法之外的所有方法)的抽象便利类。

SortedMap接口是保持映射以键值升序的顺序排列的Map的扩展接口,可确保图中的条目是排序好的。额外提供了firstKey方法、lastKey方法、headMap方法(返回键值<某值的那部分图)和tailMap方法(返回键值≥某值的那部分图)。

NavigableMap接口扩展自SortedMap,提供了导航方法lowerKey、floorKey、ceilingKey、higherKey分别返回<、≤、≥、>某值的键值,如无返回null。还提供了pollFirstEntry方法和pollLastEntry方法。

下面分别对Map接口的3个具体实现类进行介绍和学习。在次之前首先介绍下Entry条目。

条目(Entry)

图中所谓的键值对,其实就是Entry,它是Map接口中了一个内部接口。可以理解图中的每个键值对就是一个Entry对象。在我个人看来,从一定程度上,其实图也是一个集合,它的元素即为Entry对象。一个Map<K,V>可以一定程度理解为Set<Map.Entry<K,V>>。

Entry接口有getKey方法、getValue方法和setValue方法等,分别用于返回条目的键值、值、设置新的值等。

散列图(HashMap)

同规则集Set接口的具体实现类HashSet,用来存储互不相同的东西,HashSet存储的是互不相同的元素,而HashMap存储的是互不相同的键值对。

对于定位一个值、插入一个映射以及删除一个映射,使用HashMap是高效的。

下面时散列图HashMap的一个简单程序示例:

import java.util.*;

public class Main{
    public static void main(String[] args) {
        HashMap<String,Integer> hashMap = new HashMap<>();
        hashMap.put("A",12);
        hashMap.put("C",16);
        //put返回覆盖的值,如无返回null
        System.out.println(hashMap.put("A",13));//12
        System.out.println(hashMap.put("B",16));//null
        //replace,如某键存在,同put,替换某键对应的值。如不存在返回null,不会添加
        System.out.println(hashMap.replace("B",15));//返回原来的16并将16改为15
        System.out.println(hashMap.replace("E",19));//null(不会添加E)
        //如果replace为3个参数,当且仅当key存在且值=oldValue时才替换并return true,否则,return false
        System.out.println(hashMap.replace("D",11,17));//false
        System.out.println(hashMap.replace("C",11,17));//false
        System.out.println(hashMap.replace("C",16,17));//true 并将C的值改为17
        System.out.println(hashMap);//{A=13, B=15, C=17}
        System.out.println(hashMap.size());//3
        System.out.println(hashMap.containsKey("F"));//false
        System.out.println(hashMap.containsKey("B"));//true
        System.out.println(hashMap.containsValue(13));//true
        System.out.println(hashMap.containsValue(16));//false
        Set<String> keys = hashMap.keySet();
        System.out.println(keys);//[A, B, C]
        Collection<Integer> vals = hashMap.values();
        System.out.println(vals);//[13, 15, 17]
        Set<Map.Entry<String,Integer>> entrys = hashMap.entrySet();
        System.out.println(entrys);//[A=13, B=15, C=17]
        //get获取对应键的值,如不存在则返回null
        System.out.println(hashMap.get("D"));//null
        System.out.println(hashMap.get("C"));//17
        //getOrDefault获取对应键的值,如不存在则返回设定的默认值
        System.out.println(hashMap.getOrDefault("D",0));//0
    }
}

输出:

12
null
16
null
false
false
true
{A=13, B=15, C=17}
3
false
true
true
false
[A, B, C]
[13, 15, 17]
[A=13, B=15, C=17]
null
17
0

链式散列图(LinkedHashMap)

LinkedHashMap类是HashMap的派生类,用链表实现拓展了HashMap。支持Entry可以按照它们插入图的顺序排序(插入顺序),也支持它们被最后一次访问时从最早到最晚的顺序(访问顺序)。

注意在需要创建按访问顺序排序的LinkedHashMap时,需要用构造方法LinkedHashMap(initialCapacity,loadFactor,true),尤其是第三个参数规定了accessOrder为true。默认构造创建的LinkedHashMap中accessOrder的值默认设为false。关于构造函数中的 initialCapacity 和 loadFactor 分别为初始容量和客座率,在上一节中提到过。

下面时一个LinkedHashMap的简单程序示例:

import java.util.*;

public class Main{
    public static void main(String[] args) {
        HashMap<String,Integer> hashMap = new HashMap<>();
        hashMap.put("A",13);
        hashMap.put("B",15);
        LinkedHashMap<String,Integer> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put("C",11);
        linkedHashMap.put("E",18);
        linkedHashMap.putAll(hashMap);
        linkedHashMap.put("F",12);
        //其他的一些常用方法同HashSet,不再赘述
        System.out.println(linkedHashMap);

        //使用访问顺序创建LinkedHashMap,关键为第三个参数设置了accessOrder = true,10为初始容量,0.75为客座率
        LinkedHashMap<String,Integer> accessOrderLinkedHashMap = new LinkedHashMap<>(10,0.75f,true);
        accessOrderLinkedHashMap.put("C",1);
        accessOrderLinkedHashMap.put("B",2);
        accessOrderLinkedHashMap.put("D",3);
        accessOrderLinkedHashMap.put("A",4);
        accessOrderLinkedHashMap.get("D");
        accessOrderLinkedHashMap.get("C");
        System.out.println(accessOrderLinkedHashMap);
        //迭代器遍历
        Iterator<Map.Entry<String,Integer>> iterator = accessOrderLinkedHashMap.entrySet().iterator();
        while (iterator.hasNext()){
            Map.Entry<String,Integer> entry = iterator.next();
            System.out.println(entry.getKey()+" = "+entry.getValue());
        }
    }
}

输出:

{C=11, E=18, A=13, B=15, F=12}
{B=2, A=4, D=3, C=1}
B = 2
A = 4
D = 3
C = 1

可以发现在设置开启访问顺序后,get操作会将访问的条目置至map的最后。最终输出顺序为条目访问的先后顺序(访问顺序)。在使用访问顺序的LinkedHashMap时,需要注意不要忽视了这一点。

如我们在使用下面的这种遍历时:

import java.util.*;

public class Main{
    public static void main(String[] args) {
        //使用访问顺序创建LinkedHashMap,关键为第三个参数设置了accessOrder = true,10为初始容量,0.75为客座率
        LinkedHashMap<String,Integer> accessOrderLinkedHashMap = new LinkedHashMap<>(10,0.75f,true);
        accessOrderLinkedHashMap.put("C",1);
        accessOrderLinkedHashMap.put("B",2);
        accessOrderLinkedHashMap.put("D",3);
        accessOrderLinkedHashMap.put("A",4);
        accessOrderLinkedHashMap.get("D");
        accessOrderLinkedHashMap.get("C");
        System.out.println(accessOrderLinkedHashMap);
        //迭代器遍历
        Iterator<Map.Entry<String,Integer>> iterator = accessOrderLinkedHashMap.entrySet().iterator();
        while (iterator.hasNext()){
            Map.Entry<String,Integer> entry = iterator.next();
            System.out.println(entry.getKey()+" = "+accessOrderLinkedHashMap.get(entry.getKey()));//注意使用了get
        }
    }
}

此时会意外发现,程序在输出了第一个条目后报抛ConcurrentModificationException异常。

树形图(TreeMap)

TreeMap类一般用于存储可排序的键值对。可选择使用Comparable接口或Comparator接口分别排序成自然顺序和比较器顺序。其在遍历排号顺序的键值对时是高效的。如使用构造方法TreeMap(Comparator comparator)创建使用自定义比较器的有序图。

下面时一个简单的程序示例:

import java.util.*;

public class Main{
    public static void main(String[] args) {
        TreeMap<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("F",12);
        treeMap.put("A",11);
        treeMap.put("D",10);
        treeMap.put("B",15);
        treeMap.put("C",16);
        System.out.println(treeMap);
        TreeMap<String,Integer> treeMap2 = new TreeMap<>(Collections.reverseOrder());
        treeMap2.put("F",12);
        treeMap2.put("A",11);
        treeMap2.put("D",10);
        treeMap2.put("B",15);
        treeMap2.put("C",16);
        System.out.println(treeMap2);
        System.out.println("treeMap.firstKey() = " + treeMap.firstKey());
        System.out.println("treeMap.lastKey() = " + treeMap.lastKey());;
        //headMap和tailMap返回的类型为SortedMap接口对象
        System.out.println("treeMap.headMap(\"C\") = " + treeMap.headMap("C"));//小于C的部分
        System.out.println("treeMap.tailMap(\"C\") = " + treeMap.tailMap("C"));//大于等于C的部分
        //higherKey、lowerKey、floorKey、ceilingKey返回的是一个值
        System.out.println("treeMap.higherKey(\"C\") = " + treeMap.higherKey("C"));//大于C的最小值
        System.out.println("treeMap.lowerKey(\"C\") = " + treeMap.lowerKey("C"));//小于C的最大值
        System.out.println("treeMap.floorKey(\"C\") = " + treeMap.floorKey("C"));//小于等于C的最大值
        System.out.println("treeMap.ceilingKey(\"C\") = " + treeMap.ceilingKey("C"));//大于等于C的最小值
        //higherKey、lowerKey、floorKey、ceilingKey如没有符合条件的,则返回null
        System.out.println("treeMap.ceilingKey(\"H\") = " + treeMap.ceilingKey("H"));//大于等于H的最小值
        //pollFirstEntry和pollLastEntry
        System.out.println("treeMap.pollFirstEntry() = \"" + treeMap.pollFirstEntry()+"\"");//删除并返回First
        System.out.println("treeMap.pollLastEntry() = \"" + treeMap.pollLastEntry()+"\"");//删除并返回Last
    }
}

输出:

{A=11, B=15, C=16, D=10, F=12}
{F=12, D=10, C=16, B=15, A=11}
treeMap.firstKey() = A
treeMap.lastKey() = F
treeMap.headMap("C") = {A=11, B=15}
treeMap.tailMap("C") = {C=16, D=10, F=12}
treeMap.higherKey("C") = D
treeMap.lowerKey("C") = B
treeMap.floorKey("C") = C
treeMap.ceilingKey("C") = C
treeMap.ceilingKey("H") = null
treeMap.pollFirstEntry() = "A=11"
treeMap.pollLastEntry() = "F=12"

可以看到,使用TreeMap默认是根据Key的默认Comparater接口的方法排序生成的自然顺序。上面代码12行,用比较器构造函数,传入Collections.reverseOrder()生成的逆自然顺序比较器,使TreeMap使用逆自然顺序的比较器顺序。当然也可以自己写一个Comparator接口实例传入。

后面为一些SortedMap接口中的一些方法以及NavigableMap接口中的一些导航方法的使用。

总结

以上三点介绍并用实例叙述了3种图的类型,那什么时候分别要用什么类型呢?通常情况下,如果更新图时不需要保持图中条目的顺序,使用HashMap。如果需要保持图中条目的插入顺序或访问顺序,则使用LinkedHashMap。如果需要使图中的条目按照键值排序,则使用TreeMap。

程序实例

题目:编程以统计一个文本中单词出现的次数,然后按照单词的属性a大小的升序显示这些单词以及它们出现的次数。一个单词的属性a定义为单词中所有字母Ascii码的数值的和,字母不区分大小写,大写转小写。(本题为我自改的,原题目只需按单词的字典序显示)

分析:

显然用键值对存储的图(可按照键值排序条目的图(TreeMap))来解决这个问题比较方便。因为首先使用键值对存储方便记录,同时使用TreeMap方便排序。

这里由于我改成了按单词的特定属性排序,所以为了方便,需将单词封装成一个类。以方便获取属性a值以及实现Comparater接口。

代码:

import java.util.*;

public class Main{
    public static void main(String[] args) {
        String text = "Good morinig. Have a good class. "+
                "Have a good visit. Have fun!";
        //由于Word的Comparater接口的比较方法定义为了降序,这里传入逆自然顺序比较器,以生成逆自然顺序的比较器顺序
        TreeMap<Word,Integer> treeMap = new TreeMap<>(Collections.reverseOrder());
        //句子划分成单词
        String[] words = text.split("[ \n\t\r.,;:!?(){]");
        for (String word : words) {
            //划分后可能有空格,进行过滤
            if(!"".equals(word.trim())){
                Word myWord = new Word(word.toLowerCase());
                //如果不存在添加进去值为1,如果存在覆盖添加值+1
                treeMap.put(myWord, treeMap.containsKey(myWord)?treeMap.get(myWord) +1:1);
            }
        }
        System.out.println(treeMap);
    }
}

/**
 * 封装单词类,方便统计属性a值
 * 要做TreeMap的kKey,必须实现比较接口用于在TreeMap中比较生成自然顺序,也可以在使用比较器构造函数时传入比较器接口实例
 * 因为Word要做Map的Key,所以必须重写hashCode和equals
 * 为了方便sout快速输出,重写toString方法
 */
class Word implements Comparable<Word>{
    String word;
    int a = 0;

    Word(String word){
        this.word = word;
        for (char wordChar : word.toCharArray()) {
            a += wordChar;
        }
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        Word word1 = (Word) o;
        return a == word1.a &&
                word.equals(word1.word);
    }

    @Override
    public int hashCode() {
        return Objects.hash(word, a);
    }

    @Override
    public int compareTo(Word o) {
        if(o.a>this.a){
            return 1;
        }
        return o.a==this.a?0:-1;
    }

    @Override
    public String toString() {
        return word+"("+a+")";
    }
}

输出:

{a(97)=2, fun(329)=1, have(420)=3, good(425)=3, class(534)=1, visit(559)=1, morinig(757)=1}

如果本文有任何错误,欢迎不吝指正。如有任何建议想法,欢迎评论交流。

发表评论

textsms
account_circle
email

浅笑博客

Java进阶学习——集合框架之图
关于Java集合框架的介绍,上节已有详细说明。本节主要对Java集合框架的第二个容器——图进行深入学习和介绍。 图(Map) 图是一种按照键值存储条目的容器。键值类似下标,在List中,…
扫描二维码继续阅读
2020-05-10