Map和Set是一种专门用来搜素的容器或者数据结构，其搜索的效率与其具体的实例化子类有关，是一种适合动态查找的集合容器

一、模型

       一般把搜索的数据称为关键字（Key），和关键字对应的称为值（Value），将其称为Key-Value的键值对 

因此模型会有两种：

   1、纯Key模型

   2、Key-Value模型

其中Map中存储的是Key-Value的键值对，Set中只存储了Key

二、Map的使用

   由此可知：Map是一个接口类，该类没有继承Collection，该类中存储的是结构的键值对，并且K是唯一的，不能重复

  1、Map.Entry的说明

          Map.Entry是Map内部实现的用来存放键值对映射关系的内部类，该类主要提供了的获取

注： Map.Entry并没有提供设置Key的方法

 2、Map的常用方法

注：

    （1） Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap

    （2） Map中存放键值对的Key是唯一的，value是可以重复的

    （3）Map的Key可以全部分离出来，存储到Set中进行访问（因为Key不能重复）

    （4）Map的value可以全部分离出来，存储到Collection中的任意一个子集合中进行访问（因为value不能重复）

    （5）Map中键值对中的Key不能直接修改，value可以修改，如果要修改key，只能先将key删除掉，然后再进行重新插入

    （6）TreeMap和HashMap的区别

 3、HashMap的使用案例

public class TestHashMap {public static void main(String[] args) {Map hashMap = new HashMap<>();hashMap.put(1,"hello");hashMap.put(3,"world");hashMap.put(20,"world");hashMap.put(4,"world");hashMap.put(5,"world");System.out.println(hashMap);//输出是无序的System.out.println(hashMap.getOrDefault(100,"啥也没有"));//按照指定的key获取valueString v1 = hashMap.get(1);String v5 = hashMap.get(5);System.out.println(v1);System.out.println(v5);}
}

 4、TreeMap的使用案例

import java.util.Collection;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;public class TestTreeMap {//TreeMap的演示，是有序的public static void main(String[] args) {TreeMap treeMap = new TreeMap<>();treeMap.put(1,"hello");treeMap.put(3,"world");treeMap.put(2,"world");treeMap.put(4,"world");treeMap.put(5,"world");System.out.println(treeMap);//按照指定的key获取valueString v1 = treeMap.get(1);String v5 = treeMap.get(5);System.out.println(v1);System.out.println(v5);String v4 = treeMap.getOrDefault(4,"空值");String v10 = treeMap.getOrDefault(10,"空值");System.out.println(v4);System.out.println(v10);//删除指定的元素treeMap.remove(5);System.out.println(treeMap);//获取所有的key的不重复集合Set keySet = treeMap.keySet();System.out.println(keySet);//获取所有的valueCollection values = treeMap.values();System.out.println(values);//是否包含key，是否包含valueSystem.out.println(treeMap.containsKey(1));System.out.println(treeMap.containsValue("hello"));//遍历fun1(treeMap);System.out.println("方法二");fun2(treeMap);}//根据所有的key去获取值，方法一，不常用private static void fun1(Map map) {Set keySet = map.keySet();for (Integer key : keySet) {System.out.println("key = " + key + " value = " + map.get(key));}}//方法二private static void fun2(Map map) {Set> entries = map.entrySet();for (Map.Entry entry : entries) {System.out.println("key = " + entry.getKey() + " value = " + entry.getValue());}}
}

三、Set的说明

        Set是继承自Collection的接口类，Set只存储了key

 1、常见方法说明

注：

     （1）Set是继承Collection的一个接口类

     （2） Set只存储了key，并且要求key唯一

     （3）Set底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的

     （4）Set最大的功能就是对集合中的元素进行去重

     （5）实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序

     （6）Set的key不能修改，如果要修改，先把原来的删除，再重新插入

     （7）Set不能插入null的key

     （8）TreeSet和HashSet的区别

三、搜索树

     二叉搜索树又被称为二叉排序树，它或者是一颗空树，或者是具有以下性质的二叉树

    若它的左子树不为空，那么左子树上所有的节点的值都小于根节点的值

    若它的右子树不为空，那么右子树上所有的节点的值都大于根节点的值

