3-hashtable

发表于2023-03-25更新于2023-09-11字数统计5.5k阅读时长38分

1. 哈希表基本概念的入门

哈希表也叫散列表，是通过key & value来进行定位的数据结构，他把关键码值映射到表中一个位置来进行定位，这个映射函数叫做哈希函数；
元素在数组位置position可以表示为hash(key)， 表面上只存放key，找到key就可以找到value。
主要思想是空间换时间，可以节约遍历的时间成本，但是代价是需要建立字典库存储映射结果。

  • 数组+链表结构
    数组查询方便，可以通过下标直接获得所对应的值，但是插入删除不方便，需要整体移动元素还需要扩容；
    链表查询不方便，没有下标只能通过遍历的方式进行查询，增加插入方便，只需要找到需要插入的节点之后进行插入删除即可；
    哈希表是两者的结合，获得了两者的优点。
    哈希碰撞指经过哈希函数两个key都映射到了同一个数组位置上，那么这时候有两种解决方法。
  • 拉链法：在同一个位置进行链表结构的扩充；
  • 线性探索法： 往数组的下一个位置进行扩充；
    需要考虑到的是查询效率，当链表长度过长，那么使用线性探索法；当链表长度足够，使用拉链法。
    哈希攻击指的是黑客运用一些会转换为相同存储位置的数据注入，最后使得哈希表退化成一个单链表，降低了查询效率，DOS(Denial of Service, 拒绝服务供给)攻击.

1.1 hashMap

1.1.1 map基本操作

  • hashMap的主要Api：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    map.clear();
    map.size();
    map.isEmpty
    map.containsKey(); //判断
    map.containsValue();
    map.get(key);
    map.put(key,value);
    map.putAll(otherMap);
    map.remove(key);
    map.getOrDefault(key,defaultValue);查找key的值,不存在则返回默认值。
    map.entrySet();用来遍历每一对KV
    for(Map.Entry<Integer，Integer> etntey : map.entrySet())
  • map遍历三种方式
    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
    // 第一种方式： keySet 取出map中所有键，封装为map集合
    		Set<String> s1=buy.keySet();
    		//开始根据键找值
    		for (String key : s1) {
    			Integer value=buy.get(key);
    			System.out.println(key+"->>>>"+value);	
    		}

    // 第二种方式： 将所有键值对取出封装为entrySet集合
    		Set<Map.Entry<String,Integer>> en=buy.entrySet();
    		for (Map.Entry<String, Integer> entry : en) {
    			String key=entry.getKey();
    			Integer value=entry.getValue();
    			System.out.println(key+"->>>"+value);
    			
    		}

    // 第三种方式： Lambda表达式遍历
    		buy.forEach(new BiConsumer<String, Integer>() {
    			@Override
    			public void accept(String t, Integer u) {
    				System.out.println(t+"->>>"+u);
    				
    			}
    		});

1.1.2 HashMap两个重要参数

  • 初始容量大小：确定了哈希表底层数组的长度，必须是2的幂，默认初始值为16；
  • 加载因子： 决定什么时候进行扩容，默认为0.75f，当数组存储元素个数超过初始容量大小*加载因子，数组就会用refresh()方法进行扩容，将数组扩大到原来的两倍。
    扩容十分耗费性能，因为会生成一个新的数组，而且原来元素都要重新计算hashcode存入新的数组。

1.1.3 put方法原理

将key通过本地方法public native int hashcode()， 获取对应key的哈希码， 这个哈希码和key的存储位置有关，一般计算规则是取模存入，假如数组的长度是16个字节，key的hashcode是3214968，那么3214968 mod 16 = 8, 那么key就会被存储在数组的第8个位置，如果该位置为空则直接存入，如果该位置有值，就将插入的key与已经存在的key逐一进行equals判断，如果true就替换values，否则就以链表或红黑树(当链表长度大于8时)形式接入。此时(key, value)被封装为Node节点一同进行put操作

红黑树是平衡二叉树，在查找的效率方面比链表高。

  • equals()和hashcode()关系
    equals()方法对于基本数据类型，比较两个数的内容是否相等，而对于引用数据类型，则比较两个数的存储位置是否相等。
    两个对象equals()了，那么他们的hashcode()一定相等；两个对象不equals()，他们的hashcode不一定不相等(经过算法可能计算出来相同的值，哈希碰撞的原理)
    equals()重写了，hashcode()就一定要重写，否则可能两个对象equals，他们的hashcode仍然不相等，可能为后世使用埋下隐患;

1.1.4 get(key)方法原理

首先调用hashcode()方法获取key的hashcode；
之后取模定位到数组的索引位置，如果位置为空，返回null；
如果有值，逐一遍历将key进行equal判断，成功则放回对应Node中的values；匹配不到返回null。

