哈希表

一般哈希表都是用来快速判断一个元素是否出现集合里。但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。Hash法的优势就是牺牲了空间去换了时间，在工业场景中也很适用。

实现理论

哈希函数打比方：就是将学生姓名映射为哈希表上的索引，通过特定编码方式生成hashCode。如果hashCode超过哈希表大小（tableSize），会进行取模操作以确保映射在表内。但如果学生数量大于表大小，可能导致多个学生映射到同一索引位置。

发生冲突的解决办法：

拉链法

注意点：拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

线性探测法

注意点：一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。

Hash数组——242.有效的字母异位词

力扣题目链接

方法理论很简单，直接定义一个数组critic全为0；判断两个数组中的元素，A数组中存在元素就++，B数组中存在的元素就–；最后判断critic数组是否全为0。为0就代表是移位词。要求只有小写字母，那么就给我们浓浓的暗示，用数组！然后这里涉及到一个要采用哪种hash的实现方法的问题一般有

• 数组

• set （集合）

  数组局限性

  数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制。

  如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

• map(映射)

  数组和set来做哈希法的局限

  数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。

  set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。

  每个部分还是有不同底层实现。

所以我们要根据不同的问题来选择实现的方式。然后从速度上分析如果可以用数组解决就用数组解决，因为其他hash方式需要进行hash函数的加密。

Hashset——349. 两个数组的交集

力扣题目链接

如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。这个思路就是建议用Set来解决问题，因为set可以不用申请连续的空间，而相比之下map是键值对的形式，可以用key存储查找的值，用value存储次数。可以方便的使用set1.contains来检测是在集合中。

for (int i:nums2){
    if (set1.contains(i)) set2.add(i);
}

​

Hashmap——454.四数相加II

力扣题目链接

这个题目是有四个数组并没不用考虑有重复的四个元素所以可以很直接的想到用hash map来解决。这道题目中并不需要key有序，选择std::unordered_map 效率更高！然后还需要思考map应该怎么用。第一步计算两个数相加的和，用和做键值， value 做重复的次数，然后在用两个数相加来找有多少个为0的情况。

• map用来做什么

• map中key和value分别表示什么

  class Solution {
      public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
          int res = 0;
          Map<Integer, Integer> map = new HashMap<Integer, Integer>();
          //统计两个数组中的元素之和，同时统计出现的次数，放入map
          for (int i : nums1) {
              for (int j : nums2) {
                  int sum = i + j;
                  map.put(sum, map.getOrDefault(sum, 0) + 1);
              }
          }
          //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
          for (int i : nums3) {
              for (int j : nums4) {
                  res += map.getOrDefault(0 - i - j, 0);
              }
          }
          return res;
      }
  }

难点还是想到要用hash来解决问题

伪Hash——第15题. 三数之和

力扣题目链接

这个题就，如果用hash的解决方法就不行，因为他要求不重复比如 -1，1，0和 1，-1，0就算重复，所以要直接通过两层for循环来判断的话，可能会出现重复的情况。所以现有的解发就是双指针排序，设置左右节点，最外层for循坏迭代，，right和left寻找能与之组队的数判断的原则就是看三数之和大于0还是小于0。其中的List的声明也可以学习一下，

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
	// 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.length; i++) {
	    // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) { 
                return result;
            }

            if (i > 0 && nums[i] == nums[i - 1]) {  // 去重a
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;
            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
		    // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    
                    right--; 
                    left++;
                }
            }
        }
        return result;
    }
}

Hash常用库函数

ArrayList

ArrayList 是 Java 中常用的动态数组实现，它提供了一系列常用的方法来操作列表。以下是一些常见的 ArrayList 方法：

• 添加元素：

  • add(E element): 将元素添加到列表的末尾。

  • add(int index, E element): 在指定位置插入元素。

ArrayList<String> list = new ArrayList<>();
list.add("One");
list.add("Two");
list.add(1, "Three"); // 在索引1处插入元素 "Three"

• 获取元素：
  • get(int index): 获取指定位置的元素。

String element = list.get(1); // 获取索引1处的元素

• 更新元素：
  • set(int index, E element): 替换指定位置的元素。

list.set(1, "NewElement"); // 将索引1处的元素替换为 "NewElement"

• 删除元素：

  • remove(int index): 移除指定位置的元素。

  • remove(Object obj): 移除指定元素。

  • clear(): 清空列表中的所有元素。

list.remove(1); // 移除索引1处的元素
list.remove("Two"); // 移除元素 "Two"
list.clear(); // 清空列表

• 查询元素：

  • contains(Object obj): 判断列表是否包含指定元素。

  • indexOf(Object obj): 返回指定元素的第一个出现位置的索引。

boolean contains = list.contains("One"); // 判断列表是否包含 "One"
int index = list.indexOf("Two"); // 获取元素 "Two" 的索引

• 列表大小和判空：
  • size(): 返回列表中的元素个数。
  • isEmpty(): 判断列表是否为空。

int size = list.size(); // 获取列表大小
boolean isEmpty = list.isEmpty(); // 判断列表是否为空

HashSet

HashSet 是 Java 中的一个集合类，它实现了 Set 接口，底层基于哈希表实现。以下是 HashSet 常用的一些方法：

1. 添加元素：

   • boolean add(E e): 将指定的元素添加到集合中，如果元素已经存在，则不会重复添加，返回 true 表示添加成功，false 表示元素已存在。

   HashSet<String> set = new HashSet<>();
   set.add("apple");
   set.add("banana");

2. 移除元素：

   • boolean remove(Object o): 从集合中移除指定的元素，如果元素存在并成功移除，则返回 true。

   set.remove("banana");

3. 清空集合：

   • void clear(): 移除集合中的所有元素。

   set.clear();

4. 判断集合是否为空：

   • boolean isEmpty(): 判断集合是否为空。

   if (set.isEmpty()) {
       System.out.println("集合为空");
   }

5. 获取集合大小：

   • int size(): 获取集合中元素的数量。

   int size = set.size();

6. 判断元素是否存在：

   • boolean contains(Object o): 判断集合中是否包含指定的元素。

   if (set.contains("apple")) {
       System.out.println("集合包含苹果");
   }

7. 遍历集合：

   • 使用迭代器或增强 for 循环来遍历集合中的元素。

   for (String element : set) {
       System.out.println(element);
   }

HashMap

HashMap 是 Java 中常用的集合类，它实现了 Map 接口，提供了键值对的存储和检索功能。以下是 HashMap 常用的一些方法：

1. put(K key, V value)：

   • 将指定的键值对存储在 HashMap 中。如果键已经存在，则替换对应的值，并返回旧值。

   HashMap<String, Integer> map = new HashMap<>();
   map.put("One", 1);
   map.put("Two", 2);

2. get(Object key)：

   • 返回指定键所映射的值，如果该键不存在，则返回 null。

   Integer value = map.get("One");

3. containsKey(Object key)：

   • 判断 HashMap 中是否包含指定键。

   boolean containsKey = map.containsKey("Three");

4. containsValue(Object value)：

   • 判断 HashMap 中是否包含指定值。

   boolean containsValue = map.containsValue(2);

5. remove(Object key)：

   • 从 HashMap 中移除指定键及其对应的值。

   map.remove("One");

6. size()：

   • 返回 HashMap 中键值对的数量。

   int size = map.size();

7. keySet()：

   • 返回包含 HashMap 中所有键的集合。

   Set<String> keys = map.keySet();

8. values()：

   • 返回包含 HashMap 中所有值的集合。

   Collection<Integer> values = map.values();