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()); // 返回 -3
        minStack.pop();
        System.out.println(minStack.top());    // 返回 0
        System.out.println(minStack.getMin()); // 返回 -2
    }
}

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