1.1.5 hashMap 在Java1.7和1.8中的区别

1. 结构不同

1.7采用的是数组+链表的数据结构
1.8采用的是数组+链表+红黑树的数据结构(当链表长度大于8时，扩展为红黑树)

2. 节点不同

区别：
1.8中的hash作为一个常量，可以减少扩容时候再次计算哈希值造成的性能消耗。
1.8多了红黑树的节点。

3. hash函数区别

1.8相较于1.7只采用了一次位运算和一次与运算，而这次的目的是为了能够减少哈希碰撞，将高位和地位融合在一起，因为发现进行取模操作的时候对高位的影响是相对较小的。因为计算公式为(n-1) & hash，对高位基本上是没有什么影响的。

取模，hash%length，计算机中直接求余效率不如位移运算，源码中做了优化hash&(length-1)，hash % length == hash & (length - 1)的前提是length是2的n次方, 位运算特征，length是2的n次方，那么他减去1之后就是n个1，异或运算同0异1，这时候就能准确得出他在长度内的值是多少了。

4. 初始化方式

1.7：

  • table是直接赋值给了一个空数组，在第一次put元素时初始化和计算容量。
  • table是单独定义的inflateTable（）初始化方法创建的。
    1.8：
  • table没有赋值，属于懒加载，构造方式时已经计算好了新的容量位置（大于等于给定容量的最小2的次幂）。
  • table是resize（）方法创建的。

5. 扩容方式

1.7： 运用异或对哈希值进行重新计算，运用resize()方法负责扩容，inflateTable()负责创建表；
1.8： 运用原来的哈希值加上扩容数组长度得到新的数组索引位置，节约了性能利用；表为空时候resize()创建表，表中有数值resize()扩容

6. 数据插入方式

1.7： 头插法
1.8： 尾插法，避免了在并发时出现逆序和循环链表的情况

1.1.6 线程问题

1.7 死循环，数据丢失，并发执行扩容阶段
1.8 解决死循环，数据丢失仍然没有解决，并发put的时候

整体储存流程如下：

1.2 Set

1.2.1 Set集合基本操作

list是有序的，元素可以重复的；set是无序的，不能重复的

  • 主要Api：
    1
    2
    3
    4
    5
    6
    7
    8
    boolean add(E object) //添加一个元素，添加成功返回true
    void clear() //从Set集合中移除所有元素，该方法是从Collection集合继承过来的。
    Object clone()
    boolean contains(Object object) //判断集合内是否包含元素
    boolean isEmpty() //判断是否为空集合
    Iterator<E> iterator() //迭代器，遍历set集合用
    boolean remove(Object object) //移除元素
    int size() //数组长度
  • 遍历方式
  1. iterator遍历
    1
    2
    3
    4
    5
    6
    Set<String> set = new HashSet<String>();  
    Iterator<String> it = set.iterator();  
    while (it.hasNext()) {  
      String str = it.next();  
      System.out.println(str);  
    }
  2. 增强for遍历
    1
    2
    3
    for (String str : set) {  
          System.out.println(str);  
    }

2. 数组相关题目

2.1 字母异位词

相关题目

Problem 242 有效的字母异位词

复杂度

时间复杂度：O(n)
空间复杂度：O(1)

主要思想

这道题目要我们比较的是每个字符出现的次数，那么我们就有两个需要比较的量，一个是出现的字符是否相等，另一个是字符出现的次数是否相等，那么我们就可以想到，本题中的字符串由26个字母构成，是一个有限且可以连续的集合(将字符转换位ASCII码)，所以我们考虑用可存储连续集合的存储工具数组来进行存储，每个索引对应的值就是他出现的次数。那么每在s字符串出现一次，加上1； 每在t字符串出现一次，减去1； 因为异位词要求字母个数都相等，到最后只需要判断数组内的元素是否均为0即可。

注意点

