Java Map集合介绍
Map是Java集合框架中用于存储键值对（Key-Value） 的接口，它不继承自Collection接口，具有以下核心特性：
- 键唯一性：每个键（Key）只能对应一个值（Value），键重复时会覆盖旧值。
- 键值映射：通过键可以快速查找对应的值，类似于现实中的“字典”。
- 无序性：默认存储顺序不保证与插入顺序一致（除特定实现类）。
常用实现类及特点
-
HashMap（最常用）
- 底层基于哈希表实现，查询、添加、删除操作的平均时间复杂度为O(1)。
- 键和值都允许为null（但键只能有一个null）。
- 无序存储（键的位置由哈希值决定）。
-
TreeMap
- 底层基于红黑树实现，键会按自然排序（或自定义排序）规则有序排列。
- 查询、添加、删除操作的时间复杂度为O(log n)。
- 适合需要对键进行排序或范围查询的场景（如获取最大/最小键）。
-
LinkedHashMap
- 继承自HashMap，底层通过哈希表+双向链表实现，维护键值对的插入顺序（或访问顺序）。
- 性能略低于HashMap，但兼具哈希表的查询效率和顺序性。
-
Hashtable
- 古老的实现类（JDK1.0），线程安全但性能较低，已被HashMap替代（多线程场景推荐ConcurrentHashMap）。
核心方法
Map接口的常用方法（与算法题密切相关）：
put(K key, V value)：添加键值对（键存在则覆盖）。get(Object key)：根据键获取值（不存在则返回null）。containsKey(Object key)：判断键是否存在（返回boolean）。containsValue(Object value)：判断值是否存在（返回boolean）。remove(Object key)：根据键删除键值对。keySet()：返回所有键的集合（Set）。values()：返回所有值的集合（Collection）。entrySet()：返回所有键值对的集合（Set<Map.Entry<K,V>>）。
Map在算法题中的妙用
Map的核心价值在于键值映射和高效的键查询，尤其适合处理“计数”“映射关系”“缓存”等场景。以下是典型应用：
场景1：统计元素出现次数（频率统计）
问题：给定字符串，统计每个字符出现的次数（LeetCode 387变种）。
思路：用HashMap的键存储元素，值存储出现次数，遍历元素时更新计数。
public Map<Character, Integer> countFrequency(String s) {
Map<Character, Integer> freqMap = new HashMap<>();
for (char c : s.toCharArray()) {
// 若键存在则+1，否则初始化为1
freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
}
return freqMap;
}
优势：一次遍历完成统计，时间复杂度O(n)，避免嵌套循环计数。
场景2：两数之和（返回索引）
问题：给定数组和目标值，返回两个元素的索引，使它们的和为目标值（LeetCode 1）。
思路：用HashMap存储“元素值→索引”的映射，遍历数组时，通过target - 当前元素查找互补元素是否存在。
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
// 找到互补元素，返回索引
return new int[]{map.get(complement), i};
}
map.put(nums[i], i); // 存储当前元素及其索引
}
throw new IllegalArgumentException("No solution");
}
优势：时间复杂度O(n)，优于暴力解法的O(n²)。
场景3：字符串同构
问题：判断两个字符串是否同构（如“egg”和“add”同构，字符映射关系唯一，LeetCode 205）。
思路：用两个HashMap分别存储s→t和t→s的映射，确保映射关系唯一。
public boolean isIsomorphic(String s, String t) {
if (s.length() != t.length()) return false;
Map<Character, Character> sToT = new HashMap<>();
Map<Character, Character> tToS = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char sc = s.charAt(i);
char tc = t.charAt(i);
// 若s→t映射已存在且不匹配当前tc，返回false
if (sToT.containsKey(sc) && sToT.get(sc) != tc) {
return false;
}
// 若t→s映射已存在且不匹配当前sc，返回false
if (tToS.containsKey(tc) && tToS.get(tc) != sc) {
return false;
}
sToT.put(sc, tc);
tToS.put(tc, sc);
}
return true;
}
优势：通过双向映射确保字符关系唯一，时间复杂度O(n)。
场景4：LRU缓存（最近最少使用）
问题：设计一个LRU缓存结构，支持get和put操作，且淘汰最近最少使用的元素（LeetCode 146）。
思路：利用LinkedHashMap的“访问顺序”特性（构造时指定accessOrder=true），超过容量时自动移除最久未访问的元素。
class LRUCache {
private final int capacity;
private final Map<Integer, Integer> cache;
public LRUCache(int capacity) {
this.capacity = capacity;
// 初始化LinkedHashMap，指定容量、负载因子和访问顺序
this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
// 当 size 超过容量时，自动移除最久未访问的元素
return size() > capacity;
}
};
}
public int get(int key) {
return cache.getOrDefault(key, -1);
}
public void put(int key, int value) {
cache.put(key, value);
}
}
优势：LinkedHashMap天然支持访问顺序维护，避免手动实现双向链表，代码简洁高效。
场景5：TreeMap实现区间映射
问题：给定多个区间，判断一个新的区间是否与已有区间重叠（简化版）。
思路：用TreeMap存储“区间起始点→区间结束点”，通过floorKey和ceilingKey快速查找相邻区间。
public boolean isOverlapping(TreeMap<Integer, Integer> intervals, int newStart, int newEnd) {
// 找到小于等于newStart的最大起始点
Integer floorKey = intervals.floorKey(newStart);
if (floorKey != null && intervals.get(floorKey) >= newStart) {
return true; // 与前一个区间重叠
}
// 找到大于等于newStart的最小起始点
Integer ceilingKey = intervals.ceilingKey(newStart);
if (ceilingKey != null && ceilingKey <= newEnd) {
return true; // 与后一个区间重叠
}
return false;
}
优势：TreeMap的有序性使其能快速定位相邻区间，时间复杂度O(log n)。
场景6：异位词分组
问题：将字符串数组中所有异位词（字母相同但顺序不同）分组（LeetCode 49）。
思路：用HashMap的键存储“排序后的字符串”（异位词排序后相同），值存储对应的字符串列表。
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
// 将字符串排序作为键（异位词排序后相同）
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
// 若键不存在则初始化列表，再添加当前字符串
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
优势：通过排序后的字符串作为唯一键，高效分组异位词，时间复杂度O(n * k log k)（k为字符串平均长度）。
总结
Map集合在算法题中的核心应用场景：
- 频率统计：用键存元素，值存计数，适合“出现次数”类问题。
- 映射关系：如两数之和的“值→索引”、同构字符串的双向映射。
- 缓存与顺序：LinkedHashMap维护插入/访问顺序，适合LRU等缓存场景。
- 区间与排序：TreeMap的有序性适合区间查询、范围判断等场景。
选择合适的实现类（HashMap优先用于快速查询，TreeMap用于有序场景），能显著提升算法效率，是解决复杂映射问题的关键工具。
Map集合在算法题中的应用非常灵活，除了前面提到的场景，还有许多针对特定问题的巧妙用法。以下是更多典型场景：
场景1：子数组和为K的数量
问题：给定整数数组和目标值K，计算和为K的连续子数组的数量（LeetCode 560）。
思路：用HashMap存储“前缀和→出现次数”的映射，遍历数组时通过当前前缀和 - K判断是否存在符合条件的前缀和，累加次数。
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> prefixSumCount = new HashMap<>();
prefixSumCount.put(0, 1); // 初始化：前缀和为0出现1次
int currentSum = 0;
int result = 0;
for (int num : nums) {
currentSum += num;
// 若存在前缀和为currentSum - k，说明中间子数组和为k
result += prefixSumCount.getOrDefault(currentSum - k, 0);
// 更新当前前缀和的出现次数
prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);
}
return result;
}
场景2：四数相加II
问题：给定4个整数数组，计算有多少个元组(i,j,k,l)使得nums1[i] + nums2[j] + nums3[k] + nums4[l] = 0（LeetCode 454）。
思路：用HashMap存储前两个数组的和及其出现次数，再遍历后两个数组，通过-sum查找互补的和，累加次数。
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> sumCount = new HashMap<>();
// 存储nums1和nums2的所有可能和及其次数
for (int a : nums1) {
for (int b : nums2) {
int sum = a + b;
sumCount.put(sum, sumCount.getOrDefault(sum, 0) + 1);
}
}
int result = 0;
// 查找nums3和nums4的和的互补值
for (int c : nums3) {
for (int d : nums4) {
int target = - (c + d);
result += sumCount.getOrDefault(target, 0);
}
}
return result;
}
场景3：最长和谐子序列
问题：找出数组中最长的和谐子序列（元素最大值与最小值之差为1，LeetCode 594）。
思路：用HashMap统计每个元素的出现次数，再遍历键集合，若key+1存在，则两者次数之和为和谐子序列长度。
public int findLHS(int[] nums) {
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
int maxLen = 0;
for (int key : freqMap.keySet()) {
if (freqMap.containsKey(key + 1)) {
// 和谐子序列长度 = 当前key次数 + key+1次数
maxLen = Math.max(maxLen, freqMap.get(key) + freqMap.get(key + 1));
}
}
return maxLen;
}
场景4：字符串中的第一个唯一字符
问题：找到字符串中第一个只出现一次的字符（LeetCode 387）。
思路：用HashMap统计每个字符的出现次数，再遍历字符串找到第一个次数为1的字符。
public int firstUniqChar(String s) {
Map<Character, Integer> freqMap = new HashMap<>();
for (char c : s.toCharArray()) {
freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
}
for (int i = 0; i < s.length(); i++) {
if (freqMap.get(s.charAt(i)) == 1) {
return i;
}
}
return -1;
}
场景5：TreeMap实现合并区间
问题：合并所有重叠的区间（LeetCode 56）。
思路：用TreeMap按区间起始点排序，遍历区间时合并重叠或相邻的区间。
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) return new int[0][];
// 按区间起始点排序
TreeMap<Integer, Integer> intervalMap = new TreeMap<>();
for (int[] interval : intervals) {
int start = interval[0];
int end = interval[1];
// 若当前区间与已有区间重叠，合并为更大的区间
Integer floorKey = intervalMap.floorKey(end);
while (floorKey != null && intervalMap.get(floorKey) >= start) {
start = Math.min(start, floorKey);
end = Math.max(end, intervalMap.get(floorKey));
intervalMap.remove(floorKey);
floorKey = intervalMap.floorKey(end);
}
intervalMap.put(start, end);
}
// 转换为结果数组
int[][] result = new int[intervalMap.size()][2];
int i = 0;
for (Map.Entry<Integer, Integer> entry : intervalMap.entrySet()) {
result[i][0] = entry.getKey();
result[i][1] = entry.getValue();
i++;
}
return result;
}
场景6：前缀树（字典树）的Map实现
问题：实现一个前缀树，支持插入和前缀查询（LeetCode 208）。
思路：用HashMap存储每个节点的子节点（字符→节点映射），简化树结构的实现。
class TrieNode {
boolean isEnd; // 标记是否为单词结尾
Map<Character, TrieNode> children;
public TrieNode() {
children = new HashMap<>();
isEnd = false;
}
}
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// 插入单词
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
node.children.putIfAbsent(c, new TrieNode());
node = node.children.get(c);
}
node.isEnd = true;
}
// 检查前缀是否存在
public boolean startsWith(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
if (!node.children.containsKey(c)) {
return false;
}
node = node.children.get(c);
}
return true;
}
}
总结
Map集合在算法中的扩展应用体现了其强大的灵活性：
- 前缀和问题：通过映射前缀和与出现次数，快速计算子数组和相关问题。
- 多数组关联：如四数相加，用Map存储中间结果减少嵌套循环。
- 区间处理：TreeMap的有序性简化区间合并、重叠判断等操作。
- 数据结构模拟：如用Map实现前缀树，简化子节点的存储与访问。
在解题时，合理利用Map的键值映射特性，往往能将复杂问题转化为线性或线性对数时间复杂度的解法，是优化算法的重要工具。
牛客网的MAP算法题
在牛客网的算法题中，Map集合同样有广泛应用，尤其在处理计数统计、映射关系、缓存中间结果等场景时非常高效。以下结合牛客网常见题型，介绍Map的具体应用：
场景1：统计字符出现次数（牛客网高频题）
问题：输入一个字符串，统计每个字符出现的次数，并按字符ASCII码升序输出结果。
思路：用HashMap存储字符与出现次数的映射，再通过键集合排序输出。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
Map<Character, Integer> freqMap = new HashMap<>();
// 统计次数
for (char c : s.toCharArray()) {
freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
}
// 按ASCII码排序（将键转为列表排序）
List<Character> chars = new ArrayList<>(freqMap.keySet());
Collections.sort(chars);
// 输出结果
for (char c : chars) {
System.out.println(c + ":" + freqMap.get(c));
}
}
}
说明：牛客网常考此类基础统计题，Map的getOrDefault方法能简洁处理计数逻辑，配合排序满足输出要求。
场景2：两数之和（牛客网类似LeetCode 1的题型）
问题：给定一个整数数组和目标值，找出数组中两个数的索引，使它们的和为目标值（假设只有一个解）。
思路：用HashMap存储“元素值→索引”，遍历数组时查找互补元素。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
int target = sc.nextInt();
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
System.out.println(map.get(complement) + " " + i);
return;
}
map.put(nums[i], i);
}
}
}
说明：牛客网常以数组题形式出现，Map可将暴力解法的O(n²)优化为O(n)，适合处理大规模输入。
场景3：数组中出现次数超过一半的数字（牛客网剑指Offer原题）
问题：找出数组中出现次数超过一半的数字（假设一定存在）。
思路：用HashMap统计每个数字的出现次数，遍历Map找到次数超过n/2的数字。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
// 提前判断，找到结果即返回
if (freqMap.get(num) > n / 2) {
System.out.println(num);
return;
}
}
}
}
说明：这是牛客网经典的频率统计题，Map的实时计数特性可实现“找到即返回”，优化效率。
场景4：复杂链表的复制（牛客网剑指Offer原题）
问题：复制一个复杂链表，每个节点除了next指针，还有一个random指针指向链表中的任意节点或null。
思路：用HashMap存储“原节点→新节点”的映射，分两步复制：先复制节点值和next，再通过映射设置random。
import java.util.*;
class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
if (pHead == null) return null;
Map<RandomListNode, RandomListNode> nodeMap = new HashMap<>();
RandomListNode cur = pHead;
// 第一步：复制所有节点（仅值），建立映射
while (cur != null) {
nodeMap.put(cur, new RandomListNode(cur.label));
cur = cur.next;
}
// 第二步：设置next和random指针
cur = pHead;
while (cur != null) {
nodeMap.get(cur).next = nodeMap.get(cur.next); // 新节点的next指向原节点next的新节点
nodeMap.get(cur).random = nodeMap.get(cur.random); // 同理设置random
cur = cur.next;
}
return nodeMap.get(pHead);
}
}
说明：这道题体现了Map的“映射”核心价值，通过原节点与新节点的对应关系，避免了复杂的指针操作。
场景5：找出数组中只出现一次的数字（牛客网常见题）
问题：一个整型数组中，除了两个数字外，其他数字都出现了两次。请找出这两个只出现一次的数字。
思路：用HashMap统计每个数字的出现次数，最后筛选出次数为1的数字。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
List<Integer> result = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
if (entry.getValue() == 1) {
result.add(entry.getKey());
}
}
// 按要求排序输出（牛客网可能要求升序）
Collections.sort(result);
System.out.println(result.get(0) + " " + result.get(1));
}
}
说明：这道题用Map的计数功能可轻松解决，无需复杂的位运算（位运算虽更优，但Map实现更直观，适合快速解题）。
总结
在牛客网的算法题中，Map的应用主要集中在：
- 基础计数：如字符/数字出现次数统计，配合排序满足输出格式。
- 映射关系：如两数之和的索引映射、复杂链表的节点映射。
- 筛选特殊元素：如找出只出现一次或超过半数的元素。
Map的优势在于将“查找”操作的时间复杂度从O(n)降至O(1)，尤其适合牛客网中对输入规模较大的题目（如n>10⁴），能有效避免超时。解题时需根据是否需要排序选择HashMap（无序，效率高）或TreeMap（有序，适合需要按键排序的场景）。
扫一扫
168万+
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
