【算法方法总结·七】哈希的一些技巧和注意事项

  • 【算法方法总结·一】二分法的一些技巧和注意事项
  • 【算法方法总结·二】双指针的一些技巧和注意事项
  • 【算法方法总结·三】滑动窗口的一些技巧和注意事项
  • 【算法方法总结·四】字符串操作的一些技巧和注意事项
  • 【算法方法总结·五】链表操作的一些技巧和注意事项
  • 【算法方法总结·六】栈队列堆的一些技巧和注意事项
  • 【算法方法总结·七】哈希的一些技巧和注意事项 🎯

【哈希】

  • 哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里

  • 枚举 的时间复杂度是 O(n)，但如果使用 哈希表 的话， 只需要 O(1) 就可以做到

数据结构 涉及的基础内容简要讲解，主讲 Hash 函数的使用

哈希函数

  • 将任意大小的键（Key）转换为固定大小的整数（哈希值）

哈希碰撞

  • 也叫 哈希冲突，即不同键可能生成相同的哈希值（即映射到同一位置）

两种解决办法

（1）拉链法（链地址法）

  • 冲突的键值对 追加到链表 中

（2）开放寻址法

  • 一般用其中的 线性探测法
  • 依靠哈希表中的 空位 来解决碰撞问题

【哈希结构】

  • 数组、set (集合)、map(映射)

注意事项

  • 使用 数组 来做哈希的题目，是因为题目都 限制了数值的大小，如果哈希值 比较少、特别分散、跨度非常大，使用数组就造成空间的 极大浪费
  • 但是能用 数组 解决，尽量不用 set、map
  • 使用 map 的空间消耗要 比数组大一些，因为 map 要 维护红黑树或者符号表，而且还要做哈希函数的运算。所以 数组更加简单直接有效。
  • map 是一种 key value 的存储结构，可以用 key 保存数值，用 value 再保存数值所在的下标，map 中的存储结构为 {key：数据元素，value：数组元素对应的下标}

【Set】

HashSet

  • 不允许元素重复
1
2
3
4
5
6
7
8
Set<String> set = new HashSet<>();

// 1、添加元素
set.add("jack"); 
// 2、删除0号索引的元素
set.remove(0);
// 3、查询
set.contains("jack");

TreeSet

1
2
3
4
5
6
7
8
9
10
11
12
13
// 当使用无参构造器创建 TreeSet 的时候，结果仍然是无序的
TreeSet<String> Set1 = new TreeSet<>();

// 可以传入一个比较器(匿名内部类)，并指定规则
TreeSet<String> set2 = new TreeSet<>(new Comparator<String>() {
    // 添加的元素按照字符串大小来排序
	@Override
	public int compare(String o1, String o2) {
		return o1.compareTo(o2); // 小->大
	}
});
// Lambda 表达式的写法
TreeSet<String> set2 = new TreeSet<>((o1, o2) -> o1.compareTo(o2)); // 小->大

HashSet 和 TreeSet 如何实现去重

  • HashSet 必须重写 hashCode() 和 equals() 方法
  • TreeSet 需实现 Comparable 接口或提供 Comparator，定义排序和去重规则。
    如果 传入了 Comparator 匿名对象，则使用 compare 方法，方法 返回0，认为是相同元素；
    如果 没有传入，则用 Compareable 接口的 compareTo 去重。

【Map】

HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Map<Integer,Integer> map = new HashMap<>();

// put:添加
map.put(key,value);
// remove:根据键删除映射关系
map.remove(key);
// get：根据键获取值
map.get(key)
// size:获取元素个数
map.size()
// isEmpty:判断个数是否为0
map.isEmpty()
// clear:清除k-v
map.clear();
// containsKey:查找键是否存在
map.containsKey(key)
// map.getOrDefault(sum, 0)如果存在sum返回其value,否则返回0
map.getOrDefault(sum, 0)
// 如果要使得 map[s]++
map.put(s,map.getOrDefault(s,0)+1)
    
Map.Entry<k,v> 中提供 getKey()和getValue()方法

TreeMap

1
2
3
4
5
6
7
8
9
10
11
12
//使用默认的构造器，创建TreeMap, 是无序的(也没有排序)
TreeMap<String,String> treeMap = new TreeMap<>();

TreeMap<String,String> treeMap1 = new TreeMap<>(new Comparator<String,String>() {
	@Override
	public int compare(String o1, String o2) {      
		//按照传入的key的大小, 从大到小排序
		return o2.compareTo(o1);
	}
});
// Lambda 表达式的写法
TreeMap<String,String> treeMap1 = new TreeMap<>((o1, o2) -> o2.compareTo(o1)); // 大->小

Map 接口的遍历方法

keySet()

1
2
3
4
5
6
7
// 先取出所有的Key , 通过Key取出对应的Value
Set<Integer> keyset = map.keySet();  // 取得key是个对象，并不用调用特有方法，所以不需要转型
//(1) 增强for
for (Object key: keyset) {
    key//key
	map.get(key);//value
}

values()

1
2
3
4
5
6
Collection values = map.values();
//这里可以使用所有的Collections使用的遍历方法. 因为map.values()的返回值的类型是Collection 
//(1) 增强for
for (Object value: values) {
	value;//value
}

entrySet() 最常用

1
2
3
4
5
6
7
// 通过 EntrySet来获取k-v
Set<Integer> entrySet = map.entrySet(); //EntrySet< Map.Entry<K,V> >
//(1) 增强for
for (Map.Entry<Integer,Integer> entry: entrySet) { 
	entry.getKey();//key
    entry.getValue();//value
}

相关力扣题

  • 相关解法见【算法题解答·七】哈希

349. 两个数组的交集

1. 两数之和

454.四数相加II

15. 三数之和

18. 四数之和

49.字母异位词分组

128.最长连续序列