[数据结构与算法]Java 中 Map 集合的基本使用

一、HashMap

1.1 HashMap 基本使用

import java.util.*;

/**
 * @author: yunhu
 * @date: 2022/7/14
 */
public class Test {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("Alice", 12);
        map.put("Bob", 20);
        map.put("Yunhu", 18);
        for (String key: map.keySet()) {
            Integer value = map.get(key);
            System.out.println("key = " + key + ", value = " + value);
        }
    }
}

output：

key = Yunhu, value = 18
key = Bob, value = 20
key = Alice, value = 12

1.2 特性

• 非线程安全的
• 遍历 map不保证有序。
• 最多允许一个键为 null，值为 null 可以有多个。
• HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。
• HashMap 中扩容因子的大小是 0.75，当元素到达长度的 75%时，就会进行扩容。

1.3 使用 entrySet() 遍历

import java.util.*;

/**
 * @author: yunhu
 * @date: 2022/7/14
 */
public class Test {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("Alice", 12);
        map.put("Bob", 20);
        map.put("Yunhu", 18);
        for (Map.Entry<String, Integer> entry: map.entrySet()) {
            System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue());
        }
    }
}

output:

key = Yunhu, value = 18
key = Bob, value = 20
key = Alice, value = 12

1.4 HashMap 底层原理

1.4.1 获取键的 hashCode

同一个对象没有发生改变，那么他们的 hashCode 是相同的。

1.4.2 获取 hash 值和数组长度

• 计算 hashCode 的二次 hash 值。
• 计算出数组长度 len

1.4.3 获取存储地址

$index=hash\%len$

index 有两种情况：

• index 为空，直接存入 value 值。
• index 不为空，通过 equals判断与已经存在 index 位置的对象是否是同一个对象
  • 如果是，说明值发生更新，覆盖 value
  • 如果不是，发生 hash 冲突，在链表中加入这个对象。

链表的插入情况：在 JDK1.7 以及前是在头结点插入的，在 JDK1.8 之后是在尾节点插入的。

当链表中的元素个数达到 8且数组长度超过 64，链表转为红黑树，查找更快，这个过程叫做「树化」。

当链表中的元素个数小于 6, 红黑树重新转化为链表，这个过程就叫做「链化」。

二、EnumMap

如果 key是一个 enum 枚举类型，那么就可以使用 EnumMap集合，内部使用的是一个数组来存储 value，可以通过枚举的类型来直接定位数组的索引，不需要计算 hashCode()。效率高，并且空间不浪费。

import java.time.DayOfWeek;
import java.util.EnumMap;
import java.util.Map;

/**
 * @author: yunhu
 * @date: 2022/7/14
 */

public class EnumMapTest {
    public static void main(String[] args) {
        Map<DayOfWeek, String> map = new EnumMap<>(DayOfWeek.class);
        map.put(DayOfWeek.MONDAY, "weekday one");
        map.put(DayOfWeek.TUESDAY, "weekday two");
        map.put(DayOfWeek.WEDNESDAY, "weekday three");
        map.put(DayOfWeek.THURSDAY, "weekday four");
        map.put(DayOfWeek.FRIDAY, "weekday five");
        map.put(DayOfWeek.SATURDAY, "weekday six");
        map.put(DayOfWeek.SUNDAY, "weekday seven");
        System.out.println(map);
        System.out.println(map.get(DayOfWeek.FRIDAY));
    }
}

output:

{MONDAY=weekday one, TUESDAY=weekday two, WEDNESDAY=weekday three, THURSDAY=weekday four, FRIDAY=weekday five, SATURDAY=weekday six, SUNDAY=weekday seven}
weekday five

三、TreeMap

3.1 基本使用

TreeMap是有序的，如果键是字符串，那么就按字母顺序输出。

import java.util.*;

/**
 * @author: yunhu
 * @date: 2022/7/15
 */
public class Test {
    public static void main(String[] args) {
        Map<String, Integer> map = new TreeMap<>();
        map.put("yunhu", 1);
        map.put("alice", 2);
        map.put("bob", 3);
        for (String key : map.keySet()) {
            System.out.println(key);
        }
    }
}

output:

alice
bob
yunhu

3.2 自定义排序算法

3.2.1 匿名函数方式

使用 TreeMap必须实现 Comparable接口，String、Integer已经默认实现了，因此可以直接作为键来使用。

如果作为键的类型没有实现 Comparable接口，那么必须指定一个自定义的排序算法。

import java.util.*;

/**
 * @author: yunhu
 * @date: 2022/7/15
 */
public class Test {
    public static void main(String[] args) {
        Map<Person, Integer> map = new TreeMap<>(new Comparator<Person>() {
            public int compare(Person p1, Person p2) {

                // 按年龄从小到大排序
                return p1.age.compareTo(p2.age);
                
                // 按姓名排序
                // return p1.name.compareTo(p2.name);
            }
        });
        map.put(new Person("bob", 10), 1);
        map.put(new Person("alice", 12), 2);
        map.put(new Person("yunhu", 11), 3);
        for (Person key : map.keySet()) {
            System.out.println(key);
        }
    }
}
class Person {
    public String name;
    public Integer age;
    Person(String name, Integer age) {
        this.name = name;
        this.age = age;
    }
    public String toString() {
        return "{Person: " + name + " " + age + "}";
    }
}

{Person: bob 10}
{Person: yunhu 11}
{Person: alice 12}

3.2.2 实现 Comparable 接口方式

import java.util.*;

/**
 * TreeMap 自定义排序方式
 *
 * @author: yunhu
 * @date: 2022/7/15
 */
public class Test {
    public static void main(String[] args) {
        Map<Person, Integer> map = new TreeMap<>();
        map.put(new Person("bob", 10), 1);
        map.put(new Person("alice", 12), 2);
        map.put(new Person("yunhu", 11), 3);
        for (Person key : map.keySet()) {
            System.out.println(key);
        }
    }
}

class Person implements Comparable<Person>{
    public String name;
    public Integer age;
    Person(String name, Integer age) {
        this.name = name;
        this.age = age;
    }
    public String toString() {
        return "{Person: " + name + " " + age + "}";
    }

    @Override
    public int compareTo(Person o) {
        return this.name.compareTo(o.name);
    }
}

output：

{Person: alice 12}
{Person: bob 10}
{Person: yunhu 11}

按姓名排序了。