Map和Set

 public class BinarySearchTree {
    public static class Node {
        int key;
        Node left;
        Node right;
 
        public Node(int key) {
            this.key = key;
        }
    }
 
    private Node root = null;
 
    /**
     * 在搜索树中查找 key，如果找到，返回 key 所在的结点，否则返回 null
     * @param key
     * @return
     */
    public Node search(int key) {
        Node cur = root;
        while (cur != null) {
            if (key == cur.key) {
                return cur;
            } else if (key < cur.key) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
 
        return null;
    }
 
    /**
     * 插入
     * @param key
     * @return true 表示插入成功, false 表示插入失败
     */
    public boolean insert(int key) {
        if (root == null) {
            root = new Node(key);
            return true;
        }
 
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if (key == cur.key) {
                return false;
            } else if (key < cur.key) {
                parent = cur;
                cur = cur.left;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }
 
        Node node = new Node(key);
        if (key < parent.key) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        return true;
    }
 
    /**
     * 删除成功返回 true，失败返回 false
     * @param key
     * @return
     */
    public boolean remove(int key) {
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if (key == cur.key) {
                break;
            } else if (key < cur.key) {
                parent = cur;
                cur = cur.left;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }
        
        // 该元素不在二叉搜索树中
        if(null == cur){
            return false;
        }
 
        /*
        根据cur的孩子是否存在分四种情况
        1. cur左右孩子均不存在
        2. cur只有左孩子
        3. cur只有右孩子
        4. cur左右孩子均存在
            看起来有四种情况，实际情况1可以与情况2或者3进行合并，只需要处理是那种情况即可
            除了情况4之外，其他情况可以直接删除
            情况4不能直接删除，需要在其子树中找一个替代节点进行删除
        */
     return true;
     }
 }

 import java.util.TreeMap;
 import java.util.Map;
 
    public static void TestMap(){
        Map<String, String> m = new TreeMap<>();
 
        // put(key, value):插入key-value的键值对
        // 如果key不存在，会将key-value的键值对插入到map中,返回null
        m.put("林冲", "豹子头");
        m.put("鲁智深", "花和尚");
        m.put("武松", "行者");
        m.put("宋江", "及时雨");
        String str = m.put("李逵", "黑旋风");
        System.out.println(m.size());
        System.out.println(m);
 
        // put(key,value): 注意key不能为空，但是value可以为空
        // key如果为空，会抛出空指针异常
        //m.put(null, "花名");
        str = m.put("无名", null);
        System.out.println(m.size());
 
        // put(key, value):
        // 如果key存在，会使用value替换原来key所对应的value，返回旧value
        str = m.put("李逵", "铁牛");
 
        // get(key): 返回key所对应的value
        // 如果key存在，返回key所对应的value
        // 如果key不存在，返回null
        System.out.println(m.get("鲁智深"));
        System.out.println(m.get("史进"));
 
        //GetOrDefault(): 如果key存在，返回与key所对应的value，如果key不存在，返回一个默认值
        System.out.println(m.getOrDefault("李逵", "铁牛"));
        System.out.println(m.getOrDefault("史进", "九纹龙"));
        System.out.println(m.size());
 
        //containKey(key)：检测key是否包含在Map中，时间复杂度：O(logN)
        // 按照红黑树的性质来进行查找
        // 找到返回true，否则返回false
        System.out.println(m.containsKey("林冲"));
        System.out.println(m.containsKey("史进"));
 
        // containValue(value): 检测value是否包含在Map中，时间复杂度: O(N)
        // 找到返回true，否则返回false
        System.out.println(m.containsValue("豹子头"));
        System.out.println(m.containsValue("九纹龙"));
 
 
        // 打印所有的key
        // keySet是将map中的key防止在Set中返回的
        for(String s : m.keySet()){
             System.out.print(s + " ");
         }
         System.out.println();

         // 打印所有的value
         // values()是将map中的value放在collect的一个集合中返回的
         for(String s : m.values()){
             System.out.print(s + " ");
         }
         System.out.println();

         // 打印所有的键值对
         // entrySet(): 将Map中的键值对放在Set中返回了
         for(Map.Entry<String, String> entry : m.entrySet()){
             System.out.println(entry.getKey() + "--->" + entry.getValue());
         }
         System.out.println();
     }

 import java.util.TreeSet;
 import java.util.Iterator;
 import java.util.Set;

 public static void TestSet(){
     Set<String> s = new TreeSet<>();

     // add(key): 如果key不存在，则插入，返回ture
     // 如果key存在，返回false
     boolean isIn = s.add("apple");
     s.add("orange");
     s.add("peach");
     s.add("banana");
     System.out.println(s.size());
     System.out.println(s);
     isIn = s.add("apple");

     // add(key): key如果是空，抛出空指针异常
     //s.add(null);
    
     // contains(key): 如果key存在，返回true，否则返回false
     System.out.println(s.contains("apple"));
     System.out.println(s.contains("watermelen"));

     // remove(key): key存在，删除成功返回true
     //              key不存在，删除失败返回false
     //              key为空，抛出空指针异常
     s.remove("apple");
     System.out.println(s);

     s.remove("watermelen");
     System.out.println(s);

     Iterator<String> it = s.iterator();
     while(it.hasNext()){
         System.out.print(it.next() + " ");
     }
     System.out.println();
 }

 // key-value 模型
 public class HashBucket {
     private static class Node {
         private int key;
         private int value;
         Node next;

         public Node(int key, int value) {
             this.key = key;
             this.value = value;
         }
     }
 
      private Node[]  array;
      private int size;   // 当前的数据个数
      private static final double LOAD_FACTOR = 0.75;
 
      public int put(int key, int value) {
          int index = key % array.length;
 
          // 在链表中查找 key 所在的结点
          // 如果找到了，更新
          // 所有结点都不是 key，插入一个新的结点
          for (Node cur = array[index]; cur != null; cur = cur.next) {
              if (key == cur.key) {
                  int oldValue = cur.value;
                  cur.value = value;
                  return oldValue;
              }
          }
          Node node = new Node(key, value);
          node.next = array[index];
          array[index] = node;
          size++;
 
          if (loadFactor() >= LOAD_FACTOR) {
              resize();
          }
 
          return -1;
      }
 
      private void resize() {
          Node[] newArray = new Node[array.length * 2];
          for (int i = 0; i < array.length; i++) {
              Node next;
              for (Node cur = array[i]; cur != null; cur = next) {
                  next = cur.next;
                  int index = cur.key % newArray.length;
                  cur.next = newArray[index];
                  newArray[index] = cur;
              }
          }
           array = newArray;
      }
 
      private double loadFactor() {
           return size * 1.0 / array.length;
      }
 
      public HashBucket() {
           array = new Node[8];
           size = 0;
      }

      public int get(int key) {
          int index = key % array.length;
          Node head = array[index];
          for (Node cur = head; cur != null; cur = cur.next) {
              if (key == cur.key) {
                  return cur.value;
              }
          }
          return -1;
      }
 }