image

编辑人: 浅唱

2024-08-11

0

737

算法核心-哈希算法

分析&回答

哈希算法又称散列函数算法,是一种查找算法。把一些复杂的数据,通过某种函数映射关系,映射成一种易于查找的方式。

哈希算法进行查找的基本原理是根据数量 预先设置一个长度为M的数组,使用一个哈希函数F,并以数据的关键字作为自变量,得到唯一的返回值,返回值的范围为[0, M-1],这样就可以利用哈希函数F将数据元素映射到数组的某一位下标并把数据存放在对应的位置上。

哈希是一种高效的存储算法,也是一种高效的查找算法。 哈希像一本字典,当进行查词的时候,通过目录找到页码,再到对应页码就能找到所需要的内容。

一般情况下,哈希算法的查询效率可以达到常数级别,哈希表成为直接寻址的有效替代方案。而有时候关键字的取值范围太大,数据在通过函数进行映射的时候,找不到一个哈希函数,使得关键字不能映射唯一的值,出现冲突现象。解决哈希冲突的方法:

  1. 链地址法
  2. 二次再散列法
  3. 线性探测再散列
  4. 建立一个公共溢出区

哈希算法解决问题 (两数之和)

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}

哈希算法解决问题 (替换单词)

在英语中,有一个叫做 词根(root) 的概念,它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如,词根an,跟随着单词 other(其他),可以形成新的单词 another(另一个)。

现在,给定一个由许多词根组成的词典和一个句子,需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根,则用最短的词根替换它。

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        Map<Character,List<Integer>> map = new HashMap<>();
        // 所有单词先排序,保证哈希表中的顺序也是从短到长
        Collections.sort(dictionary,(o1,o2)->o1.length()-o2.length());
        // 构建哈希表
        for(int i=0; i<dictionary.size(); ++i) {
            String s = dictionary.get(i);
            char c = s.charAt(0);
            List<Integer> list = map.getOrDefault(c,new ArrayList<>());
            list.add(i);
            map.put(c,list);
        }
        
        // 单词替换
        int start = 0, n=sentence.length();  // 记录单词的在字符串的起始位置
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<n; ++i) {
            char c = sentence.charAt(i);
            if(c==' ') {
                checkAndSplice(sentence.substring(start,i), dictionary, map, sb, true);
                start = i+1;
            }
        }
        // 善后
        checkAndSplice(sentence.substring(start,n),dictionary,map,sb,false);
        return sb.toString();
    }

    private void checkAndSplice(String s, List<String> dict, Map<Character,List<Integer>> map, StringBuilder sb, boolean withBlank) {
        char head = s.charAt(0);
        List<Integer> list = map.get(head);
        int n = s.length();
        // 字典中可能存在符合要求的字典单词
        if(list!=null)
            for(Integer a:list) {
                String word = dict.get(a);
                boolean isMatch = true;
                for(int i=0; i<word.length(); ++i) {
                    if(i>=n) {
                        isMatch = false;
                        break;
                    }
                    char c = s.charAt(i);
                    char cc = word.charAt(i);
                    if(c!=cc) {
                        isMatch = false;
                        break;
                    }
                }
                if(isMatch) {
                    sb.append(word+(withBlank?" ":""));
                    return;
                }
            }
        // 不存在
        sb.append(s+(withBlank?" ":""));
    }
}

-   时间复杂度:O(nm)O(nm),m为哈希表中索引的平均长度,n为句子长度。
-   空间复杂度:O(k)O(k),k为字典单词数。

题目代码出自LeetCode,请自行查阅。

反思&扩展


喵呜面试助手: 一站式解决面试问题,你可以搜索微信小程序 [喵呜面试助手] 或关注 [喵呜刷题] -> 面试助手 免费刷题。如有好的面试知识或技巧期待您的共享!

创作类型:
原创

本文链接:算法核心-哈希算法

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。
分享文章