Basic
- 根据关键码的值而进行访问的数据结构
-
一般解决问题：快速判断一个元素是否出现在合集里
-
哈希函数
- key -> 哈希函数 -> 内存地址 -> key/value 对应的内存地址
- 哈希碰撞
- 两个不同的 key 通过同一个哈希函数得到相同的内存地址
- 方法 1: 拉链法 -> 发生冲突的元素都被存储在链表中
- 拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间
- 方法 2: 线性探测法 -> 要保证 tableSize 大于 dataSize，需要依靠哈希表中的空位来解决碰撞问题
- 四个特性
访问 access：哈希表中没有
搜索 search：O(1)
- 通过 key 找 value
- 碰撞 O(k) -> k 就是碰撞元素的个数
插入 insert：O(1)
删除 remove：O(1)
- 三种哈希结构
数组 Array
- 数组 -> 就是一组哈希表
- hashtable 通过 数组 array 的常用操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
//通过数组array - 创建哈希表
String[] hashTable = new String[4];
//添加元素
//time complexity: O(1)
hashTable[1] = "hanmeimei";
hashTable[2] = "lihua";
hashTable[3] = "siyangyuan";
//更新元素 update element
//time complexity: O(1)
hashTable[1] = "bishi";
//删除元素 remove element
//time complexity：O(1)
hashTable[1] = "";
//获取value get value
//time complexity:O(1)
String temp = hashTable[3];
|
HashMap
- 为什么有 hashmap ？
- HashMap 利用 hash 算法实现了快速存取的特性
- hash table 和 HashMap 有什么关系？
- hash table 是一种逻辑数据结构，HashMap 是 Java 中的一种数据类型（结构类型），它通过代码实现了 Hash table 这种数据结构，并在此结构上定义了一系列操作
- hashtable 通过 HashMap 的常用操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
//创建哈希表
//通过编程语言自带的函数
HashMap<Integer, String> map = new HashMap<>();
//第一个是key的类型 第二个是value的类型
//添加元素 add elelments
//time complexity: O(1)
//map.put(key, value)
map.put(1, "hanmeimei");
map.put(2, "lihua");
map.put(3, "siyangyuan")
//更新元素 update element
//time complexity: O(1)
//map.put(key, value)
map.put(1,"bishi");
//删除元素 remove element
//time complexity：O(1)
//map.remove(key)
map.remove(1);
//获取value get value
//time complexity:O(1)
//返回与指定键关联的值
map.get(3);
//检查key是否存在 check key
//time complexity: O(1)
//hashTable check the length
//map.containsKey(key)
//返回值：如果Map集合中包含指定的键名，则返回true；否则返回false
map.containsKey(3);
//检查哈希表长度以及是否还有元素
//length
//time complexity: O(1)
//hashTable Size variables
map.size();
//Is Empty?
//time complexity:O(1);
//hashTable size variables
map.isEmpty();
|
HashSet
- set 集合的两个特点
- 无序
- 里面的元素不是按照某个顺序而排序的
- set 相当于 hash 表的 value，所以也算包含在 hash 表这个结构中
- 不重复
- set 的主要作用
- 检查某个元素是否存在
- 检查是否有重复元素
- 对比 Num 原来数据集 ?= Num 插入集合
- 如果 不等于 就说明存在重复元素
- hashset 如何运作
例如：现在要把一个元素加入一个 hashset 中
- 拿到元素
- 通过哈希函数得到这个元素的哈希值
- hashset 底部就是一个 hash 表，将哈希值放在哈希表上对应的位置
- 如果对应位置没有元素 -> 存入对应位置
- 如果应对位置有元素 -> 对比当前元素和哈希表上的元素是否相等
- 如果是相等的 -> 重复，hashset 不允许重复，所以要么保留原来元素 or 进行更新
- 如果是不相等的 -> 哈希冲突/碰撞，用之前提到的链表等方法
- 四个特性
访问 access：在 set 里通过 index 进行访问是一个不太存在的方法 ❌
搜索 search： - 无 hash collision - O(1) ✅ - 有 hash collision - O(k) -> k 是冲突元素的个数
插入 insert： - 无 hash collision - O(1) ✅ - 有 hash collision - O(k)
删除 delete： - 无 hash collision - O(1) ✅ - 有 hash collision - O(k)
- set 常用操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
//create HashSet
HashSet<Integer> set = new HashSet<>();
//集合元素类型 变量名称 创建对象
//add element
//time complexity:O(1)
set.add(10);
set.add(3);
set.add(5);
set.add(2);
set.add(2);
//[10,3,5,2]
System.out.println(set.toString());
//search element
//O(1)
set.contains(2);
//delete element
//O(1)
set.remove(2);
//[10,3,5]
System.out.println(set.toString());
//size
//O(1)
set.size();
|
HashMap 和 HashSet 的异同
242. Valid Anagram
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution {
public boolean isAnagram(String s, String t) {
int[] record = new int[26];
for (int i = 0; i < s.length(); i++) {
//charAt() 方法用于返回指定索引处的字符char值
//索引范围为从 0 到 length() - 1
//相互加减会得到ASCII码之间的运算
record[s.charAt(i) - 'a']++; //不需要记住字符a的ASCII码，只需要一个相对字符即可
}
for (int i = 0; i < t.length(); i++) {
record[t.charAt(i) - 'a']--;
}
for (int count: record) {
if (count != 0) {
return false;
}
}
return true;
}
}
|
349. Intersection of Two Arrays
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums1.length == 0 || nums2 ==null || nums2.length == 0) {
return new int[0];
}
Set<Integer> set1 = new HashSet<>();
Set<Integer> resSet = new HashSet<>();
//遍历数组nums1 将数传入set1
for(int i : nums1) {
set1.add(i);
}
//遍历数组nums2 如果发现nums2有与nums1重合的数 介入resSet
for(int i : nums2) {
if(set1.contains(i)) {
resSet.add(i);
}
}
//另外申请一个数组存放setRes中的元素，最后返回数组
int[] arr = new int[resSet.size()];
int j = 0;
for (int i : resSet) {
arr[j++] = i;
}
return arr;
}
}
|
202. Happy Number
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public boolean isHappy(int n) {
Set<Integer> record = new HashSet<>();
//为了确保sum的重复出现，只要开始重复了就不进入循环
while( n != 1 && !record.contains(n) ) {
record.add(n);
n = getNextNumber(n);
}
return n == 1;
}
private int getNextNumber(int n) {
int res = 0;
while(n > 0) {
int temp = n % 10;
res += temp * temp;
n = n / 10;
}
return res;
}
}
|
1. Two Sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
if (nums == null || nums.length == 0) {
return res;
}
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int temp = target - nums[i];
if(map.containsKey(temp)) {
res[1] = i;
res[0] = map.get(temp);
break;
}
map.put(nums[i], i);
}
return res;
}
}
|
383. Ransom Note
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
//定义一个哈希映射数组
int[] record = new int[26];
//遍历
for(char c : magazine.toCharArray()) {
record[c - 'a'] += 1;
}
for(char c : ransomNote.toCharArray()) {
record[c - 'a'] -= 1;
}
//如果数组中存在负数，说明ransomNote字符串中存在magazine中没有的字符
for(int i : record) {
if (i < 0) {
return false;
}
}
return true;
}
}
|
例如：现在要把一个元素加入一个 hashset 中