开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【数据结构与算法】| Map和Set -> 正文阅读

[数据结构与算法]【数据结构与算法】| Map和Set

一、二叉搜索树
二、Map的使用
三、Set的使用
四、哈希表

一、二叉搜索树

这里讲的是最简单的搜索树。

搜索树的概念很简单，就是根节点的左边节点的值比根节点小，右边节点比根节点大，同时每一棵子树都是如此。

示意图：

1.搜索树的查找

思路：

跟链表的查找有点像，首先先设置一个节点cur，判断查找的值是否大于当前cur的值，大于cur的值，那么cur = cur.right，否则如果小于cur的值，cur = cur.left ,不然就是返回当前节点的值。

代码：

public TreeNode search(int key) {
    if(root == null) {
        return null;
    }
    TreeNode cur = root;
    while(cur != null) {
        if(cur.key > key) {
            cur = cur.left;
        }
        else if(cur.key < key) {
            cur = cur.right;
        }
        else {
            return cur;
        }
    }
    return null;
}

2.搜索树的插入

思路：

插入节点就相当于在找到一个合适的节点后，插入到这个节点的左边或者右边。也就是说插入节点，这个节点其实也就是叶子节点。创建一个节点cur来查找合适的位置，当cur为空的时候，那么cur的上一个节点就是合适的节点。所以我们还要创建一个parent来保存cur的上一个节点，来确保cur为空的时候，还能找到上一个节点。

public boolean insert(int key) {
    TreeNode node = new TreeNode(key);
    if(root == null) {
        root = node;
    }
    TreeNode cur = root;
    TreeNode parent = null;
    while (cur != null) {
        if(cur.key > key) {
            parent = cur;
            cur = cur.left;
        }
        else if (cur.key < key) {
            parent = cur;
            cur = cur.right;
        }
        else {
            return false;
        }
    }
    if(parent.key > key) {
        parent.left = node;
    }
    else{
        parent.right = node;
    }
    return true;
}

3.搜索树的删除

删除比较复杂，具体分7种情况。

现在假设我们通过查找，cur就是我们要删除的节点。

一、cur.left为空的时候

1.cur.left为空的时候，而cur 又为 root 的时候，直接root = root.right即可。

示意图：

2.cur.left为空的时候，创建一个节点来保存cur的上一个节点，假设这个保存的节点是parent。如果cur.right 不为空，那么下一步操作就是parent .right = cur.right即可。

3.cur.left为空的时候，创建一个节点来保存cur的上一个节点，假设这个保存的节点是parent。如果cur.right 为空，那么下一步操作就是parent .right = null即可。

二、cur.right 为空的时候

1.cur.right 为空的时候，并且cur == root 的时候，那么直接root = root.left 即可。

2.cur.right为空的时候，创建一个节点来保存cur的上一个节点，假设这个保存的节点是parent。如果cur.right 为空，那么下一步操作就是parent .right = cur.right即可。

3.2.cur.right为空的时候，创建一个节点来保存cur的上一个节点，假设这个保存的节点是parent。如果cur.left 为空，那么下一步操作就是parent .right = null即可。

三、cur.right 不为空和cur.left 不为空的情况

假如我要删除85这个节点，思路如下：

要么在85这个节点的左边找到最大值，要么在85这个节点的右边找到最小值，然后找到的这个值替换掉85这个节点的值。

技巧：利用了最大或者最小值的节点只能是叶子节点的特性。

我以在右边找到最小值为例画图。

85的右边的最小值就是87，然后85的节点的值替换成87，然后87节点置空即可。

具体代码：

public void remove(int key) {
    TreeNode cur = root;
    TreeNode parent = null;
    while (cur != null) {
        if(cur.val < key) {
            parent = cur;
            cur = cur.right;
        }else if(cur.val > key) {
            parent = cur;
            cur = cur.left;
        }else {
            //找到了 就要开始删除了
            removeNode(cur,parent);
            return;
        }
    }
}
private void removeNode(TreeNode cur, TreeNode parent) {
    if(cur.left == null) {
        if(cur == root) {
            root = root.right;
        }else if(cur == parent.left) {
            parent.left = cur.right;
        }else {
            parent.right = cur.right;
        }
    }else if(cur.right == null) {
        if(cur == root) {
            root = root.left;
        }else if(cur == parent.left){
            parent.left = cur.left;
        }else {
            parent.right = cur.left;
        }
    }else {
        TreeNode targetParent = cur;
        TreeNode target = cur.right;
        while (target.left != null) {
            targetParent = target;
            target = target.left;
        }
        cur.val = target.val;
        //分两种情况
        if(targetParent.left == target) {
            targetParent.left = target.right;
        }else {
            targetParent.right = target.right;
        }
    }
}

二、Map的使用

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class test {
    public static void main(String[] args) {
        Map<String,Integer> map = new TreeMap<>();
        Map<String,Integer> map2 = new HashMap<>();
    }
}

Map是一个接口，尖括号里面是数据的引用类型。上面的代码就是Map的具体使用。

Map想要实例化，只能实例化TreeMap或者HashMap.

如果实例化TreeMap，底层是一棵红黑树。

如果实例化HashMap，底层是哈希表。

按照我自身的理解，我认为Map就是一个容器，存储的模式是键值对的模式。就好比一个人总会有外号的，当有人叫这个外号的时候，你总会有回应。例如，悟空是斗战胜佛，猪八戒是净坛使者。。。。

1.Map的增删查改

