Map和Set的详解

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

一、模型

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

因此模型会有两种：

   1、纯Key模型

   2、Key-Value模型

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

二、Map的使用

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

  1、Map.Entry<K,V>的说明

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

注： Map.Entry<K,V>并没有提供设置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<Integer,String> 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获取value
        String 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<Integer,String> 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获取value
        String 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<Integer> keySet = treeMap.keySet();
        System.out.println(keySet);
        //获取所有的value
        Collection<String> values = treeMap.values();
        System.out.println(values);
        //是否包含key，是否包含value
        System.out.println(treeMap.containsKey(1));
        System.out.println(treeMap.containsValue("hello"));
 
        //遍历
        fun1(treeMap);
        System.out.println("方法二");
        fun2(treeMap);
 
    }
    //根据所有的key去获取值，方法一，不常用
    private static void fun1(Map<Integer, String> map) {
        Set<Integer> keySet = map.keySet();
        for (Integer key : keySet) {
            System.out.println("key = " + key + " value = " + map.get(key));
        }
    }
 
    //方法二
    private static void fun2(Map<Integer, String> map) {
        Set<Map.Entry<Integer,String>> entries = map.entrySet();
        for (Map.Entry<Integer,String> 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<Integer> 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<Integer> 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<Integer, Integer> map = new HashMap<>();
        for (int i = 0;i < arr.length;i++) {
            int cnt = map.getOrDefault(arr[i],0);
            map.put(arr[i],cnt + 1);
        }
    }
}