集合进阶二 （Set Map Steam流）

一.Set集合1.特点注意无序不是每次执行出来的结果都是不一样的-------------默认升序2.HashSet集合的底层原理基于哈希表1哈希表eg.冲突是必然的 只能去降低冲突率1哈希冲突的避免1常见哈希函数设计2*负载因子调节哈希冲突的根本原因是哈希函数的设计和负载因子没有必然的 “一定冲突” 关系负载因子只影响冲突的概率。负载因子 α1 只是说明元素数量等于容量不代表新元素的哈希值一定会和已有元素的哈希值重复只是冲突的概率极高但不是 “一定”。更重要的是对于拉链式哈希桶是无限扩展的不存在 “桶满” 的情况冲突只和哈希函数有关和负载因子无关。2哈希冲突的解决1闭散列线性探测二次探测2开散列3hashcodehashCode()为对象返回一个整数哈希值用于在哈希表中快速定位对象。核心作用配合equals()一起决定对象在哈希集合中的唯一性和存储位置。哈希表通过hashCode()计算桶下标用equals()验证桶内元素是否相等大幅提升查找效率从 O(n) 降到 O(1) 平均hashCode()的 5 条核心约定一致性同一对象多次调用hashCode()必须返回相同整数前提是对象未被equals()比较的属性修改。相等性如果a.equals(b) true则a.hashCode()必须等于b.hashCode()。不等性如果a.equals(b) falsea.hashCode()不强制要求不同但尽量不同减少哈希冲突提升性能。不可变性不要用可变字段计算hashCode()否则对象修改后哈希值变化会导致哈希集合中「找不到」该对象。性能哈希值应尽量均匀分布避免大量对象哈希值相同极端情况会让哈希表退化成链表时间复杂度 O(n)。hashCode()与equals()的绑定关系只要重写了equals()就必须重写hashCode()否则违反上述约定 2导致哈希集合异常。Override public int hashCode() { // 传入参与 equals 比较的所有字段 return Objects.hash(id, name, age); }常见面试考点hashCode()和equals()的关系答equals()相等的对象hashCode()必须相等hashCode()相等的对象equals()不一定相等哈希冲突。重写equals()必须重写hashCode()。为什么重写equals()必须重写hashCode()答违反 Java 规范导致哈希集合如HashSet、HashMap无法正确识别相等对象出现逻辑错误。hashCode()可以返回固定值吗答语法上可以但会导致所有对象哈希值相同哈希表退化成链表时间复杂度 O(n)性能极差绝对不推荐。String、Integer等包装类的hashCode()是怎么实现的String用字符串内容计算哈希值缓存结果避免重复计算Integer直接返回int值本身Long返回(int)(value ^ (value 32))Double用Double.doubleToLongBits()转换后计算哈希值Objects.hash()和手动计算的区别答Objects.hash()内部会对数组做哈希计算自动处理null代码更简洁手动计算性能略高但容易出错推荐用Objects.hash()。两步定位法第一步定位桶通过hashCode()当你调用map.put(key, value)时JVM 会先调用key.hashCode()计算出一个哈希值。通过这个哈希值计算出数组下标桶的位置。目的把不同的对象分散到不同的桶里实现 “分桶”。第二步确认元素通过equals()定位到桶后如果桶里有多个元素链表 / 树结构JVM 会遍历这些元素调用key.equals(element)来逐个比对直到找到完全一致的那个。目的在同一个桶内精确锁定目标元素。扩容的时候需要注意什么扩容后 也要重新哈希每个值4哈希桶完整代码// key-value 模型 public class HashBucket { private static class Node { private int key; private int value; Node next; public Node(int key, int value) { this.key key; this.value value; } } private Node[] array; private int size; // 当前的数据个数 private static final double LOAD_FACTOR 0.75; private static final int DEFAULT_SIZE 8; // 默认桶的大小 // 构造方法 public HashBucket() { array new Node[DEFAULT_SIZE]; size 0; } // 插入/更新 key-value返回旧 value不存在返回 -1 public int put(int key, int value) { // 1. 计算下标 int index key % array.length; // 保证下标非负 index index 0 ? -index : index; // 2. 遍历链表看 key 是否已经存在 Node cur array[index]; while (cur ! null) { if (cur.key key) { // key 已存在更新 value返回旧值 int oldVal cur.value; cur.value value; return oldVal; } cur cur.next; } // 3. key 不存在头插法插入新节点 Node newNode new Node(key, value); newNode.next array[index]; array[index] newNode; size; // 4. 判断是否需要扩容 if (loadFactor() LOAD_FACTOR) { resize(); } return -1; } // 扩容2倍扩容 重新哈希 private void resize() { // 新数组是原来的 2 倍 Node[] newArray new Node[array.length * 2]; // 遍历每个桶 for (int i 0; i array.length; i) { Node cur array[i]; // 遍历每个节点重新计算下标插入新数组 while (cur ! null) { Node next cur.next; // 保存下一个节点 int index cur.key % newArray.length; index index 0 ? -index : index; // 头插法插入新数组 cur.next newArray[index]; newArray[index] cur; cur next; } } // 替换成新数组 array newArray; } // 获取 key 对应的 value不存在返回 -1 public int get(int key) { int index key % array.length; index index 0 ? -index : index; Node cur array[index]; while (cur ! null) { if (cur.key key) { return cur.value; } cur cur.next; } return -1; } // 计算负载因子 private double loadFactor() { return size * 1.0 / array.length; } }5只出现一次的数字class Solution { public int singleNumber(int[] nums) { HashSetInteger hashsetnew HashSet(); //使集合中的数字都只出现一次 for(int i0;inums.length;i){ if(!hashset.contains(nums[i])){ hashset.add(nums[i]); }else{ hashset.remove(nums[i]); } } //判断哪个是集合中的数字 for(int i0;inums.length;i){ if(hashset.contains(nums[i])){ return nums[i]; } } return -1; } }6宝石与石头public int numJewelsInStones(String jewels, String stones) { HashSetCharacter hashsetnew HashSet(); //将所有的宝石放进hashset集合 for(int i0;ijewels.length;i){ char chjewels.charAt(i); hashset.add(ch); } //遍历stones 寻找在宝石集合的元素 int count0; for(int i0;istones.length;i){ char chstones.charAt(i); if(hashset.contains(ch)){ count; } } return count; }7随机链表的复制第一次遍历第二次遍历class Solution { public Node copyRandomList(Node head) { if(headnull){ return null; } HashMapNode,Node hashmapnew HashMap(); //第一次遍历 Node curhead; while(cur!null){ Node newNodenew Node(cur.val); hashmap.put(cur,newNode); curcur.next; } //修改next和random的值 curhead; while(cur!null){ hashmap.get(cur).nexthashmap.get(cur.next); hashmap.get(cur).randomhashmap.get(cur.random); curcur.next; } return hashmap.get(head); } }8坏键盘打字public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 1. 读取输入期望字符串、实际字符串 String expected scanner.nextLine(); String actual scanner.nextLine(); // 2. 构建好键集合实际出现的字符统一转大写去重 SetCharacter goodKeys new HashSet(); for (char c : actual.toCharArray()) { // 字母转大写其他字符数字、下划线保持不变 char upperC Character.toUpperCase(c); goodKeys.add(upperC); } // 3. 遍历期望字符串找坏键按发现顺序去重 SetCharacter printed new HashSet(); // 记录已经输出过的坏键 StringBuilder result new StringBuilder(); for (char c : expected.toCharArray()) { char upperC Character.toUpperCase(c); // 条件不在好键集合 且 未输出过 → 是坏键 if (!goodKeys.contains(upperC) !printed.contains(upperC)) { result.append(upperC); printed.add(upperC); // 标记为已输出避免重复 } } // 4. 输出结果 System.out.println(result); }2底层原理{占满12个就会扩容至原数组的两倍}---------------------------------------------------------------------------------------------------------------------------直接在生成里面选择3.LinkedHashSet集合的底层原理基于哈希表 双链表4.TreeSet集合基于红黑树法一法二二.Map集合1.概述发现重复的键后面的数据会覆盖前面的2.常用方法注意类型也要准确Set集合无序 不重复Collection集合包含list有序 可重复Set无序 不可重复queue队列通常可重复倒入的元素会覆盖原有的元素(相同时3.遍历方法1.键找值2.键值对其中 增强for循环元素类型就是map.entry类型ctrlaltv 自动补全为3.Lambda表达式4.Map集合案例-统计投票人数5.HashMap键相同的时候才是新的覆盖旧的这里是不同的键计算得到了相同的哈希值Map 只比较 key不比较 value1. 计算 key.hashCode() → 找到数组下标2. 去到对应位置遍历链表/红黑树3. 对每个节点的 key 调用 key.equals(要找的key)4. 若返回 true → 认为是同一个key → 覆盖value5. 若返回 false → 继续找 / 新增节点发现前两个蜘蛛精都出现了要想去重 在学生类中重写equalsand hashcode方法自带重写的方法6.LinkedHashMap7.TreeMap同时重写了equals和hashcode或者8.集合的嵌套-案例省和市使用Collections工具类调用addAll而不用具体实现类ArrayList面向接口编程通过使用Collections.addAll()或接口方法代码不依赖于具体的实现类如ArrayList而是依赖于更高级的接口如List或Collection。这使得代码更加通用可以轻松地切换不同的实现类例如从ArrayList切换到LinkedList而无需修改依赖这些接口的代码。如果需要操作集合优先考虑Collections工具类而不是直接调用具体实现类的方法。三.Steam流1.认识Stream--原始方法结合lambda表达式 这两个lambda表达式也可以用合并一个(像淡黄色行代码 可以set.stream后点击CtrlAltv自动补全由于直接调用steam方法是Collection提供的 Map不支持 所以可以就键 值 键值对而言也可以连续调用方法2.Stream的常用方法1.Steam流常见的中间方法比较器比较小数时需要使用Double.compare(double a, double b)的方法来避免浮点数比较的陷阱Double.compare(double a, double b)的返回值负整数如果a小于b。零如果a等于b。正整数如果a大于b此处map函数相当于将Student对象全部映射成其名字当需要合并的两个steam流类型不一样时 则allst的类型为Object。2.Steam流常见的终结方法用get方法得到最终结果max()方法返回的是一个OptionalT对象而不是直接返回流中的元素 get()是Optional的方法用于直接提取值但如果流为空会抛出异常。