初识数据结构——Map和Set：哈希表与二叉搜索树的魔法对决

package Tree;

//表示树的节点
class Node {
    public int key;
    public Node left;
    public Node right;
    public Node(int key) {
        this.key = key;
    }

    @Override
    public String toString() {
        return "Node{" +
                "key=" + key +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}

public class BinarySearchTree {
   private Node root = null;


   //把新的元素插入到树中
   public void insert(int key) {
        //如果当前是空树，那就直接用root指向新节点即可
       Node newNode = new Node(key);
       if (root == null) {
           root = newNode;
       }
       // 如果是普通的树，需要找到哦插入位置，再去进行插入
       //cur用来找待插入元素的位置
       //parent记录cur的父元素
       Node cur = root;
       Node parent = null;
       while (cur != null) {
           if(key<cur.key) {
               //往左找
               parent = cur;
               cur = cur.left;

           }else if(key>cur.key) {
               //往右找
               parent = cur;
               cur = cur.right;

           }else {
               //对于相等的情况，存在不同的解决方式
               //当前不允许重复key存在，并且是Set只保存key，直接return
               return;
           }
       }
       //通过上述循环最终得到的结果就是cur为空
       //此时的parent就是叶子节点，也就是新插入元素的父亲，此时就是要把newNode插入到parent的子节点上
       //新节点，应该在parent的左子树还是右子树呢??直接比较大小
       if (key> parent.key){
           parent.right = newNode;
       }else {
           parent.left = newNode;
       }
   }

   public void remove(int key) {
       if (root == null) {
           return;
       }
       //查找要删除节点的位置，记录其父节点
       Node cur = root;
       Node parent = null;
       while (cur != null) {
           if(key<cur.key) {
               parent = cur;
               cur = cur.left;
           }else if(key>cur.key) {
               parent = cur;
               cur = cur.right;
           }else {
               //找到了
               removeNode(parent, cur);
               return;
           }
       }

   }


   private void removeNode(Node parent, Node cur) {
       //具体删除节点要考虑四种情况
       //1.没有子树
       if(cur.right == null && cur.left == null) {
           //1.1如果cur就是root，需要对root进行调整
           if(cur == root) {
               //说明整棵树只有root一个节点，直接把root设置为空
               root = null;
           }
           //1.2如果cur不是root，同时cur是parent的左子树
           if (cur == parent.left) {
               parent.left = null;
               return;
           }
           //1.3如果cur不是root，同时cur是parent的右子树
            if (cur == parent.right) {
                parent.right = null;
                return;
            }
            //稳妥起见加个return
           return;
       }
       //2.只有左子树
       if(cur.left != null && cur.right == null) {
            //2.1cur为root
           if(cur == root){
               root = cur.left;
               return;
           }
           //2.2cur不为root，且cur是parent的左子树
           if (cur == parent.left) {
               parent.left = cur.left;
               return;
           }
           //2.3cur不为root，且cur是parent的右子树
            if (cur == parent.right) {
                parent.right = cur.left;
                return;
            }

       }

       //3.只有右子树
       if(cur.left == null && cur.right != null) {
           //3.1只有root
           if(cur == root){
               root = cur.right;
               return;
           }
           //3.2cur不是root，且cur是parent的左子树
           if (cur == parent.left) {
               parent.left = cur.right;
               return;
           }
           //3.3cur不是root，且cur是parent的右子树
           if (cur == parent.right) {
               parent.right = cur.right;
               return;
           }

       }
       //4.左右都有子树
       if(cur.left != null && cur.right != null) {
           // 这种情况下，不需要考虑 cur 是不是 root的情况，并没有真正的删除 cur指向的节点，即使 cur 是 root，也无需修改 root 的指向
           //因为实际删除的是“替罪羊节点”
           //4.1首先需要找到右子树中的最小值 =>替罪羊,
           //后续要删除替罪羊，也顺便把替罪羊的父亲，记录一下.
           Node goat = cur.right;
           Node goatParent= cur;
           while (goat.left != null) {
               goatParent = goat;
               goat = goat.left;
           }
           //循环结束后。goat指向的就是cur右子树的最左侧元素
           //4.2移花接木，把替罪羊节点的值复制到cur节点中
           cur.key = goat.key;
           //4.3真正删除goat节点，因为goat是没有左子树的，让goatParent直接连上goat的右子树即可
           // 即使goat的右子树也是空也不影响
            if(goat == goatParent.left){
                goatParent.left = goat.right;
            }else {
                goatParent.right = goat.right;
            }
       }
   }


   //查找key是否在树中，如果存在则返回对应节点位置，如果不存在则返回null
    private Node find(int key) {
       if (root == null) {
           return null;
       }
       Node cur = root;
       while (cur != null) {
           if(key<cur.key) {
               cur = cur.left;
           }
           else if(key>cur.key) {
               cur = cur.right;
           }else {
               //相等，找到了
               return cur;
           }
       }
       return null;
    }


   //先序遍历
   private static void preOrder(Node root) {
       if (root == null) {
           return;
       }

       System.out.print(root.key + " ");
       preOrder(root.left);
       preOrder(root.right);
   }

