rust学习笔记12-hashmap与1. 两数之和

rust集合中也有hashmap，昨天已经提到过，学过java同学再熟悉不过了，一道经典面试题问hashmap在java1.8的实现原理，数组+哈希表+红黑树，rust中hashmap在功能上和java一样，但实现上有很大差别，它的基本用法如下

use std::collections::HashMap;

let mut map: HashMap<&str, i32> = HashMap::new();

// 插入键值对
map.insert("Alice", 25);
map.insert("Bob", 30);

// 查找键值
match map.get("Alice") {
    Some(&age) => println!("Alice 的年龄是: {}", age),
    None => println!("未找到 Alice"),
};

// 遍历哈希表
for (key, value) in &map {
    println!("{}: {}", key, value);
}

rust和java1.8中hashmap，相同和不同点我整理了一下：

相同点
基本功能：
        两者都用于存储键值对，并且通过键来快速查找对应的值。
        都基于哈希表实现，平均时间复杂度为 O(1)。
        支持的操作：
        插入（put/insert）、删除（remove）、查找（get）等操作。
        提供遍历方法，可以访问所有的键值对。
哈希冲突处理：
        两者都使用哈希函数将键映射到桶中，并处理哈希冲突（例如链地址法或开放寻址法）。
泛型支持：
        两者都支持泛型类型参数，允许指定键和值的类型。

区别

特性	Rust 的 `HashMap`	Java 1.8 的 `HashMap`
冲突处理	拉链法（链表）	链表 + 红黑树（长度 ≥8 时树化）
哈希算法	默认 SipHash（安全优先）	依赖 `hashCode()`，优化高频类型
线程安全	需显式同步（如 `Mutex`）	非线程安全，需用 `ConcurrentHashMap`
函数式操作	`entry()` API	`computeIfAbsent`、`merge` 等 Lambda 支持
空值支持	通过 `Option<T>` 显式处理	允许 `null` 键和值
内存管理	编译时所有权检查	GC 自动回收，可能泄漏
性能重点	内存安全 + 抗 HashDoS	高冲突优化 + 并发工具

Rust 的 HashMap 更加注重安全性、性能和内存管理。它提供了严格的所有权和借用规则，确保程序在并发环境下的正确性和安全性。同时，Rust 的类型系统在编译时就进行了严格的类型检查，避免了运行时的类型错误。
Java 1.8 的 HashMap 更加注重易用性和开发效率。它提供了自动垃圾回收机制，减少了开发者手动管理内存的负担。此外，Java 的 HashMap 在并发环境下提供了 ConcurrentHashMap，简化了多线程编程的复杂性。

实战应用

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

解答

use std::collections::HashMap;


pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    //设置一个map长度和数组一致
    let mut map: HashMap<i32, i32>  = HashMap::with_capacity(nums.len());

    for i in 0..nums.len() {
        //获取target - nums[i]的值,就是要寻找到值，如9-2=7， 看看map中是否存在
        let n = target - nums[i];
        if let Some(k) = map.get(&n) {
            //存在并且不等于自己本身，就找到了返回
            if *k != i as i32{
                return  vec![*k as i32, i as i32];
            }
        }
        // 不存在把数组元素和下标存放到map中
        map.insert(nums[i], i as i32);

    }
    return  vec![];
        
}

fn main() {
    let res = two_sum(vec![2,7,3,6], 9);
    println!("{:?}", res);
}

match模式匹配版本

use std::collections::HashMap;

pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    //设置一个map长度和数组一致
    let mut map: HashMap<i32, i32>  = HashMap::with_capacity(nums.len());

    for i in 0..nums.len() {
        //获取target - nums[i]的值,就是要寻找到值，如9-2=7， 看看map中是否存在
        let n = target - nums[i];
        // 查找键值
        match map.get(&n) {
            Some(&k) => {
                if k != i as i32{
                    return vec![k , i as i32];
                }
            }
            None => {
                // 不存在把数组元素和下标存放到map中
                map.insert(nums[i], i as i32);
            }
        };

    }
    return  vec![];
        
}



fn main() {
    let res = two_sum(vec![2,7,3,6], 9);
    println!("{:?}", res);
}