Map和Set是一种专门用来搜素的容器或者数据结构,其搜索的效率与其具体的实例化子类有关,是一种适合动态查找的集合容器
一、模型
一般把搜索的数据称为关键字(Key),和关键字对应的称为值(Value),将其称为Key-Value的键值对
因此模型会有两种:
1、纯Key模型
2、Key-Value模型
其中Map中存储的是Key-Value的键值对,Set中只存储了Key
二、Map的使用
由此可知:Map是一个接口类,该类没有继承Collection,该类中存储的是
1、Map.Entry
Map.Entry
方法 | 解释 |
K.getKey() | 返回entry中的key |
V.getValue() | 返回entry中的value |
V.setValue(V value) | 将键值对中的value替换为指定value |
注: Map.Entry
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的区别
Map底层结构 | TreeMap | HashMap |
底层结构 | 红黑树 | 哈希桶 |
插入/删除/查找时间复杂度 | O(log2^N) | O(1) |
是否有序 | 关于key有序 | 无序 |
线程安全 | 不安全 | 不安全 |
插入/删除/查找区别 | 需要进行元素比较 | 通过哈希函数计算哈希地址 |
比较与重写 | key必须能够比较,否则会抛出ClassCastException异常 | 自定义类型需要重写equals和hashCode方法 |
应用场景 | 需要key有序场景下 | key是否有序不关心,需要更高的时间性能 |
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获取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
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
keySet = treeMap.keySet(); - System.out.println(keySet);
- //获取所有的value
- Collection
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
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的区别
Set底层结构 | TreeSet | HashSet |
底层结构 | 红黑树 | 哈希桶 |
插入/删除/查找时间复杂度 | O(log2^N) | O(1) |
是否有序 | 关于key有序 | 不一定有序 |
线程安全 | 不安全 | 不安全 |
插入/删除/查找区别 | 按照红黑树的特性来进行插入和删除 | 先计算key的哈希地址,然后进行插入和删除 |
比较与重写 | key必须能够比较,否则会抛出ClassCastException异常 | 自定义类型需要重写equals和hashCode方法 |
应用场景 | 需要key有序场景下 | key是否有序不关心,需要更高的时间性能 |
三、搜索树
二叉搜索树又被称为二叉排序树,它或者是一颗空树,或者是具有以下性质的二叉树
若它的左子树不为空,那么左子树上所有的节点的值都小于根节点的值
若它的右子树不为空,那么右子树上所有的节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树
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);
- }
- }
- }