   //中序遍历
    private static void inOrder(Node root) {
        if (root == null) {
            return;
        }
       inOrder(root.left);
       System.out.print(root.key + " ");
        inOrder(root.right);
    }



   public void print(){
       //先打印先序遍历
       System.out.println("先序遍历结果：");
       preOrder(root);
       System.out.println();
       //在打印中序遍历
       System.out.println("中序遍历结果：");
       inOrder(root);
       //有了先序和中序就能够画出树的结构
   }


    public static void main(String[] args) {
       int[] arr = {1, 3, 2, 6, 5, 7, 8, 9, 10, 0};

       //BinarySearchTree也总被缩写成BST
        BinarySearchTree tree = new BinarySearchTree();
        //循环插入
        for(int key: arr){
            tree.insert(key);
        }
        tree.print();
        System.out.println();
        System.out.println(tree.find(7));
    }
}

Map<String, String> heroNicknames = new HashMap<>();
heroNicknames.put("林冲", "豹子头");
heroNicknames.put("李逵", "黑旋风");
heroNicknames.put("宋江", "及时雨");

// 获取外号
System.out.println(heroNicknames.get("林冲"));  // 输出：豹子头

// 遍历所有英雄
for (Map.Entry<String, String> entry : heroNicknames.entrySet()) {
    System.out.println(entry.getKey() + "的外号是：" + entry.getValue());
}

Set<String> fruitSet = new HashSet<>();
fruitSet.add("苹果");
fruitSet.add("香蕉");
fruitSet.add("橙子");
fruitSet.add("苹果");  // 这个不会被添加进去

System.out.println(fruitSet.contains("香蕉"));  // 输出：true
System.out.println(fruitSet.size());          // 输出：3

int hashCode = "魔法".hashCode();  // 返回一个魔法数字

public class MyHashMap {
    //利用链表去解决哈希冲突，利用一个静态内部类Node来表示链表节点
    static class Node{
        public int key;
        public int value;
        public Node next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    //一般来说这个数组的长度的设定也是有技巧的
    // 一个典型的做法是选择素数作为数组的长度，减少哈希冲突的概率
    private Node[] table = new Node[1001];
    //记录有效元素的个数
    private int size;
    //设定哈希函数，把key转成数组下标
    private int hashCode(int key){
        return key % table.length;
    }
    //哈希表的核心操作
    //插入/修改操作
    public void put(int key, int value) {
        //1.根据key，计算出下标位置
        int index = hashCode(key);
        //2.遍历链表，看一下key是否在链表中已经存在
        Node head = table[index];
        for(Node cur = head; cur != null; cur = cur.next){
            //如果已经存在，就修改对应的value值
            if(cur.key == key){
                cur.value = value;
                return;
            }
        }
        //3.如果不存在直接插入，按照头插方式插入
        Node newNode = new Node(key, value);
        newNode.next = head;
        table[index] = newNode;
        //4.插入完成后size要自增
        size++;
        //5.扩容（考虑负载因子）
        if((double)size/table.length > 0.75){
            resize();
        }
    }
    //扩容
    private void resize(){
        //创建一个更大的数组，直接遍1.5倍，更好的方法找一个刚好大于原来size的2倍多一点的素数
        Node[] newTable = new Node[table.length + table.length>>1];
        //搬运，把原来table中的元素搬运过来
        for(int i = 0; i < table.length; i++){
            for (Node cur = table[i]; cur != null; cur = cur.next){
                //根据这个节点，创建新节点，插入到新数组中
                Node newNode = new Node(cur.key, cur.value);
                int newIndex =  cur.key % newTable.length;
                //把新节点头插到新的链表中
                newNode.next = newTable[newIndex];
                newTable[newIndex] = newNode;
            }
        }
        //替换操作
        table = newTable;
    }

    //根据键获取值
    public Integer get(int key) {
        //1.根据key计算出下标
        int index = hashCode(key);
        //2.在对应的链表上找到该key的值
        for(Node cur = table[index]; cur != null; cur = cur.next){
            if(cur.key == key){
                return cur.value;
            }
        }
        //3.通过上述循环都没有找到就返回null
        return null;
    }
    //删除键值对，本质上就是链表删除
    public void remove(int key) {
        //1.根据key找到下标
        int index  = hashCode(key);
        //2.先考虑链表为空的情况，直接返回，不需要删除
        if(table[index] == null) return;
        //考虑是否为头节点情况
        if(table[index].key == key){
            table[index] = table[index].next;
            size--;
            return;
        }
        //再考虑普通情况
        Node prev = table[index];
        Node cur = prev.next;
        while (cur != null) {
            if(cur.key == key){
                prev.next = cur.next;
                size--;
                return;
            }
            prev = cur;
            cur = cur.next;
        }
    }
}

public int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

public int numJewelsInStones(String J, String S) {
    Set<Character> jewels = new HashSet<>();
    for (char c : J.toCharArray()) {
        jewels.add(c);
    }
    
    int count = 0;
    for (char c : S.toCharArray()) {
        if (jewels.contains(c)) count++;
    }
    return count;
}