当前位置：首页 > news >正文

前端算法：字典and哈希表（力扣1题、349题解法）

news 2024/10/23 3:23:43

一、字典

1.概念

2.特点

3.在JS中如何实现

4.字典用法

使用对象作为字典

使用map

5.应用场景

二、哈希表

1.概念

2.工作原理

3. 在 JavaScript 中的实现

4.哈希表用法

使用 Map 作为哈希表

5.应用场景

三、字典与哈希表的区别

四、力扣算法实战

1.1题两数之和

2.349题两个数组的交集

五、总结

一、字典

1.概念

字典是一种以键值对形式存储数据的集合。在字典中，每个键都是唯一的，值可以是任意类型。这种结构使得查找、插入和删除操作变得非常高效。

2.特点

唯一性：字典中的每个键都是唯一的，不能重复。
快速查找：通过键可以快速访问到对应的值，平均时间复杂度为 �(1)O(1)。
灵活性：可以存储多种数据类型的值。

3.在JS中如何实现

在 JavaScript 中，可以使用对象（{}）或 ES6 引入的 Map 来实现字典。

4.字典用法

使用对象作为字典

// 创建一个字典
const dictionary = {"apple": "A fruit that is red or green.","banana": "A long yellow fruit.","orange": "A citrus fruit."
};// 查找值
console.log(dictionary["apple"]); // 输出: A fruit that is red or green.// 添加新键值对
dictionary["grape"] = "A small, round fruit.";
console.log(dictionary["grape"]); // 输出: A small, round fruit.// 删除键值对
delete dictionary["banana"];
console.log(dictionary["banana"]); // 输出: undefined

使用map

// 创建一个字典
const map = new Map();
map.set("apple", "A fruit that is red or green.");
map.set("banana", "A long yellow fruit.");// 查找值
console.log(map.get("banana")); // 输出: A long yellow fruit.// 添加新键值对
map.set("grape", "A small, round fruit.");
console.log(map.get("grape")); // 输出: A small, round fruit.// 删除键值对
map.delete("apple");
console.log(map.get("apple")); // 输出: undefined

5.应用场景

数据存储：可以用来存储用户信息、配置选项、字典数据等。
频率统计：统计单词出现频率，例如在文本分析中。
快速查找：用于需要频繁查找的场景，如缓存、路由配置等。

二、哈希表

1.概念

哈希表是一种实现字典的数据结构，利用哈希函数将键映射到数组索引。这种映射允许在常数时间内（理想情况下）查找、插入和删除元素。

2.工作原理

哈希函数：将键转换为数组的索引。好的哈希函数应当尽可能均匀地分布键，以减少冲突。
冲突处理：当两个不同的键被哈希到同一个索引时，称为冲突。常见的解决方法包括：
- 链式存储：在每个索引位置使用一个链表来存储所有映射到该位置的键值对。
- 开放地址法：在数组中查找下一个可用位置来存储冲突的键值对。

3. 在 JavaScript 中的实现

JavaScript 的 Map 和对象（{}）可以视为哈希表的实现。Map 允许使用任何类型的值作为键，且保留插入顺序。

4.哈希表用法

使用 Map 作为哈希表

// 创建一个哈希表
const hashTable = new Map();// 插入数据
hashTable.set("name", "Alice");
hashTable.set("age", 30);
hashTable.set("city", "New York");// 查找数据
console.log(hashTable.get("name")); // 输出: Alice// 删除数据
hashTable.delete("age");
console.log(hashTable.has("age")); // 输出: false

5.应用场景

缓存：快速查找和存储数据，如 API 响应缓存。
数据库索引：加速数据库查询操作。
频率统计：类似于字典，但在高并发情况下的表现通常更好。

三、字典与哈希表的区别

特点	字典	哈希表
数据结构	以键值对形式存储数据	使用哈希函数映射键到索引
时间复杂度	平均 O（1）	理想情况下平均 O（1）
键的类型	键通常是字符串或符号	键可以是任意数据类型
处理冲突	使用链表或其他方法处理冲突	使用链式存储或开放地址法处理冲突
语言支持	多种语言均支持	多数语言中都有哈希表的实现

四、力扣算法实战

1.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]

解题思路：设立一个字典，循环数组，用目标值减去循环的值，然后查找字典里是否含有结果，如果有就返回，没有就放到map里

代码如下：

var twoSum = function(nums, target) {let map = new Map()for(let i=0;i<nums.length;i++){num = target - nums[i]if(map.has(num)){return [map.get(num),i]}map.set(nums[i],i)}
};

2.349题两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的 交集。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

解题思路：只需要返回数组的交集，那么先将第二个数组放进集合中，然后从第一个数组运用集合扁平化之后将重复元素去除，在用过滤器查找是否含有相同数。

代码如下

var intersection = function(nums1, nums2) {let set = new Set(nums2);return [...new Set(nums1)].filter((val)=>set.has(val))
};

五、总结

字典是一种用于存储键值对的数据结构，允许通过唯一键快速访问对应的值，而哈希表则是实现字典的底层数据结构，通过哈希函数将键映射到存储位置，从而支持高效的查找、插入和删除操作。虽然字典通常保持键的插入顺序（在某些语言中），哈希表的实现则侧重于处理键的碰撞和动态调整大小，以保持性能。总的来说，字典依赖哈希表的高效性来实现其功能。

查看全文

http://www.mrgr.cn/news/56472.html