分析&回答
哈希算法又称散列函数算法,是一种查找算法。把一些复杂的数据,通过某种函数映射关系,映射成一种易于查找的方式。
哈希算法进行查找的基本原理是根据数量 预先设置一个长度为M的数组,使用一个哈希函数F,并以数据的关键字作为自变量,得到唯一的返回值,返回值的范围为[0, M-1],这样就可以利用哈希函数F将数据元素映射到数组的某一位下标并把数据存放在对应的位置上。
哈希是一种高效的存储算法,也是一种高效的查找算法。 哈希像一本字典,当进行查词的时候,通过目录找到页码,再到对应页码就能找到所需要的内容。
一般情况下,哈希算法的查询效率可以达到常数级别,哈希表成为直接寻址的有效替代方案。而有时候关键字的取值范围太大,数据在通过函数进行映射的时候,找不到一个哈希函数,使得关键字不能映射唯一的值,出现冲突现象。解决哈希冲突的方法:
- 链地址法
- 二次再散列法
- 线性探测再散列
- 建立一个公共溢出区
哈希算法解决问题 (两数之和)
给定一个整数数组 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,请自行查阅。
反思&扩展
喵呜面试助手: 一站式解决面试问题,你可以搜索微信小程序 [喵呜面试助手] 或关注 [喵呜刷题] -> 面试助手 免费刷题。如有好的面试知识或技巧期待您的共享!