数据结构——Map和Set

1. 从根节点开始，比较插入值与当前节点的值。

2. 根据比较结果，决定向左子树或右子树移动。

3. 重复上述过程，直到找到一个空位置（即当前节点的左子节点或右子节点为空）。

4. 将新节点插入到该空位置。

• 找到右子树的最小节点（或左子树的最大节点）。

• 用最小节点的值替换被删除节点的值。

• 删除右子树的最小节点。

public class BinarySearchTree {
//创建内部类，作为节点
    static class Node{
        public int val;
        public Node left;
        public Node right;
        //构造方法，初始化节点
        public Node(int val){
            this.val = val;
        }
    }
    public Node root;
    //查找
    public boolean search(int data){
        if(root==null){
            return false;
        }
        Node cur = root;
        while(cur!=null){
            //如果大于data，右边寻找
            if(cur.val<data){
                cur = cur.right;
            }else if(cur.val>data){//小于data，左边寻找
                cur = cur.left;
            }else {
                return true;
            }
        }
        return false;
    }

    //插入
    public void insert(int data){
        Node node = new Node(data);
        //如果根节点为空
        if(root==null){
            root = node;//根节点为新节点
            return;
        }
        Node cur = root;
        Node parent = null;
        while(cur!=null){
            parent = cur;//存放父节点
            //向右子树移动
            if(cur.val<data){
                cur = cur.right;
            }else if(cur.val>data){//向左子树移动
                cur = cur.left;
            }else{
                return;//如果val已经存在，直接退出
            }
        }
        //将新节点插入到末尾空节点
        if(parent.val<data){
            parent.right = node;
        }else if(parent.val > data){
            parent.left = node;
        }
    }

    //删除
    public boolean remove(int data){
        if(root==null){
            return false;
        }
        Node cur = root;
        Node parent = null;
        //查找data
        while(cur!=null){
            if(cur.val<data){
                parent = cur;
                cur = cur.right;
            }else if(cur.val>data){
                parent = cur;
                cur = cur.left;
            }else {
                //删除
                delete(parent,cur);
                return true;
            }
        }
        return false;
    }
    private void delete(Node parent,Node cur){
        //如果cur左节点为空
        if(cur.left==null){
            //如果cur为根节点
            if(cur==root){
                root = cur.right;
                root.left=null;
            }
            //如果cur在左边
            if(parent.left==cur){
                parent.left = cur.right;
            }
            //如果cur在右边
            if(parent.right==cur){
                parent.right=cur.right;
            }
        }else if(cur.right==null){//cur右节点为空
            if(cur==root){
                root = cur.left;
                root.right=null;
            }
            if(parent.left==cur) {//在左边
                parent.left = cur.left;
            }
            if(parent.right==cur){//在右边
                parent.right = cur.right;
            }
        }else{//左右节点均不为空
            leftChild(parent,cur);
            //rightChild(parent,cur);
        }
    }
    //1.找到cur左节点的最右边节点
    private void leftChild(Node parent,Node cur){
        parent = cur;
        Node child = cur.left;
        while(child.right!=null){
            parent = child;
            child = child.right;
        }
        //与cur交换，再删除交换后的节点
        cur.val = child.val;
        //如果cur左节点没有右孩子
        if(parent.left==child){
            parent.left = child.left;
        }else{
            parent.right = child.left;
        }
    }
    //2.找到cur右节点的最左边节点
    private void rightChild(Node parent,Node cur){
        parent = cur;
        Node child = cur.right;
        //cur右节点的最左边节点
        while(child.left!=null){
            parent = child;
            child = child.left;
        }
        //与cur交换，再删除交换后的节点
        cur.val = child.val;
        //如果cur右节点没有左孩子
        if(parent.right==child){
            parent.right = child.right;
        }else{
            parent.left = child.right;
        }
    }
}

5. 性能分析

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

2. Map 的常⽤⽅法

import java.util.Collection;
import java.util.TreeMap;
import java.util.Map;
import java.util.Set;

