搜索概念及场景、模型一般把搜索的数据称为关键字Key和关键字对应的称为值Value将其称之为Key-value的键值对。所以模型会有两种1. 纯key模型Set 2. Key-Value 模型Map1.Set1.1特点Set是继承自Collection的接口类Set中只存储了键(Key)。【核心特点保存的元素无序、不能修改、不会重复】1.2常见方法核心操作add remove containsimport java.util.Iterator; import java.util.Set; import java.util.TreeSet; public class Test1 { public static void main(String[] args) { SetString set1 new TreeSet(); SetString set2 new TreeSet(); //添加元素 set1.add(ccc); set1.add(aaa); set1.add(ddd); set1.add(bbb); set2.add(ddd); set2.add(aaa); set2.add(ccc); set2.add(bbb); System.out.println(set1); System.out.println(set2); System.out.println(set1.equals(set2)); //无序无论添加时的顺序是什么 最后 set1与set2的顺序都是[aaa, bbb, ccc, ddd] //不重复无论输入几个 aaa 最后都只剩一个 aaa //判断元素是否在 Set 中存在 System.out.println(set1.contains(ccc)); //删除元素 set1.remove(ccc); System.out.println(set1); //获取元素个数 System.out.println(set1.size()); //判断是否为空 System.out.println(set1.isEmpty()); //清空整个集合 set1.clear(); System.out.println(set1); //遍历集合中的元素 //循环遍历 for(String s : set2){ System.out.println(s); } //基于迭代器遍历 IteratorString iterator set2.iterator(); while(iterator.hasNext()){ System.out.println(iterator.next()); } } }2.Map2.1特点Map是一个接口类该类没有继承自CollectionMap存储了键值对key-value并且K一定是唯一的不能重复。Map最主要的用途构建 key - value 映射关系 使用put插入键值对使用get 根据 key 获取value;2.2常见方法 (核心操作get put remove)package Set_Mao_12_2024_2_13; import java.util.*; public class Test_Map { public static void main(String[] args) { MapString, String map new TreeMap(); //MapString, String map2 new HashMap() //Map最主要的用途构建 key - value 映射关系 //使用 put 插入键值对 put(key, value) key 是唯一的 如果重复 取最后一个 map.put(黑旋风, 李逵); map.put(及时雨, 宋江); map.put(小李广, 花荣); map.put(呼保义, 宋江); map.put(黑旋风, 李鬼); System.out.println(map); //使用 get 根据 key 获取value; System.out.println(map.get(及时雨)); System.out.println(map.get(玉麒麟)); //若无此键值对 就会返回 null //或者使用 getOrDefault 可以在查找的时候 指定默认值 可以避免因为返回null产生的问题 //若 k 存在返回对应的值若 k 不存在返回指定的默认值 System.out.println(map.getOrDefault(及时雨, 梁山好汉)); //宋江 System.out.println(map.getOrDefault(玉麒麟, 梁山好汉)); //梁山好汉 //此处 size得到的是键值对的个数 System.out.println(map.size()); //判断 key 是否存在高效 树/哈希表 System.out.println(map.containsKey(及时雨)); //判断 value 是否存在低效 遍历 System.out.println(map.containsValue(宋江)); //拿到所有的 key value 慎用 低效 高开销操作 耗费空间和时间 SetString keySet map.keySet(); System.out.println(keySet); CollectionString values map.values(); System.out.println(values); //遍历 Map 中的键值对 慎用 低效 同样是高开销操作 for (Map.EntryString, String entry : map.entrySet()) { System.out.println(entry.getKey() : entry.getValue()); } //根据 key 删除键值对 map.remove(及时雨); System.out.println(map); //判断是否为空 System.out.println(map.isEmpty()); } }3.二叉搜索树Binary Search Tree3.1概念二叉搜索树又称二叉排序树它或者是一棵空树或者是在二叉树的基础上做了额外的要求。【二叉树数的度为2度就是子树的个数】如以下性质:1若它的左子树不为空则左子树上所有节点的值key都小于根节点的值key2若它的右子树不为空则右子树上所有节点的值key都大于根节点的值key3它的左右子树也分别为二叉搜索树int[ ] array { 5,3,4,1,7,8,2,6,0,9 };3.2操作--查找核心操作import com.sun.tools.javac.Main; import java.awt.desktop.AppReopenedEvent; //实现树的一个节点 class Node { public int key; public Node left, right null; public Node(int key) { this.key key; } Override public String toString() { return Node{ key key , left left , right right }; } } //实现二叉搜索树 Binary--二进制的 Search--寻找 也可缩写成 BST public class BinarySearchTree { private Node root null; // 根节点 空树 //1. 实现查找操作 查找 key 是否在树中存在 如果存在返回对应的节点位置 不存在返回null public Node find(int key) { if(root null) return null; Node cur root; while(cur ! null) { if(key cur.key) { cur cur.left; } else if(key cur.key) { cur cur.right; } else{ return cur; //相等 即找到了 } } //循环结束已经找到叶子结点了还没找到key说明不存在 return null; } }3.3操作--插入1如果树为空树即根 null直接插入。2如果树不是空树按照查找逻辑确定插入位置插入新结点。//与上文查找代码连接 //2. 实现插入操作 把新的元素插到树中 public void insert(int key) { //如果当前树是空树直接用 root 指向新节点即可 Node newNode new Node(key); if (root null) { root new Node(key); return; } //普通的树需要找到插入的位置再进行插入 //cur 用来找待插入元素的位置parent 记录 cur 的父元素 Node cur root; Node parent null; while (cur ! null) { if(key cur.key) { //往左找 parent cur; cur cur.left; } else if(key cur.key){ //往右找 parent cur; cur cur.right; } else { //对于相等的情况存在多种不同的处理方式 //当前不允许重复 key 存在并且 Set 只保存key直接return。 return; } } //通过上述循环最终得到 cur 为 null 的情况此时 parent 就是叶子结点也是要新插入元素的父亲 //就需要把 newNode 插入到 parent 的子节点上 但 此刻新节点 应该在 parent 的左子树 还是右子树上呢 if(key parent.key) { parent.left newNode; } else { parent.right newNode; } } //先序遍历 根 - 左 - 右 public static void preOrder(Node root) { if (root null) { return; } System.out.print(root.key ); preOrder(root.left); preOrder(root.right); } //中序遍历 左 - 根 - 右 public static void inOrder(Node root) { if (root null) { return; } inOrder(root.left); System.out.print(root.key ); inOrder(root.right); } public void print() { //先打印先序遍历 再打印中序遍历 System.out.println(先序遍历结果); preOrder(root); System.out.println(); System.out.println(中序遍历结果); inOrder(root); System.out.println(); } public static void main(String[] args) { int[] arr {1, 3, 2, 6, 5, 7, 8, 9, 10, 0}; BinarySearchTree tree new BinarySearchTree(); for(int key : arr){ tree.insert(key); } //查找 System.out.println(tree.find(9)); //插入 System.out.println(); //空一行 tree.insert(11); tree.print(); }3.4操作--删除较复杂设待删除结点--cur待删除结点的双亲结点--parent根节点--root 节点的值--key。//与上文 查找 插入代码连接 //3. 实现删除操作 public void remove(int key) { //不存在就不做任何事情 if(root null) return; //查找要删除节点的位置同时记录其父节点 Node cur root; Node parent null; while (cur ! null) { if(key cur.key) { //往左找 parent cur; cur cur.left; } else if(key cur.key){ parent cur; cur cur.right; } else { //找到了进行真正的删除操作 用removeNode方法 return; } } } private void removeNode(Node parent, Node cur) { //要考虑四种情况 //1. cur没有子树 if(cur.left null cur.right null) { //1.1 如果 cur 就是 root需要对 root 进行调整 if(cur root){ //说明整个树只有root一个节点 此时直接把root设为null即可 root null; return; } //1.2 cur 不是 root同时cur是parent的左子树 if(cur parent.left) { //此时把左子树置空就相当于删除了cur parent.left null; return; } //1.3 cur 不是 root同时cur是parent的右子树 if(cur parent.right) { //此时把右子树置空就相当于删除了cur parent.right null; return; } //理论上不会走到此处为了稳妥还是加上 return; } //2. cur只有左子树 if(cur.left ! null cur.right null) { //2.1 cur为root if(cur root) { root cur.left; return; } //2.2 cur不是root同时cur是parent的左子树 if(cur parent.left) { parent.left cur.left; return; } //2.3 cur不是root同时cur是parent的右子树 if(cur parent.right) { parent.right cur.left; return; } } //3. cur只有右子树 if(cur.left null cur.right ! null) { //3.1 cur为root if(cur root) { root cur.right; return; } //3.2 cur不是root同时cur是parent的左子树 if(cur parent.left) { parent.left cur.right; return; } //3.3 cur不是root同时cur是parent的右子树 if(cur parent.right) { parent.right cur.right; return; } } //4. cur有俩子树 if(cur.left ! null cur.right ! null) { //这种情况下不用考虑root 情况因为实际删除的不是cur指向的节点而是 “替罪羔羊节点” //4.1 先找到右子树中的最小值 -- 替罪羔羊节点 goat--山羊 后需要找其父亲也需要记录一下 Node goat cur.right; Node goatParent cur; while(goat.left ! null) { goatParent goat; goat goat.left; }//循环结束后goat就指向右子树的最左侧元素了 //4.2 移花接木 把替罪羊的值复制到cur中 cur.key goat.key; //4.3 真正删除 goat 节点goat是没有左子树的直接让 goatParent 连上 goat 的右子树即可 //即使goat的右子树是空也没影响 当然还有个坑goat不一定就是goatParent的左子树 if(goat goatParent.left) { goatParent.left goat.left; } else { goatParent.right goat.left; } } } public static void main(String[] args) { int[] arr {1, 3, 2, 6, 5, 7, 8, 9, 10, 0}; BinarySearchTree tree new BinarySearchTree(); for(int key : arr){ tree.insert(key); } //查找 System.out.println(tree.find(9)); //插入 System.out.println(); //空一行 tree.insert(11); tree.print(); }4.哈希表重点4.1概念该方式即为哈希(散列)方法哈希方法中使用的转换函数称为哈希(散列)函数构造出来的结构称为哈希表(Hash Table)或者称散列表。4.2哈希冲突1解决方案1-闭散列2解决方案2-开散列重点掌握冲突-避免-负载因子调节已知哈希表中已有的关键字个数是不可变的那我们能调整的就只有哈希表中的数组的大小。3哈希函数可以认真理解下面的例子注意哈希函数设计的越精妙产生哈希冲突的可能性就越低但是无法避免哈希冲突。4.3代码实现public class MyHashMap { // 使用 Node 表示 哈希表 中的链表节点. static class Node { public int key; public int value; public Node next; public Node(int key, int value) { this.key key; this.value value; } } // 一般来说这个数组的长度的设定也是有技巧的. // 一个典型的做法是选择素数作为数组的长度. 减少哈希冲突的概率. private Node[] table new Node[1001]; private int size; // 设定哈希函数. 把 key 转成数组下标. private int hashCode(int key) { return key % table.length; } // 哈希表的核心操作 // 插入/修改键值对 public void put(int key, int value) { // 1. 根据参数 key, 计算出下标位置. int index hashCode(key); // 2. 遍历链表, 看一下 key 是否是在链表中已经存在. // 如果存在, 就修改对应的 value. Node head table[index]; for (Node cur head; cur ! null; cur cur.next) { if (cur.key key) { cur.value value; return; } } // 3. 如果不存在, 直接插入; 按照头插的方式. Node newNode new Node(key, value); newNode.next head; table[index] newNode; // 4. 插入完成后, size 就要自增. size; // 5. 扩容 if ((double)size / table.length 0.75) { resize(); } } private void resize() { // 1. 创建一个更大的数组. 直接 * 2 是简单粗暴的做法. 更好的做法, 是找到一个刚好大于原来 size 2 倍多点的素数. Node[] newTable new Node[table.length * 2]; // 2. 搬运, 把原来 table 中的所有的链表元素都搬运过来. for (int i 0; i table.length; i) { for (Node cur table[i]; cur ! null; cur cur.next) { // 根据这个节点, 创建新节点, 插入到新的数组中. Node newNode new Node(cur.key, cur.value); int newIndex cur.key % newTable.length; // 把新节点, 头插到新的链表中. newNode.next newTable[newIndex]; newTable[newIndex] newNode; } } // 3. 使用新的数组替换旧的. table newTable; } // 根据键获取值 public Integer get(int key) { // 1. 根据 key, 计算出下标. int index hashCode(key); // 2. 在对应的链表上找到该 key 的 value 值. for (Node cur table[index]; cur ! null; cur cur.next) { if (cur.key key) { return cur.value; } } // 3. 通过上述循环, 都没有找到, 最终结果就返回 null. return null; } // 删除键值对. 本质上就还是链表删除. // 插入的时候, 一般要考虑扩容; 删除的时候, 一般不会考虑缩容~~ public void remove(int key) { // 1. 根据 key 找到下标. int index hashCode(key); // 2. 针对链表删除 key 的节点. // a) 先考虑链表为空的情况 if (table[index] null) { // 链表为空, 直接返回, 不需要删除 return; } // b) 先考虑是否是 头结点 的情况 if (table[index].key key) { table[index] table[index].next; size--; return; } // c) 一般情况, 遍历链表. 遍历的同时把该节点的前一个节点, 也记录一下. Node prev table[index]; Node cur table[index].next; while (cur ! null) { if (cur.key key) { // 触发删除操作. prev.next cur.next; size--; // 由于 hash 表中的 key 是唯一的. return; } prev cur; cur cur.next; } } }4.4性能分析虽然哈希表一直在和冲突做斗争但在实际使用过程中我们认为哈希表的冲突率是不高的冲突个 数是可控的也就是每个桶中的链表的长度是一个常数所以通常意义下我们认为哈希表的插入/ 删除/查找时间复杂度是O(1)。5.OJ 面试题5.1只出现一次的数字https://leetcode.cn/problems/single-number/descriptionimport java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; public class MapProblem { public int singleNumber(int[] nums) { // 使用 HashMap 统计每个数字出现的次数 // 再遍历 HashMap, 找到出现一次的数字. MapInteger, Integer map new HashMap(); for (int num : nums) { //不想让他返回n空 就设置默认值为0 int count map.getOrDefault(num, 0); map.put(num, count 1); } // 遍历该 map, 找到出现一次的数字. for (Map.EntryInteger, Integer entry : map.entrySet()) { if (entry.getValue() 1) { return entry.getKey(); } } // 正常来说, 不会走这个逻辑. 题目会保证数组 nums 中一定存在出现次数为 1 的数字. return 0; } }public int singleNumber(int[] nums) { // 通过异或的方式实现. int result 0; for (int num : nums) { result ^ num; } return result; }5.2复制带随机指针的链表https://leetcode.cn/problems/copy-list-with-random-pointer/需要有Node 再写成静态内部类import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; public class MapProblem { static class Node { int val; Node next; Node random; public Node(int val) { this.val val; this.next null; this.random null; } } public Node copyRandomList(Node head) { // 1. 创建 Map, key 是旧节点, value 是新节点. MapNode, Node map new HashMap(); // 2. 遍历旧链表, 依次创建新节点, 并插入 map 中. for (Node oldNode head; oldNode ! null; oldNode oldNode.next) { Node newNode new Node(oldNode.val); map.put(oldNode, newNode); } // 3. 再次遍历旧链表, 建立 next 和 random 指向. for (Node oldNode head; oldNode ! null; oldNode oldNode.next) { Node newNode map.get(oldNode); // 连接 next Node newNodeNext map.get(oldNode.next); newNode.next newNodeNext; // 连接 random Node newNodeRandom map.get(oldNode.random); newNode.random newNodeRandom; } // 4. 返回新链表的头节点. return map.get(head); } }5.3宝石与石头https://leetcode.cn/problems/jewels-and-stones/description/import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; public class MapProblem { public int numJewelsInStones(String jewels, String stones) { // 1. 创建 Set, 存储宝石. SetCharacter set new HashSet(); // 2. 遍历宝石, 加入 Set. for (char c : jewels.toCharArray()) { set.add(c); } // 3. 遍历石头, 统计宝石的数量. int count 0; for (char c : stones.toCharArray()) { // 使用 hash 来查询, 效率更高的. // if (set.contains(c)) { // count; // } if (jewels.indexOf(c) 0) { count; } } return count; } }5.4坏键盘打字https://www.nowcoder.com/questionTerminal/f88dafac00c8431fa363cd85a37c2d5eimport java.util.HashSet; import java.util.Scanner; import java.util.Set; public class BrokenKey { public static void main(String[] args) { Scanner in new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNext()) { // 注意 while 处理多个 case // 长的, 完整的内容 String expected in.next(); // 短的, 残缺的内容 String actual in.next(); // 1. 把这俩字符串都转成大写. expected expected.toUpperCase(); actual actual.toUpperCase(); // 2. 遍历 actual, 把 actual 里的内容添加到 Set 中. SetCharacter actualSet new HashSet(); for (int i 0; i actual.length(); i) { actualSet.add(actual.charAt(i)); } // 3. 遍历 expected, 看是否在 actualSet 中不存在 SetCharacter brokenSet new HashSet(); for (int i 0; i expected.length(); i) { char c expected.charAt(i); if (!actualSet.contains(c)) { // 说明当前的 c 就是坏了的按键. // 输出之前, 要判定一下是否已经输出过了. if (brokenSet.contains(c)) { continue; } // 没有输出过才能打印, 一定是使用 print 而不是 println. System.out.print(c); brokenSet.add(c); } } // 最后打印换行, 表示结果结束了. System.out.println(); } } }