本题可能有的会考虑用Map进行存储，key为字母字符，values为次数；是可以的，但是Map中key的特点是可以连续可以不连续，需要用一个哈希映射来存储相对应Map的值，而且也会新增很多空间，影响性能。而连续的集合用数组可以和Map达到一样的效果，但是空间成本小了。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isAnagram(String s, String t) {
        // 新建26位数组存储26个字母
        int[] temp = new int[26];
        // 加入记录
        for(int i = 0; i < s.length(); i++) {
            temp[s.charAt(i) - 'a'] ++;
        }
        // 移除记录
        for(int i = 0; i < t.length(); i++) {
            temp[t.charAt(i) - 'a'] --;
        }
        // 匹配是否还有记录
        for(int i = 0; i < 26; i++) {
            if(temp[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

2.2 赎金信

相关题目

Problem 383 赎金信

复杂度

时间复杂度：O(n)
空间复杂度：O(1)

主要思想

和上道题的思路是一样的，找要求的重复字符以及其出现的次数。这个升级版主要体现在他不是完全匹配的了，那我们就要从中想出加上的是哪个，减去的是哪个。那么这里用大的数组加入，小的数组减去，如果都大于0，说明大的完全能包含小的；如果小于0，说明大的里面由小的没有的元素。

注意点

学一下字符串的两种遍历方法吧，for增强遍历for(char ch : str.toCharArray)和直接遍历for()... str.charAt(i)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
    }
}

3. Set相关题目

3.1 两个数组的交集

相关题目

Problem 349 两个数组的交集

复杂度

时间复杂度：O(n)
空间复杂度：O(n)

主要思想

题目中说到输出结果中的每个元素一定是唯一的，那么就无需去考虑每个元素出现的次数了。所以我们只需判断的是有没有出现过即可，那么这种单一元素的判断，而且数组内元素是离散的，用数组会造成很多空间的浪费，所以我们想到了无连续的离散的集合Set。创建两个集合，其中一个作为比对集，负责比较有没有重复，另一个作为结果集，记录符合条件元素。

注意点

集合转数组的写法：resset.stream().mapToInt(x -> x).toArray()

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 计算的集合
        Set<Integer> tempset = new HashSet<>();
        // 结果输出的集合
        Set<Integer> resset = new HashSet<>();
        for(int i : nums1) {
            tempset.add(i);
        }
        for(int i : nums2) {
            if(tempset.contains(i)) {
                // 比对成功，加入结果集
                resset.add(i);
            }
        }
        return resset.stream().mapToInt(x -> x).toArray();
    }
}

3.2 快乐数

相关题目

Problem 202 快乐数

复杂度

时间复杂度：O(n)
空间复杂度：O(n)

主要思想

这道题明确声明了会有无限循环的情况出现，那么这道题得到的就两个结果，一个是我们确定是快乐数的条件：最后结果是1；另一个是无限循环，不是快乐数。所以我们可以直接在循环中设置退出条件一个是为1， 另一个是无限循环。那么要判断是否无限循环就是判断字符是否出现过，重复出现的问题想到哈希表，又因为我们只需要记录内容，次数我们不关心，一个维度我们就用Set就可以了。

注意点

获取每位数字的方法：第一步是取10模，得到个位的数字；第二步是除以10，将十位的数字移到下一位个位，然后不断循环，中止的条件是没有可以移动的位了，说明这个数已经被我们操作完了，也就是n > 0。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean isHappy(int n) {
        Set<Integer> code = new HashSet<>();
        // 因为会无限循环，所以到了重复的时候就说明无需再进行下去了
        while(n != 1 && !code.contains(n)){
            code.add(n);
            n = getNextCount(n);
        }
            return n == 1;
}


        // 获取每位数字的平方和
        private int getNextCount(int n) {
            int res = 0;
            while(n > 0) {
                int temp = n % 10;
                res += temp * temp;
                n = n / 10;
            }
            return res;
        }
    
}

4. Map相关题目

4.1 两数之和

相关题目

Problem 1 两数之和

复杂度

时间复杂度：O(n)
空间复杂度：O(n)

主要思想

我们需要通过数组的每个元素值对其进行计算，然后输出的是他的下标，那么这时候我们会发现，其实我们需要操作的是两个值，又需要对元素进行比对匹配，所以选择用Map集合或者数组存储会比较好一些，那我们就看到底是不是连续的。因为最后要输出的是索引，所以我们会选择把索引存在Values中，而元素就只能存在key中了，因为元素的离散的，所以我们只能用Map集合了。

注意点

每次一定都要好好想想空值和特殊值有没有办法包含在你的逻辑中，没有的话要提前排除掉。数组的空值具体实现为：nums == null || nums.length == 0

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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<>();
        // key为数组元素值，values为对应元素索引
        for(int i = 0; i < nums.length; i++) {
            int temp = target - nums[i];
            if(map.containsKey(nums[i])) {
                res[1] = i;
                res[0] = map.get(nums[i]);
                break;
            }
            map.put(temp, i);
        }
        return res;
    }
}

4.2 四数之和Ⅱ

相关题目

Problem 454 两数相加Ⅱ

复杂度

时间复杂度：O(n^2)
空间复杂度：O(n)

主要思想

这里要求我们输出的是元组的个数，也就是我们不需要具体的去确认他的下标，只需要知道有这个东西存在就可以了。所以我们要关心的就是元素的值。那其实我们可以两两拆分，遍历数组集合求出两个数组的和，然后再与另外两个数组匹配，时间复杂度虽然是n^2^，但是相较于暴力算法直接缩短了一半。但是我们发现，可能一个数的和可以由多种表现形式，所以我们还需要关心的一个点就是组成该和的个数。所以其实我们要考虑到的是两个变量，所以我们会使用Map集合，key用来存储两个数组和的值，values用来存储这个和的组成出现的次数。之后在进行配对的时候也要把所有符合的次数加上，也就计数的时候不是+1，而是+values了。