public class TestMap {
    public static void main(String[] args){
        Map<String,Integer> map = new TreeMap<>();
        TreeMap<String,Integer> treeMap = new TreeMap<>();//TreeMap重写了接口Map的所有方法
        map.put("the",3);
        map.put("early",5);
        map.put("bird",4);
        map.put("catches",7);
        map.put("the",6);//key已存在，可以改变key对应的value值
        map.put("worm",4);
        System.out.println(map.size());//返回此地图中键值映射的数量
        System.out.println(map.get("the"));//key存在，返回key对应的value
        System.out.println(map.get("word"));//key不存在，返回null
        System.out.println(map.getOrDefault("bird",0));//key存在，返回key对应的value
        System.out.println(map.getOrDefault("time",0));//key不存在，返回自定义value
        System.out.println(map.remove("the"));//删除key对应的映射关系，并返回key对应的value值
        System.out.println(map.remove("the"));//key不存在则返回null
        Set<String> keyset = map.keySet();//将map中所有的key放入keyset中
        System.out.println(keyset);
        for(String s : map.keySet()){
            System.out.print(s+" ");
        }
        System.out.println();
        Collection<Integer> con =map.values();//将map中所有的value放入con中
        System.out.println(con);
        for(Integer cot:map.values()){
            System.out.print(cot+" ");
        }
        System.out.println();
        //将map中的所有映射关系放入entry中
        Set<Map.Entry<String,Integer>> entry = map.entrySet();
        System.out.println(entry);
        for(Map.Entry<String,Integer> entry1:map.entrySet()){
            System.out.println("key: "+entry1.getKey()+" ; value: "+entry1.getValue());
        }
    }
}

1. set 的常用方法

import java.util.*;

public class TestSet {
    public static void main(String[] args) {
        Set<String> set = new TreeSet<>();
        TreeSet<String> treeSet = new TreeSet<>();//TreeSet重写了接口set的所有方法
        //为set添加元素
        System.out.println(set.add("the"));
        System.out.println(set.add("early"));
        System.out.println(set.add("bird"));
        System.out.println(set.add("catches"));
        System.out.println(set.add("the"));//key已存在，不添加
        System.out.println(set.add("worm"));
        System.out.println(set.size());//返回set中元素的个数
        System.out.println(set.isEmpty());//判断set是否为空，不为空返回false
        //判断元素是否存在
        System.out.println(set.contains("the"));//存在，true
        System.out.println(set.contains("world"));//不存在，false
        //删除set中指定的元素
        System.out.println(set.remove("the"));//存在要删除的元素，删除并返回true
        System.out.println(set.remove("the"));//不存在要删除的元素，返回false
        //创建顺序表，作为集合使用
        ArrayList<String> arrayList = new ArrayList<>();
        arrayList.add("bird");
        arrayList.add("worm");
        判断set是否包含顺序表中的所有元素
        System.out.println(set.containsAll(arrayList));//包含，true
        arrayList.add("the");
        System.out.println(set.containsAll(arrayList));//不包含，false
        //将set中的元素全部转换为数组
        String[] s = set.toArray(new String[0]);//原代码直接使用 set.toArray() 会返回 Object[] 而不是 String[]
        System.out.print(Arrays.toString(s));//打印数组
        System.out.println();
        System.out.println(set.addAll(arrayList));//将集合arraylist中的元素添加到set中,重复元素不添加
        //迭代器
        Iterator<String> it = set.iterator();
        while(it.hasNext()){
            System.out.print(it.next()+" ");
        }
        System.out.println();
        set.clear();//清空集合
        System.out.println(set.isEmpty());//set为空，返回true
    }
}

2. 冲突

1. 概念

-哈希函数设计

引起哈希冲突的⼀个原因可能是：哈希函数设计不够合理。哈希函数设计原则：

• 哈希函数的定义域必须包括需要存储的全部关键码，⽽如果散列表允许有m个地址时，其值域必须在0到m-1之间

• 哈希函数计算出来的地址能均匀分布在整个空间中

• 哈希函数应该⽐较简单

3. 常⻅哈希函数

1. 线性探测

2. ⼆次探测

3. 总结

7. 和 java 类集的关系