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

代码随想录（三）—— 哈希表部分刷题

news 2025/1/14 17:58:53

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

数组
set （集合）
map(映射)

在java中有就是，hashmap, LinkedHashMap, TreeMap ，HashTable 等

总结一下，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法！

1. 两个数组的交集

349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集

。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。

class Solution {public int[] intersection(int[] nums1, int[] nums2) {/**因为要判断一个元素是不是在另一个集合中的操作，可以使用哈希表来进行操作可以使用 Set集合，存储一个nums1中的元素然后遍历nums2,如果Set中有这个元素，说明是交集元素，则加入交集*/List<Integer> list = new ArrayList<>();Set<Integer> set = new HashSet<>();for(var num1 : nums1) {set.add(num1);}for(var num2 : nums2) {if(set.contains(num2)) list.add(num2);}return list.toArray(new int[0]);}
}

补充：

java中的map:

在 Java 中，主要有以下几种常用的 Map 实现类：
一、HashMap
特点：
基于哈希表实现，允许使用 null 键和 null 值。
不保证元素的顺序，特别是在对哈希表进行添加、删除等操作后，元素的顺序可能会发生变化。
查找、插入和删除操作的时间复杂度通常为 O (1)，在最坏情况下可能会退化为 O (n)，其中 n 是元素的数量。
适用场景：
当对元素的顺序没有要求，只需要快速的存储和检索键值对时非常适用。
二、LinkedHashMap
特点：
继承自 HashMap，同时维护了一个双向链表，保证了元素的插入顺序或者访问顺序。
可以通过构造函数选择是按照插入顺序还是访问顺序（最近访问的元素会被移动到链表尾部）来遍历元素。
与 HashMap 相比，插入和访问稍微慢一些，因为需要维护链表结构。
适用场景：
需要按照插入顺序或者访问顺序遍历键值对时使用。
三、TreeMap
特点：
基于红黑树实现，保证了元素按照键的自然顺序或者指定的比较器顺序进行排序。
不允许使用 null 键，但可以使用 null 值。
查找、插入和删除操作的时间复杂度为 O (log n)，其中 n 是元素的数量。
适用场景：
当需要按键的有序顺序遍历键值对时使用，比如实现有序的映射表。
四、Hashtable
特点：
是早期 Java 版本中的同步版本的哈希表实现，不允许使用 null 键和 null 值。
所有方法都是线程安全的，但在单线程环境下性能比 HashMap 低。
适用场景：
在多线程环境下，需要保证线程安全且不允许 null 键值时可以使用，但在现代 Java 中，通常更推荐使用 ConcurrentHashMap 或通过同步包装器对 HashMap 进行同步。
五、ConcurrentHashMap
特点：
高并发环境下的哈希表实现，支持多线程并发访问。
不允许使用 null 键，但可以使用 null 值。
采用了分段锁技术，在保证线程安全的同时，尽量减少锁的粒度，提高并发性能。
适用场景：
在多线程环境下，需要高效地进行并发读写操作时使用。