注意点

存储更新个数的操作：包含：map.put(sum, map.get(sum) + 1);不包含：map.put(nums1[i] + nums2[j], 1);

代码实现

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
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        // 计数器记录满足条件元组个数
        int count = 0;
        Map<Integer,Integer> map = new HashMap<>();
        // 两两配对生成集合
        for(int i = 0; i < nums1.length; i++) {
            for(int j = 0; j < nums2.length; j++) {
                int sum = nums1[i] + nums2[j];
                if(map.containsKey(sum)) {
                    // 存储个数更新的操作
                    map.put(sum, map.get(sum) + 1);
                }else{
                    map.put(nums1[i] + nums2[j], 1);
                }
            }
        }
        for(int i = 0; i < nums3.length; i++) {
            for(int j = 0; j < nums4.length; j++) {
                int temp = 0 - (nums3[i] + nums4[j]);
                    if(map.containsKey(temp)) {
                        // 需要进行所有的配对
                        count += map.get(temp);
                    }
            }
        }
        return count;
    }
}

4.3 三数之和

相关题目

Problem 15 三数之和

复杂度

时间复杂度：O(n^2)
空间复杂度：O(n)

主要思想

等于一个指定的值，那么就有大于小于等于三种情况，只有三者不断的中立，那么最后才能实现，那么我们就想到了其实可以用排序对他进行划分，那么排序就想到了双指针，但是这里有三个数怎么办呢，那么我们就固定一个，然后去走另外两个，等于是有两个变量的双指针就是O(a)级别的时间复杂度，有三个变量的双指针就是O(n)的时间复杂度，有n个变量的双指针就是O(n^n-2)的时间复杂度。

注意点

去重复的动作，因为题目明确告诉我们了一样的不算，那么我们怎么去重复呢，就对于固定指针而言，他前后不能一样，对于移动的双指针模型而言，他们两个不能同时一样即可。因为他们两组指针是相对运动的。 而有个细节的点就是判断固定指针去重的时候如果这么写nums[i] == nums[i + 1]，就会引发一个只是重复元素但是被我们排除的情况，因为我们未曾比较过，而后移了，这个本来应该操作的可操作范围就变小了，应该写成和i-1进行比较，这样才能确保所有都是匹配过的，操作范围上一个一样的比你大，那肯定你能匹配到的范围也是他能够匹配到的。
去重不能只去除一次，而要去到满足这个条件为止，所以不能用if，而要用while
将集合装进集合：list.add(Arrays.asList(nums[index], nums[left], nums[right]));

代码实现

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
45
46
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        // 对于第一项就大于0的有序数组，那么势必无法加起来等于0


        
        for(int index = 0; index < nums.length; index++){
                    if(nums[index] > 0) {
            return list;
        }
        // 对于index的去重
        if(index != 0 && nums[index] == nums[index - 1]) {
            continue;
        }
        int left = index + 1;
        int right = nums.length - 1;
        while(left < right){
            int sum = nums[index] + nums[left] + nums[right];
            if(sum > 0) {
                // 太大了，应该小一点，那么右边就缩小
                right --;
            } else if(sum < 0) {
                // 太小了，应该大一点，左边过来点
                left ++;
            } else if(sum == 0) {
                // 是我们的目标，装进集合里去！
            list.add(Arrays.asList(nums[index], nums[left], nums[right]));
            
            // 去重left
            while(left < right && nums[left] == nums[left + 1]) {
                left++;
            }
            // 去重right
            while(left < right && nums[right] == nums[right - 1]) {
                right--;
            }
            left++;
            right--;
            }
        }
        }
        return list;
    }
}

4.4 四数之和

相关题目

Problem 18 四数之和

复杂度

时间复杂度：O(n^3)
空间复杂度：O(n)

主要思想

比三数之和多了一层循环。

注意点

不要判断nums[k] > target 就返回了，三数之和 可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。

代码实现

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
45
46
47
48
49
50
51
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++) {
            // 剪枝处理
            if (nums[k] > target && nums[k] >= 0) {
            	break; // 这里使用break，统一通过最后的return返回
            }
            // 对nums[k]去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
                // 2级剪枝处理
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;
                }

                // 对nums[i]去重
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
                    if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
                        right--;
                    // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
                    } else if ((long) nums[k] + nums[i] + nums[left] + nums[right]  < target) {
                        left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        // 找到答案时，双指针同时收缩
                        right--;
                        left++;
                    }
                }

            }
        }
        return result;
    }
};