映射

问题描述

映射是一种存储键值对的数据结构。
在C++中为map，Java中为HashMap，Python中为dict。
它们都提供了通过键快速访问值的能力。

基本概念

特点

1. 键值对存储
2. 键的唯一性
3. 快速查找
4. 动态添加删除
5. 支持迭代访问

代码实现

1. C++ Map

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    // 创建映射
    map<string, int> m1;                          // 空映射
    map<string, int> m2 = {                       // 使用初始化列表
        {"apple", 1},
        {"banana", 2},
        {"orange", 3}
    };
    
    // 插入元素
    m1["apple"] = 1;                             // 使用[]运算符
    m1.insert({"banana", 2});                    // 使用insert方法
    m1.insert(make_pair("orange", 3));          // 使用make_pair
    
    // 访问元素
    cout << m1["apple"] << endl;                // 使用[]运算符
    cout << m1.at("banana") << endl;            // 使用at方法（有边界检查）
    
    // 检查键是否存在
    if (m1.count("apple") > 0) {
        cout << "apple exists" << endl;
    }
    
    // 查找元素
    auto it = m1.find("banana");
    if (it != m1.end()) {
        cout << it->first << ": " << it->second << endl;
    }
    
    // 删除元素
    m1.erase("apple");                          // 删除指定键的元素
    
    // 获取大小
    cout << "Size: " << m1.size() << endl;
    
    // 遍历映射
    for (const auto& pair : m2) {
        cout << pair.first << ": " << pair.second << endl;
    }
    
    return 0;
}

2. Java HashMap

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        // 创建映射
        HashMap<String, Integer> m1 = new HashMap<>();           // 空映射
        HashMap<String, Integer> m2 = new HashMap<>() {{        // 使用匿名内部类初始化
            put("apple", 1);
            put("banana", 2);
            put("orange", 3);
        }};
        
        // 添加元素
        m1.put("apple", 1);
        m1.put("banana", 2);
        m1.putIfAbsent("apple", 3);  // 如果键不存在才添加
        
        // 访问元素
        System.out.println(m1.get("apple"));           // 获取值
        System.out.println(m1.getOrDefault("pear", 0)); // 获取值，如果不存在返回默认值
        
        // 检查键是否存在
        if (m1.containsKey("apple")) {
            System.out.println("apple exists");
        }
        
        // 删除元素
        m1.remove("apple");
        
        // 获取大小
        System.out.println("Size: " + m1.size());
        
        // 遍历映射
        for (Map.Entry<String, Integer> entry : m2.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        
        // Java 8 Lambda表达式
        m2.forEach((key, value) -> 
            System.out.println(key + ": " + value)
        );
    }
}

3. Python Dict

# 创建字典
d1 = {}                                  # 空字典
d2 = {'apple': 1, 'banana': 2, 'orange': 3}  # 直接初始化
d3 = dict(apple=1, banana=2, orange=3)   # 使用dict()函数

# 添加和修改元素
d1['apple'] = 1                          # 添加或更新元素
d1.update({'banana': 2, 'orange': 3})    # 批量更新

# 访问元素
print(d1['apple'])                       # 使用[]访问（键不存在会报错）
print(d1.get('pear', 0))                # 使用get方法（键不存在返回默认值）

# 检查键是否存在
if 'apple' in d1:
    print('apple exists')

# 删除元素
del d1['apple']                          # 使用del语句
value = d1.pop('banana')                 # 删除并返回值
last_item = d1.popitem()                 # 删除并返回最后一个键值对

# 字典视图
print(d2.keys())                         # 获取所有键
print(d2.values())                       # 获取所有值
print(d2.items())                        # 获取所有键值对

# 遍历字典
for key in d2:                           # 遍历键
    print(key, d2[key])

for key, value in d2.items():            # 遍历键值对
    print(key, value)

# 字典推导式
squares = {x: x**2 for x in range(5)}    # {0:0, 1:1, 2:4, 3:9, 4:16}
filtered = {k: v for k, v in d2.items() if v > 1}  # 值大于1的项

应用场景

1. 缓存实现
2. 计数统计
3. 数据索引
4. 配置存储
5. 关联数据

注意事项

1. 键的类型要求
2. 内存开销
3. 哈希冲突
4. 迭代顺序
5. 线程安全性

常见示例

1. 字符计数

map<char, int> countChars(string s) {
    map<char, int> counts;
    for (char c : s) {
        counts[c]++;
    }
    return counts;
}

public static Map<Character, Integer> countChars(String s) {
    HashMap<Character, Integer> counts = new HashMap<>();
    for (char c : s.toCharArray()) {
        counts.put(c, counts.getOrDefault(c, 0) + 1);
    }
    return counts;
}

def count_chars(s: str) -> dict:
    return {c: s.count(c) for c in set(s)}
    # 或者使用 Counter
    # from collections import Counter
    # return Counter(s)

2. 两数之和

vector<int> twoSum(vector<int>& nums, int target) {
    map<int, int> seen;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (seen.count(complement)) {
            return {seen[complement], i};
        }
        seen[nums[i]] = i;
    }
    return {};
}

public static int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (seen.containsKey(complement)) {
            return new int[] {seen.get(complement), i};
        }
        seen.put(nums[i], i);
    }
    return new int[0];
}

def two_sum(nums: list, target: int) -> list:
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []