数据结构-Java Map 和 Set-2

数据结构-Java Map 和 Set-1

https://developer.aliyun.com/article/1517082

Map和Set搜索

概念

Map和set是一种专门用来进行搜索的容器或者数据结构，其搜索的效率与其具体的实例化子类有关

以前常见的搜索方式有：

1. 直接遍历，时间复杂度为O(N)，元素如果比较多效率会非常慢

2. 二分查找，时间复杂度为 O( ),但搜索前必须要求序列是有序的

上述排序比较适合静态类型的查找，即一般不会对区间进行插入和删除操作了，而现实中的查找比如：

1. 根据姓名查询考试成绩

2. 通讯录，即根据姓名查询联系方式

3. 不重复集合，即需要先搜索关键字是否已经在集合中

可能在查找时进行一些插入和删除的操作，即动态查找，那上述两种方式就不太适合了，本节介绍的Map和Set是一种适合动态查找的集合容器。

存储方式

和python中的Set和Dict类是类似的，他们有直接全部存储key的模型，和存放key-value键值对的模型：

1. key模型，例如：
   

• 快速查找一个单词是否在英文词典中
  
• 快速查找某个名字是否在通讯录中
  

2. key-value模型，比如：
   

• 统计某一篇英文短报中，单词的出现个数，key为单词，value为单词出现的个数，也可以称为权值
  
• 统计后楼梦中，个人物名字出现的次数，其key-value模型为<名字：次数>
  

Map是以key-value键值对的形式来存储，而Set使用的是key存储方式。

key-value：

key：

注意：Map可以看做是一种特殊的Set类型，Set中key不会出现重复元素，Map中的key也不会，但是Map中的每一个key都多了一个与之对应的value权重。

Map & Set 的使用

Map

概要

在前言中我们介绍过：

其中Map是单独的一个接口，没有继承自Collection，而Set接口继承Collection

单独的接口不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap

Map<String, Integer> treeMap = new TreeMap<>();

Map中传入类，以key-value的形式。其中key是唯一的，key不能有重复的，而value可以有重复的。

如果new 一个 TreeMap，那么就会以搜索树的方式插入。

• Map的put方法，向容器中存放key-value值
  
• Map重写了println和print方法，可以直接打印
  

public static void main(String[] args) {
        Map<String, Integer> treeMap = new TreeMap<>();
        treeMap.put("hello",3);
        treeMap.put("world",4);
        System.out.println(treeMap);
}

运行结果为：

相对应的根据传入的类，print或者println会进行重载，以适应不同的情况。

但是需要注意的是，对Map进行插入的时候key不能为null，否则会抛出空指针异常（NullPointerException）：

可比较性

对于Map中传入的key类，一定是可以比较的。

假设有一个student类：

class student {
    int age;
    String name;
    public student(int age, String name) {
        this.age = age;
        this.name = name;
    }
}

在key值中传入student类：

    public static void main(String[] args) {
        Map<student, Integer> treeMap = new TreeMap<>();
        treeMap.put(new student(18,"张三"),3);
        treeMap.put(new student(19,"李四"),4);
        System.out.println(treeMap);
    }

编译会抛出异常如下：

也就是说传入的student是无法比较的。

Map元素的访问

由于Map不是数组类型，无法通过treeMap[ i ]的形式访问，编译抛出异常：

java: 需要数组, 但找到java.util.Map<java.lang.String,java.lang.Integer>

使用for-each方法 来进行访问：

Map<String,Integer> treeMap = new TreeMap<>();

1. 访问所有key，使用Map中的keySet（）方法，返回Map中所有键值对key-value的key的集合
   

for(String e: treeMap.keySet()) {
            System.out.println(e);
}

访问所有的value，使用Map中的values（）方法，返回Map中所有键值对key-value 的value的集合

for(Integer e: treeMap.values()) {
            System.out.println(e);
}

注意：for-each迭代无法直接遍历Map这种字典类型数据：

Map的方法

Set

概要

Set继承与Collection接口，而Map是独立的，Set，相较于Map这种key-value的存放形式，Set只需要存放key一个关键字：key是唯一的

对于Set，我们也把他称为集合，集合是一种数学概念，集合由一个或多个确定的元素所构成的整体。

它具备如下性质：

1. 无序性，一个集合中，每个元素的地位都是相同的，元素之间是无序的。集合上可以定义序关系，定义了序关系后，元素之间就可以按照序关系排序。但就集合本身的特性而言，元素之间没有必然的序
2. 互异性，一个集合中，任何两个元素都认为是不相同的，即每个元素只能出现一次。有时需要对同一元素出现多次的情形进行刻画，可以使用多重集，其中的元素允许出现多次。

Set中的key同Map键值对key-value中的key一样，是无法直接修改的，如果要修改可以直接删除原来的key然后再重新添加即可。

Set的实现类有TreeSet和HashSet，还有LinkedHashSet，LinkedHashSet，他两是在HashSet的基础上维护的一个双向链表，用来记录元素的插入次序，让其在结构上有序。

互异性

有如下代码：其中add（Object x）;是向set中添加元素的意思。

    public static void main(String[] args) {
        Set<Integer> set1 = new TreeSet<>();
        set1.add(1);
        set1.add(2);
        set1.add(3);
        System.out.println(set1);
    }

我们在set集合中添加数字1,2,3。可以发现打印结果为：

如果往里面添加两个1呢？

    public static void main(String[] args) {
        Set<Integer> set1 = new TreeSet<>();
        set1.add(1);
        set1.add(1);
        System.out.println(set1);
    }

运行结果只有1。这就是其互异性

集合Set的一个最大的作用，就是根据它的互异性来去掉重复元素

Set元素的访问

同Map的key访问方法。使用for-each迭代器

Set的方法