1.增（添加元素）

public static void main(String[] args) {
    Map<String,Integer> map = new TreeMap<>();
    map.put("hello",8);
    map.put("strange",10);
    map.put("apple",3);
    map.put("banana",4);
    System.out.println(map);
    //Map<String,Integer> map2 = new HashMap<>();
}

注意观察，我添加元素的时候，不是按照我代码的顺序打印出来的，是排列过的顺序打印出来的。

原因是TreeMap 里面的元素必须是课比较的，否则就不能添加，另外null也不能添加。所以添加自定义类型要实现Comparable接口或者传一个比较器。

public static void main(String[] args) {
    Map<students,Integer> map2 = new TreeMap<>();
    map2.put(new students(),1);
}

public static void main(String[] args) {

    Map<students,Integer> map2 = new TreeMap<>();
    map2.put(null,1);
    
}

2.删（删除元素）

public static void main(String[] args) {
    Map<String,Integer> map = new TreeMap<>();
    map.put("hello",8);
    map.put("strange",10);
    map.put("apple",3);
    map.put("banana",4);
    System.out.println(map);
    map.remove("hello");
    map.remove("apple",3);
    System.out.println(map);

}

利用remove方法可以删除Map中的元素，有两种参数形式，一种只传key值，第二种是传key值和value值。

3.查（查找元素）

public static void main(String[] args) {
    Map<String,Integer> map = new TreeMap<>();
    map.put("hello",8);
    map.put("strange",10);
    map.put("apple",3);
    map.put("banana",4);
    System.out.println(map);
    System.out.println(map.get("apple"));
    System.out.println(map.get("banana"));
}

通过查找key值可以得出key所对应的的value值。

4.改（修改元素）

Map中的元素的key是不可以重复，但是value可以，因此你新增一个相同的元素，当key相同时，会直接覆盖，value会变成新的value。

public static void main(String[] args) {
    Map<String,Integer> map = new TreeMap<>();
    map.put("hello",8);
    map.put("strange",10);
    map.put("apple",3);
    map.put("banana",4);
    System.out.println(map);
    map.put("apple",13);
    map.put("banana",14);
    System.out.println(map);
}

2.Map 的keySet（）

public static void main(String[] args) {
    Map<String,Integer> map = new TreeMap<>();
    map.put("hello",8);
    map.put("strange",10);
    map.put("apple",3);
    map.put("banana",4);
    System.out.println(map);
    Set<String> set = map.keySet();
    System.out.println(set);
}

这个方法就是把Map中的元素的key值都放到一个集合中去。

3.Map.entrySet()

public static void main(String[] args) {
    Map<String,Integer> map = new TreeMap<>();
    map.put("hello",8);
    map.put("strange",10);
    map.put("apple",3);
    map.put("banana",4);
    System.out.println(map);
    Set<String> set = map.keySet();
    System.out.println(set);
    Set<Map.Entry<String,Integer>> set2= map.entrySet();
    for (Map.Entry<String,Integer> stringIntegerEntry: set2) {
        System.out.println(stringIntegerEntry);
    }
}

Set<Map.Entry<K, V>> entrySet() 这个方法是把Map中元素的键值对都一一打印出来。

Map还有一些方法就不再展示如何使用了，了解就行。

方法	解释
V get(Object key)	返回 key 对应的 value
V getOrDefault(Object key, V defaultValue)	返回 key 对应的 value，key 不存在，返回默认值
V put(K key, V value)	设置 key 对应的 value
V remove(Object key)	删除 key 对应的映射关系
Set keySet()	返回所有 key 的不重复集合
Collection values()	返回所有 value 的可重复集合
Set<Map.Entry<K, V>> entrySet()	返回所有的 key-value 映射关系
boolean containsKey(Object key)	判断是否包含 key
boolean containsValue(Object value)	判断是否包含 value

4.Map的小结

HashMap 和 TreeMap的各种方法都是一样的，只是底层不一样。

Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap
Map中存放键值对的Key是唯一的，value是可以重复的
Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。
Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。
Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行****重新插入。
TreeMap和HashMap的区别

Map底层结构	TreeMap	HashMap
底层结构	红黑树	哈希桶
插入/删除/查找时间复杂度	O(1)
是否有序	关于Key有序	无序
线程安全	不安全	不安全
插入/删除/查找区别	需要进行元素比较	通过哈希函数计算哈希地址
比较与覆写	key必须能够比较，否则会抛出 ClassCastException异常	自定义类型需要覆写equals和 hashCode方法
应用场景	需要Key有序场景下	Key是否有序不关心，需要更高的时间性能

三、Set的使用

set的使用同Map差不太多，这里就不再演示Set方法的使用了。需要注意的是Set的模式是纯key模型，也就是里面只有key值，没有value值。运用的场景一般是在去重的情况下。

方法	解释
boolean add(E e)	添加元素，但重复元素不会被添加成功
void clear()	清空集合
boolean contains(Object o)	判断 o 是否在集合中
Iterator iterator()	返回迭代器
boolean remove(Object o)	删除集合中的 o
int size()	返回set中元素的个数
boolean isEmpty()	检测set是否为空，空返回true，否则返回false
Object[] toArray()	将set中的元素转换为数组返回
boolean containsAll(Collection<?> c)	集合c中的元素是否在set中全部存在，是返回true，否则返回 false
boolean addAll(Collection<? extends E> c)	将集合c中的元素添加到set中，可以达到去重的效果