Hash表经典操作与实践

前言

Hash表在我们开发工作中的使用频率不言而喻，在算法领域Hash表也是一个比较常用的数据结构，由于Hash查找时间,通过Hash算法可以快速定位数据是否存在。

Hash定义与问题

Hash表是可以通过hash算法确定某个key在集合中元素位置的数据结构。

上方，通过hash算法,我们可以计算key在存储哪个位置。hash表可以使用数组来实现，hash算法可以使用取模算法。

hash经典的操作

• 判断数据是否已经存在。

Map map = new HashMap();

if(map.contains(key) {
   //key出现过了
}

• 重复数据计数

• 字母字符类型，可以使用整型数组作为hash表

由于字符和字符之间可以进行加减乘除运算，并且他们计算结果是整型，我们可以利用这一点，通过整型数组来构建字符的hash表。

Hash法实操

leetcode242. 有效的字母异位词

class Solution {
    public boolean isAnagram(String s, String t) {

        if(s.length() != t.length()) {
            return false;
        }


       Map<Character, Integer> map = new HashMap<>();
      
       for(int i=0; i< s.length(); i++) {
           //元素是否出现过
            if(!map.containsKey(s.charAt(i))) {
                 map.put(s.charAt(i), 1);
            } else {
                 //重复元素计数
                map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
            }
       }

       for(int i=0; i< t.length(); i++) {
           if(!map.containsKey(t.charAt(i))) {
               return false;
           } else {
               map.put(t.charAt(i), map.get(t.charAt(i)) - 1);
           }
       }

       for(Map.Entry<Character, Integer> entry : map.entrySet()) {
           Integer value = entry.getValue();
           if(value != 0) {
            return false;
           }
       }

       return true;
    }
}

这道题目解题的关键依据是通过hash可以实现判断数据是否出现过，重复数据计数

leetcode454. 四数相加 II

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {

        Map<Integer,Integer> abmap = new HashMap<>();

        //先统计前两个数组元素和出现的次数
        for(int i=0; i<nums1.length; i++) {
            for(int j=0; j<nums2.length; j++) {
                //计算nums1,nums2和的次数
                int sum = nums1[i] + nums2[j];
                abmap.put(sum, abmap.getOrDefault(sum, 0) + 1);
            }
        }

        int result = 0;
        for(int i=0; i<nums3.length; i++) {
            for(int j=0; j<nums4.length; j++) {
                //计算前两个数组和nums3,nums4 和为0的次数
                int sum = nums3[i] + nums4[j];
                result  = result + abmap.getOrDefault(0-sum, 0);
            }
        }
        return result;

    }
}

这道题就是根据hash重复数据次数操作解决的。

2024加油，深入理解算法，学习算法，一起学习。