    它的左右子树也分别为二叉搜索树

 1、删除操作

       设待删除的结点为cur，双亲结点为parent

        （1）cur.left == null

                    cur是root，则root == cur.right

                    cur不是root，cur是parent.left，则parent.left == cur.right

                    cur不是root，cur是parent.right，则parent.right == cur.right

        （2）cur.right == null

                    cur是root，则root == cur.left

                    cur不是root，cur是parent.left，则parent.left == cur.left

                    cur不是root，cur是parent.right，则parent.right == cur.left

        （3）cur.left != null && cur.right != null

                   需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点（关键码最小），用它的值填补到被删除节点中，再来处理该结点的删除问题

  2、实现

public class BinarySearchTree {private static class TreeNode {TreeNode left;TreeNode right;int val;public TreeNode(int val) {this.val = val;}}public TreeNode root;/*** 查找指定的值是否存在* @param val* @return*/public boolean search(int val) {return false;}/*** 插入一个元素* @param val 要插入的值* @return*/public boolean insert(int val) {TreeNode node = new TreeNode(val);if (root == null) {root = node;return true;}TreeNode cur = root;TreeNode pre = null;while (cur != null) {if (val == cur.val) {return false;}pre = cur;if (val < cur.val) {cur = cur.left;} else {cur = cur.right;}}if (val < pre.val) {pre.left = node;} else {pre.right = node;}return true;}public boolean remove(int val) {if (root == null) {return false;}TreeNode cur = root;TreeNode parent = null;while (cur != null) {if (cur.val == val) {removeNode(parent,cur);return true;}parent = cur;if (cur.val > val) {cur = cur.left;} else {cur = cur.right;}}return false;}private void removeNode(TreeNode parent,TreeNode cur) {if (cur.left == null) {if (cur == root) {root = cur.right;} else if (cur == parent.left) {//当前节点是父节点的左孩子节点时parent.left = cur.right;} else {//当前节点是父节点的右孩子节点时parent.right = cur.right;}} else if (cur.right == null) {if (cur == root) {root = cur.left;} else if (cur == parent.left) {//当前节点是父节点的左孩子节点时parent.left = cur.left;} else {//当前节点是父节点的右孩子节点时parent.right = cur.left;}} else {TreeNode target = cur.right;TreeNode parentTarget = cur;while (target.left != null) {parentTarget = target;target = target.left;}//到达叶子节点cur.val = target.val;//删除target节点if (target == parentTarget.left) {parentTarget.left = target.right;} else {parentTarget.right = target.right;}}}public String inorder(TreeNode node) {StringBuilder sb = new StringBuilder();if (node == null) {return sb.toString();}String left  =inorder(node.left);sb.append(left);sb.append(node.val + " ");String right = inorder(node.right);sb.append(right);return sb.toString();}public boolean search1(int val) {if (root == null) {return false;}TreeNode cur = root;while (cur != null) {if (val == cur.val) {return true;}if (val < cur.val) {cur = cur.left;} else {cur = cur.right;}}return false;}
}

四、练习题加深理解

import java.util.*;public class Exe_01 {public static void main(String[] args) {//生成十万个元素的数组int capacity = 10000;int[] arr = new int[capacity];Random random = new Random();for (int i = 0;i < arr.length;i++) {int value = random.nextInt(capacity);arr[i] = value;}fun1(arr);fun2(arr);fun3(arr);}//去除十万个元素中重复的元素public static void fun1(int[] arr) {Set set = new HashSet<>();for (int i = 0;i < arr.length;i++) {set.add(arr[i]);}System.out.println("去重后元素个数" + set.size());}//查找十万个元素中第一次重复的元素public static void fun2(int[] arr) {Set set = new HashSet<>();for (int i = 0;i < arr.length;i++) {if (!set.contains(arr[i])) {set.add(arr[i]);} else {System.out.println("第一个重复的元素" + arr[i]);return;}}}//统计十万个元素中，每个元素出现的次数public static void fun3(int[] arr) {Map map = new HashMap<>();for (int i = 0;i < arr.length;i++) {int cnt = map.getOrDefault(arr[i],0);map.put(arr[i],cnt + 1);}}
}