基础算法 - 哈希表

哈希表（Hash Table）作为一种高效的数据结构，在计算机科学中广泛应用于数据存储和快速查找。其基本原理是通过哈希函数将键映射到存储位置，从而实现快速的插入、删除和查找操作。

哈希表的主要特点包括：

键值对存储：每个键值对都通过哈希函数计算得到唯一的存储位置。
快速查找：在平均情况下，哈希表支持常数时间复杂度的查找操作（O(1)）。
碰撞处理：当多个键映射到同一个位置时，哈希表使用碰撞处理方法（如链表或开放寻址法）来存储和查找数据。

哈希表通常用于解决查找、存储和计数等问题，是解决大量数据快速访问的重要工具。

相关题目

1. 两数之和 - 力扣（LeetCode）

难度：简单

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // key为nums中出现的值，value为对应的下标
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i<nums.length;i++){
            int need = target - nums[i];
            if(map.containsKey(need)){
                return new int[]{i,map.get(need)};
            }
            map.put(nums[i],i);
        }
        return new int[]{-1,-1};
    }
}

遍历数组的时候将元素值与元素下标记录至哈希表，便于后续以O(1)的时间复杂度查询need值。

49. 字母异位词分组 - 力扣（LeetCode）

难度：中等

class Solution {
    // 需要把字母异位词归类到一起
    // 找出可以产生相同哈希值的属性
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String,List<String>> map = new HashMap<>();
        for(String str:strs){
            // 如果他们组成的字母都相同，那么排序之后一定也是相同的
            // 所以将这些String中的字符都重新排序，排序之后的String作为key
            char[] tmp = str.toCharArray();
            Arrays.sort(tmp);
            String key = Arrays.toString(tmp);
            if(!map.containsKey(key))
                map.put(key,new ArrayList<>());
            map.get(key).add(str);
        }
        return new ArrayList<>(map.values());
    }
}

将排序后的数组转换为字符串作为哈希表的键。

128. 最长连续序列 - 力扣（LeetCode）

为了避免，每一次寻找当前值cur的下一个连续值cur+1要重新遍历一次数组，所以先将所有元素放在set中，以O(1)的时间复杂度去寻找cur+1，但是对于每一个cur，都需要循环去寻找，寻找以cur为底的最长连续序列，但是这样浪费了很多时间。

注意：如果num的前一个值nums-1存在，那么就不考虑num

public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int max = 0;
        for(int num : nums){
            if(!set.contains(num-1)){ // 从候选最长序列的头部开始算，判断是不是头部
                int cur = num;
                int count = 1;
                while(set.contains(cur+1)){
                    cur++;
                    count++;
                }
                max = Math.max(max, count);
            }
        }
        return max;
    }

为什么遍历set会比遍历int[]更快呢…..

因为nums中可能有很多重复的数据。。。。

class Solution {
    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int res = 0;
        int count;
        for(int num : set){ // ⭐，遍历set会更快....
            if(!set.contains(num-1)){ // 查看当前的num是不是一个连续序列的起点
                int cur = num;
                count = 1;
                while(set.contains(++cur)){ // 以cur为起点，寻找这个连续序列的最长长度
                    count++;
                }
                res = Math.max(res, count);
            }
        }
        return res;
    }
}

巧妙之处在于利用哈希集合（HashSet）来快速检索和判断数字是否存在。

2024-06-07 该篇文章被 jay1an 打上标签: 基础算法哈希归为分类: 基础算法