rust学习笔记12-hashmap与1.-两数之和
目录
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 ↦ { 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 显式处理 | 允许 null 键和值 |
| 内存管理 | 编译时所有权检查 | GC 自动回收，可能泄漏 |
| 性能重点 | 内存安全 + 抗 HashDoS | 高冲突优化 + 并发工具 |
| Rust 的 HashMap 更加注重安全性、性能和内存管理。它提供了严格的所有权和借用规则，确保程序在并发环境下的正确性和安全性。同时，Rust | ||
| 的类型系统在编译时就进行了严格的类型检查，避免了运行时的类型错误。 | ||
| Java 1.8 的 HashMap 更加注重易用性和开发效率。它提供了自动垃圾回收机制，减少了开发者手动管理内存的负担。此外，Java 的 HashMap | ||
| 在并发环境下提供了 ConcurrentHashMap，简化了多线程编程的复杂性。 | ||
| 实战应用 | ||
给定一个整数数组 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, target: i32) -> Vec { //设置一个map长度和数组一致 let mut map: HashMap = 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, target: i32) -> Vec { //设置一个map长度和数组一致 let mut map: HashMap = 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); }
总结rust使用HashMap判断key是否存在用的是引用类型&n，获取数值是k，这点需要注意，如果不愿意使用k，可以在Some(&k)也使用引用类型，这样就可以不用加*了。
总结rust使用HashMap判断key是否存在用的是引用类型&n，获取数值是k，这点需要注意，如果不愿意使用k，可以在Some(&k)也使用引用类型，这样就可以不用加*了。