哈希表,Hash Table,也称为散列表。
哈希碰撞
key映射到同一个索引位置,叫做哈希碰撞。
哈希碰撞一般有两种解决方法:拉链法 和 线性探测法。
- 拉链法
发生哈希冲突的元素被存储在链表中。 - 线性探测法
在开放定址算法里,线性探测法是散列解决冲突的一种方法,当hash一个关键字时,发现没有冲突,就保存关键字, 如果出现冲突,则就探测冲突地址下一个地址,依次按照线性查找,直到发现有空地址为止,从而解决冲突。
常见的3种哈希结构
- 数组
- set(集合)
- map(映射)
题目:有效的字母异位词
力扣 242题,有效的字母异位词
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
提示:
1
方法1 :使用Map统计每个字符出现的次数。
import java.util.*;
class Solution {
public boolean isAnagram(String s, String t) {
if(s == null || t == null){
return false;
}
if(s.equals(t)){
return true;
}
Map map1 = putInMap(s);
Map map2 = putInMap(t);
return map1.equals(map2);
}
/**
把每一个字符串拆成 char数组,每个char作为key,放到map中,每出现一次,value值加1,最后比较map是否相同
*/
Map putInMap(String s){
Map map1 = new HashMap();
char[] c1 = s.toCharArray();
for(int i = 0; i
方法2:使用每个字符的ASCII值,作为数组的索引,计算每个字符出现的次数。
class Solution {
public boolean isAnagram(String s, String t) {
if(s == null || t == null){
return false;
}
if(s.equals(t)){
return true;
}
int[] arr1 = countChar(s);
int[] arr2 = countChar(t);
return equalsArray(arr1, arr2);
}
/**计算每一个字符出现的次数, 26位长的数组,每一位置代表每个字母表中的一个字母
*/
int[] countChar(String s){
int[] alphabet = new int[26];
char[] c1 = s.toCharArray();
for(int i = 0; i
方法2:优化版,只使用一个数组,先加值,再减值,如果为0则为相同。
(实际测试性能并未提升…)
class Solution {
public boolean isAnagram(String s, String t) {
if(s == null || t == null){
return false;
}
if(s.equals(t)){
return true;
}
int[] arr = new int[26];
char[] chars1 = s.toCharArray();
for(int i = 0; i
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.e1idc.net