Java Map的遍历与排序

前言

因为尝试用Java敲Python题遇到字典排序问题而写

Java Map与Python dict的区别

Java TreeMap Java HashMap Python dict
实现原理 使用红黑树 使用哈希表 哈希表
键类型 必须同类型 必须同类型,需要提供Comparator或key实现Comparable接口 可不同类型，通过地址比较
有序性 无序 默认Key升序排序 3.6以前无序,3.6及以后有序
平均查询时间复杂度 O(logn) O(1) O(1)
null键 不允许 允许 允许

Java Map遍历

Map遍历可以用迭代器遍历或者列表遍历，前者速度更快但只能遍历一次，若需要再次遍历只能重新定义是个iterator对象，若需要重复遍历则后则效率更高

迭代器遍历

用Map.entrySet().iterator()将Map元素以Entry键值对的形式生成迭代器

1
2
3
4
5
6
7
8
9
10
11
public static <K,V> void traversal1(Map<K, V> map) {
    Iterator<Map.Entry<K,V>> iterator = map.entrySet().iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}
public static <K,V> void traversal2(Map<K, V> map) {
    for (Map.Entry<K, V> kvEntry : map.entrySet()) {
        System.out.println(kvEntry);
    }
}

这里for循环会比手动创建迭代器稍慢一点

转为List后遍历

用Map.entrySet().iterator()将Map元素以Entry键值对的形式生成列表

1
2
3
4
5
6
public static <K,V> void traversal3(Map<K, V> map) {
    List<Map.Entry<K, V>> list = new ArrayList<>(map.entrySet());
    for (Map.Entry<K, V> kvEntry : list) {
        System.out.println(kvEntry);
    }
}

Java Map排序

TreeMap通过Key排序

TreeMap默认利用key的Comparable接口比较排序(通常为自然升序排序),若提供Comparator对象则用compare()比较排序

1
2
3
4
5
6
Map<String, Integer> map = new TreeMap<>(new Comparator<String>() {
    @Override
    public int compare(String s, String t1) {
        return t1.compareTo(s);
    }
});

转为List后排序

因为HashMap是无序的TreeMap也只能通过key排序则转为List再排序是更推荐的

先说最方便的，调用Map.Entry.comparingByKey()/Map.Entry.comparingByValue()会返回对比Key/Value的Comparator对象

1
2
3
4
5
public static <K extends Comparable<K>,V extends Comparable<V>> List<Map.Entry<K, V>> toListSort2(Map<K,V> map) {
    List<Map.Entry<K,V>> list = new ArrayList<>(map.entrySet());
    list.sort(Map.Entry.comparingByValue());
    return list;
}

也可以手动创建Comparator对象

1
2
3
4
5
6
7
8
9
10
public static <K extends Comparable<K>,V extends Comparable<V>> List<Map.Entry<K, V>> toListSort1(Map<K,V> map) {
    List<Map.Entry<K,V>> list = new ArrayList<>(map.entrySet());
    list.sort(new Comparator<Map.Entry<K, V>>() {
        @Override
        public int compare(Map.Entry<K, V> kvEntry, Map.Entry<K, V> t1) {
            return kvEntry.getKey().compareTo(t1.getKey());
        }
    });
    return list;
}

当然也可以对key和value同时进行比较

1
2
3
4
5
6
7
8
9
10
11
12
13
public static <K extends Comparable<K>,V extends Comparable<V>> List<Map.Entry<K, V>> toListSor3(Map<K,V> map) {
    List<Map.Entry<K,V>> list = new ArrayList<>(map.entrySet());
    list.sort(new Comparator<Map.Entry<K, V>>() {
        @Override
        public int compare(Map.Entry<K, V> kvEntry, Map.Entry<K, V> t1) {
            if(kvEntry.getKey().compareTo(t1.getKey()) != 0) {
                return kvEntry.getKey().compareTo(t1.getKey());
            }
            return kvEntry.getValue().compareTo(t1.getValue());
        }
    });
    return list;
}