Map映射

Map映射

将键映射到值的对象。一个映射不能包含重复的键；每个键最多只能映射到一个值。

Collection只管存储元素
Map既要存储元素value 也要管理该元素对应的索引key(不可变类)

Map这种键值（key-value）映射表的数据结构，作用就是能高效通过key快速查找value（元素）

Map是一种键-值映射表，当我们调用put(K key, V value)方法时，就把key和value做了映射并放入Map。当我们调用V get(K key)时，就可以通过key获取到对应的value。如果key不存在，则返回null。和List类似，Map也是一个接口，最常用的实现类是HashMap。

如果只是想查询某个key是否存在，可以调用boolean containsKey(K key)方法。

复放入key-value并不会有任何问题，但是一个key只能关联一个value。

put()方法的签名是V put(K key, V value)，如果放入的key已经存在，put()方法会返回被删除的旧的value，否则，返回null。

Map中不存在重复的key，因为放入相同的key，只会把原有的key-value对应的value给替换掉。

功能方法

遍历Map

对Map来说，要遍历key可以使用for each循环遍历Map实例的keySet()方法返回的Set集合，它包含不重复的key的集合：

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("apple", 123);
        map.put("pear", 456);
        map.put("banana", 789);
        for (String key : map.keySet()) {
            Integer value = map.get(key);
            System.out.println(key + " = " + value);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

同时遍历key和value可以使用for each循环遍历Map对象的entrySet()集合，它包含每一个key-value映射：

public class Main {
    public static void main(String[] args) {
        Map map = new HashMap<>();
        map.put("apple", 123);
        map.put("pear", 456);
        map.put("banana", 789);
        for (Map.Entry entry : map.entrySet()) {
            String key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println(key + " = " + value);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Map和List不同的是，Map存储的是key-value的映射关系，并且，它不保证顺序。在遍历的时候，遍历的顺序既不一定是put()时放入的key的顺序，也不一定是key的排序顺序。

TreeMap

基于红黑树（Red-Black tree）的 NavigableMap 实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。

红黑树 禁止null key禁止null 自然排序有序映射 不安全

常用方法

增添元素

• V put(K key, V value)：将指定映射放入该TreeMap中
• V putAll(Map map)：将指定map放入该TreeMap中

删除元素

• void clear()：清空TreeMap中的所有元素
• V remove(Object key)：从TreeMap中移除指定key对应的映射

修改元素

• V replace(K key, V value)：替换指定key对应的value值
• boolean replace(K key, V oldValue, V newValue)：当指定key的对应的value为指定值时，替换该值为新值

查找元素

• boolean containsKey(Object key)：判断该TreeMap中是否包含指定key的映射
• boolean containsValue(Object value)：判断该TreeMap中是否包含有关指定value的映射
• Map.Entry firstEntry()：返回该TreeMap的第一个（最小的）映射
• K firstKey()：返回该TreeMap的第一个（最小的）映射的key
• Map.Entry lastEntry()：返回该TreeMap的最后一个（最大的）映射
• K lastKey()：返回该TreeMap的最后一个（最大的）映射的key
• v get(K key)：返回指定key对应的value
• SortedMap headMap(K toKey)：返回该TreeMap中严格小于指定key的映射集合
• SortedMap subMap(K fromKey, K toKey)：返回该TreeMap中指定范围的映射集合（大于等于fromKey，小于toKey）

遍历接口

• Set> entrySet()：返回由该TreeMap中的所有映射组成的Set对象
• void forEach(BiConsumer action)：对该TreeMap中的每一个映射执行指定操作
• Collection values()：返回由该TreeMap中所有的values构成的集合

其他方法

• Object clone()：返回TreeMap实例的浅拷贝
• Comparator comparator()：返回给该TreeMap的keys排序的comparator，若为自然排序则返回null
• int size()：返回该TreepMap中包含的映射的数量

使用TreeMap时，放入的Key必须实现Comparable接口。String、Integer这些类已经实现了Comparable接口，因此可以直接作为Key使用。作为Value的对象则没有任何要求。

如果作为Key的class没有实现Comparable接口，那么，必须在创建TreeMap时同时指定一个自定义排序算法:

public class Main {
    public static void main(String[] args) {
        Map<Person, Integer> map = new TreeMap<>(new Comparator<Person>() {
            public int compare(Person o1, Person o2) {
                return o1.name.compareTo(o2.name);
            }
        });
        map.put(new Person("Tom"), 1);
        map.put(new Person("Bob"), 2);
        map.put(new Person("Lily"), 3);
        for (Person key : map.keySet()) {
            System.out.println(key);
        }
        // {Person: Bob}, {Person: Lily}, {Person: Tom}
        System.out.println(map.get(new Person("Bob"))); // 2
    }
}

class Person {
    public String name;
    Person(String name) {
        this.name = name;
    }
    public String toString() {
        return "{Person: " + name + "}";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

Comparator接口要求实现一个比较方法，它负责比较传入的两个元素a和b，如果a，则返回负数，通常是-1，如果a==b，则返回0，如果a>b，则返回正数，通常是1。TreeMap内部根据比较结果对Key进行排序。

public class Main {
    public static void main(String[] args) {
        //给一组数字，里面会有一些重复的元素，求取前k个出现频次最多的元素？
        int[] arr = {1, 4, 1, 4, 2, 4, 1, 4, 2, 4, 3, 4, 4, 1, 4, 2, 4, 3, 4, 4, 2, 4, 1, 4, 2, 4, 3, 4, 3, 4, 4, 1, 2, 4, 1, 2, 4, 3, 1, 1, 1, 2, 3, 4};

        //key-Integer-元素
        //value-Integer-次数
        HashMap map = new HashMap<>();
        for (int num : arr) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        System.out.println(map);
        PriorityQueue queue = new PriorityQueue(new Comparator() {
            @Override
            public int compare(Freq o1, Freq o2) {
                return o2.freq - o1.freq;
            }
        });
        for (Integer num : map.keySet()) {
            queue.offer(new Freq(num, map.get(num)));
        }
        System.out.println(queue.poll());
        System.out.println(queue.poll());
    }
}

class Freq {
    int num;    //数字
    int freq;   //次数

    public Freq(int num, int freq) {
        this.num = num;
        this.freq = freq;
    }

    @Override
    public String toString() {
        return "Freq{" +
                "num=" + num +
                ", freq=" + freq +
                '}';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47