Java映射（含源码）

在Java中，“映射”（Map）是一个存储键值对的数据结构，允许你通过键（Key）快速访问值（Value）。映射中的每个键都是唯一的，这意味着每个键都对应一个特定的值。Java提供了几种实现映射接口的类，其中最常用的是HashMap、TreeMap和LinkedHashMap。下面是这些实现的简要介绍和它们之间的区别，以及一个简单的例子来展示如何使用它们。

HashMap

• HashMap是最常用的映射实现之一。
• 它存储键值对，但不保证映射的顺序。
• 允许使用null作为键或值。
• 它是非同步的，如果多线程同时访问它并且至少有一个线程修改了映射结构，它必须保持外部同步。

TreeMap

• TreeMap基于红黑树（Red-Black tree）实现。
• 它按照键的自然顺序或构造时提供的Comparator进行排序。
• 不允许使用null作为键，但允许使用null作为值。
• 同样是非同步的。

LinkedHashMap

• LinkedHashMap是HashMap的一个子类，可以预测迭代的顺序。
• 它通过维护一个双向链表来保持插入顺序或者访问顺序。
• 允许使用null作为键或值。
• 非同步。

示例代码

以下是一个简单的例子，展示如何使用HashMap来存储和访问键值对：

import java.util.HashMap;
import java.util.Map;public class MapExample {public static void main(String[] args) {// 创建HashMap实例Map<String, Integer> map = new HashMap<>();// 向映射中添加键值对map.put("Alice", 30);map.put("Bob", 25);map.put("Charlie", 35);// 通过键访问值System.out.println("Alice's age: " + map.get("Alice"));// 遍历映射中的所有键值对for (Map.Entry<String, Integer> entry : map.entrySet()) {System.out.println(entry.getKey() + ": " + entry.getValue());}}
}

这个例子展示了如何创建一个HashMap实例，向其中添加一些键值对，然后通过键访问值，并遍历映射中的所有键值对。类似地，你可以使用TreeMap或LinkedHashMap根据你的需要选择不同的行为特征，如排序或保持插入顺序。在Java面试中，常常会遇到涉及算法、数据结构和编程逻辑的问题。这里提供三个示例题目，它们分别关注数组操作、字符串处理和数据结构的使用，都是大厂面试中可能遇到的类型。每个示例都包括问题描述、解决方案及其源码。

1. 合并区间

问题描述：
给定一个区间的集合，区间内以数组形式给出[start, end]，合并所有重叠的区间，并返回一个不重叠的区间数组。

示例：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 合并为 [1,6].

解决方案：

import java.util.Arrays;
import java.util.LinkedList;public class MergeIntervals {public int[][] merge(int[][] intervals) {Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));LinkedList<int[]> merged = new LinkedList<>();for (int[] interval : intervals) {// 如果列表为空，或者当前区间与上一个区间不重叠，直接添加if (merged.isEmpty() || merged.getLast()[1] < interval[0]) {merged.add(interval);} else {// 否则，有重叠，合并区间merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]);}}return merged.toArray(new int[merged.size()][]);}public static void main(String[] args) {MergeIntervals solution = new MergeIntervals();int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};int[][] mergedIntervals = solution.merge(intervals);for (int[] interval : mergedIntervals) {System.out.println(Arrays.toString(interval));}}
}

2. 字符串的排列

问题描述：
给定两个字符串s1和s2，写一个函数来判断s2是否包含s1的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例：
输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).

解决方案：

public class CheckInclusion {public boolean checkInclusion(String s1, String s2) {if (s1.length() > s2.length()) return false;int[] s1Map = new int[26];int[] s2Map = new int[26];for (int i = 0; i < s1.length(); i++) {s1Map[s1.charAt(i) - 'a']++;s2Map[s2.charAt(i) - 'a']++;}for (int i = 0; i < s2.length() - s1.length(); i++) {if (matches(s1Map, s2Map)) {return true;}s2Map[s2.charAt(i + s1.length()) - 'a']++;s2Map[s2.charAt(i) - 'a']--;}return matches(s1Map, s2Map);}private boolean matches(int[] s1Map, int[] s2Map) {for (int i = 0; i < 26; i++) {if (s1Map[i] != s2Map[i]) {return false;}}return true;}public static void main(String[] args) {CheckInclusion solution = new CheckInclusion();String s1 = "ab", s2 = "eidbaooo";System.out.println(solution.checkInclusion(s1, s2)); // 输出：true}
}

3. 最小栈

问题描述：
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

解决方案：

import java.util.Stack;public class MinStack {private Stack<Integer> stack;private Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}public void push(int val) {stack.push(val);if (minStack.isEmpty() || val <= minStack.peek()) {minStack.push(val);}}public void pop() {if (stack.pop().equals(minStack.peek())) {minStack.pop();}}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}public static void main(String[] args) {MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);System.out.println(minStack.getMin()); // 返回 -3minStack.pop();System.out.println(minStack.top());    // 返回 0System.out.println(minStack.getMin()); // 返回 -2}
}

这些示例题目和解决方案旨在提供一种面向对象的编程方法，并展示Java在处理数据结构和算法问题方面的能力。通过这些练习，你可以加深对Java编程的理解并提升解决问题的能力。