// 查找
    public boolean search(int key){
        TreeNode cur = root;
        while(cur != null){
            if(cur.val > key){
                cur = cur.left;
            }else if(cur.val < key){
                cur = cur.right;
            }else{
                return true;
            }
        }
        return false;
    }

// 插入
    public boolean insert(int key){
        TreeNode node = new TreeNode(key);
        TreeNode parent = null;
        if(root == null){
            root = node;
            return true;
        }
        TreeNode cur = root;
        while(cur != null){
            if(cur.val < key){
                parent = cur;
                cur = cur.right;
            }else if(cur.val > key){
                parent = cur;
                cur = cur.left;
            }else{
                // 在二叉搜索樹中只能不能有相同的數(shù)字,比如5,有一個5就可以了,只要有這個數(shù)就可以了
                return false;
            }
        }
        if(parent.val < key){
            parent.right= node;
        }else{
            parent.left = node;
        }
        return true;
    }

// 刪除
    private void removeNode(TreeNode cur, TreeNode parent) {
        if(cur.left == null){
            // 要刪除的是根節(jié)點(diǎn)
            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{
            // cur.left != null && cur.right != null
            TreeNode parentTarget = cur;
            TreeNode target = cur.right;
            // 在右樹中找最小值
            while(target.left != null){
                parentTarget = target;
                target = target.left;
            }
            // 直到找到右樹中的最左邊的樹
            cur.val = target.val;
            // 刪除target
            if(parentTarget.left == target) {
                parentTarget.left = target.right;
            }else{
                // parentTarget.right == target
                parentTarget.right = target.right;
            }
        }
    }

 Map<String,Integer> map = new TreeMap<>();// 底層是紅黑樹,查找的時間復(fù)雜度O(N*logN)
 Map<String,Integer> map1 = new HashMap<>();// 底層是哈希表,查找的時間復(fù)雜度O(1)
 // 哈希表 = 數(shù)組 + 鏈表 + 紅黑樹

public static void main(String[] args) {
        Map<String,Integer> map = new TreeMap<>();// 底層是紅黑樹,查找的時間復(fù)雜度O(N*logN)
        // 插入元素
        map.put("push",3);// push出現(xiàn)了3次
        // 獲取元素,給定一個key值可以獲取它的value值
        Integer val = map.get("push");
        Integer val1 = map.get("aaa");// null
        // 獲取val值,如果沒有這個值,返回一個默認(rèn)值
        Integer val2 = map.getOrDefault("bbb",99999);
        System.out.println(val);
        // 刪除key值
        // map.remove("push");
        // 把所有的key放入一個集合中
        Set<String> set = map.keySet();
        System.out.println(set);
        // 獲取values中的所有值
        ArrayList<Integer> value = new ArrayList(map.values());
        System.out.println(value);
        // 把Map.Entry<String,Integer>當(dāng)做Set中的一個節(jié)點(diǎn)
        // map.entrySet()用于獲取這種節(jié)點(diǎn)
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        for(Map.Entry<String,Integer> entry : entrySet){
            System.out.println("key: " + entry.getKey() + " value: " + entry.getValue());
        }
        // boolean map.containsKey("push"); 判斷是否含有key
        // boolean map.containsValue(3); 判斷是否含有value
        Map<String,Integer> map1 = new HashMap<>();// 底層是哈希表,查找的時間復(fù)雜度O(1)
        // 哈希表 = 數(shù)組 + 鏈表 + 紅黑樹
    }

public static void main(String[] args) {
        Set<String> set = new TreeSet<>();
        set.add("push");
        set.add("hello");
        set.add("world");
        // set是無序的
        System.out.println(set);
        Iterator<String> it = set.iterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }
    }

package Demo1;
import java.util.Arrays;
public class HashBuck {
    // 鏈表數(shù)組,數(shù)組中的每一個元素都時鏈表的頭結(jié)點(diǎn)
    public class Node{
        public int key;
        public int val;
        public Node next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    public Node[] array;
    public int usedSize;
    public static final float DEFAULT_LOAD_FACTOR = 0.75f;
    public HashBuck(){
        array = new Node[10];
    }
    public void put(int key,int value){
        int index = key % array.length;
        // 遍歷index下標(biāo)的鏈表 是否存在key 存在就更新value 不存在就頭插這個節(jié)點(diǎn)
        Node node = new Node(key,value);
        // 該鏈表的頭結(jié)點(diǎn)
        Node cur = array[index];
        while(cur != null){
            if(cur.key == key){
                // 如果插入的這個key相同就替換這個key
                cur.val = value;
                return;
            }
            cur = cur.next;
        }
        // 沒有找到這個節(jié)點(diǎn)就頭插
        node.next = array[index];
        array[index] = node;
        usedSize++;
        // 負(fù)載因子大于閾值
        if(doLoadFactor() > DEFAULT_LOAD_FACTOR){
            // 擴(kuò)容
            // array = Arrays.copyOf(array,2*array.length);
            resize();
        }
    }
    private void resize(){
        // 建一個新的數(shù)組
        Node[] newArray = new Node[2*array.length];
        for(int i = 0;i < array.length;i++){
            Node cur = array[i];
            while(cur != null){
                Node tmp = cur.next;
                // 每次都要算新數(shù)組的下標(biāo)因?yàn)槭且粋€鏈表有很多個節(jié)點(diǎn)
                int newIndex = cur.key % newArray.length;
                // 頭插法
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;
                cur = tmp;
            }
        }
        array = newArray;
    }
    // 計(jì)算負(fù)載因子
    private float doLoadFactor(){
        return usedSize * 1.0f / array.length;
    }
    // 獲取對應(yīng)key的value值
    public int get(int key){
        int index = key % array.length;
        Node cur = array[index];
        while(cur != null){
            if(cur.key == key){
                // 如果插入的這個key相同就替換這個key
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }
}

public static void main(String[] args) {
        HashMap<String,Integer> hashMap = new HashMap<>();
        hashMap.put("hello",2);
        hashMap.put("abcde",10);
        hashMap.put("abc",11);
        Integer val = hashMap.get("hello");
        System.out.println(val);
        // 遍歷map
        System.out.println(hashMap);
        for(Map.Entry<String,Integer> entry : hashMap.entrySet()){
            System.out.println("key:" + entry.getKey() + " value:" + entry.getValue());
        }
        // Map不支持迭代器遍歷,Set支持迭代器遍歷
        // 可以將Map轉(zhuǎn)化為Set進(jìn)行迭代器遍歷
        HashMap<Student,Integer> hashMap1 = new HashMap<>();
        hashMap1.put(new Student(),2);
        hashMap1.put(new Student(),2);
        hashMap1.put(null,2);
        // TreeMap<Student,Integer> hashMap2 = new TreeMap<>();
        // hashMap2.put(new Student(),3);
        // hashMap2.put(new Student(),3);
        // Sutdent不能進(jìn)行比較
        // set可以去重,Set的底層是HashMap
        // 每次存儲元素的時候,默認(rèn)的value都是一個Object對象
        HashSet<String> set = new HashSet<>();
        set.add("hello");
        set.add("world");
        set.add("hello");
        System.out.println(set);
    }

public static void main(String[] args) {
        int[] array = {1,1,2,2,3,3};
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < array.length;i++){
            if(!map.containsKey(array[i])){
                map.put(array[i],1);
            }else{
                int k = map.get(array[i]);
                k++;
                map.put(array[i],k);
            }
        }
        System.out.println(map);
    }

class Solution {
   public List<String> topKFrequent(String[] words, int k) {
        // 1. 統(tǒng)計(jì)單詞出現(xiàn)的次數(shù)
        Map<String,Integer> map = new HashMap<>();
        for(String s : words){
            if(!map.containsKey(s)){
                map.put(s,1);
            }else{
                int val = map.get(s);
                map.put(s,val+1);
            }
        }
        // 2. 把單詞和出現(xiàn)的次數(shù)當(dāng)做一個整體放入小根堆中
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(
                new Comparator<Map.Entry<String,Integer>>(){
        public int compare(Map.Entry<String,Integer> o1,Map.Entry<String,Integer> o2){
            // 放元素的時候,如果頻率相同,我們轉(zhuǎn)變?yōu)榇蟾?-> 按照單詞的字典序進(jìn)行排序
            if(o1.getValue().compareTo(o2.getValue()) == 0){
                return o2.getKey().compareTo(o1.getKey());
            }
            return o1.getValue().compareTo(o2.getValue());
        }
        });
        for(Map.Entry<String,Integer> entry : map.entrySet()){
            if(minHeap.size() < k){
                // 沒有放滿小根堆
                minHeap.add(entry);
            }else{
                // 放滿了和堆頂元素比較大小
                // 如果比堆頂元素還大,就入堆
                int v = minHeap.peek().getValue();
                if(v < entry.getValue()){
                    minHeap.poll();
                    minHeap.offer(entry);
                }else{
                    // 出現(xiàn)頻率相同,比較字典序大小
                    if(v == entry.getValue()){
                        if(minHeap.peek().getKey().compareTo(entry.getKey()) > 0){
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }
        // 2 3 4 -> 4 3 2
        List<String> arr = new ArrayList<>();
        for(int i = 0;i < k;i++){
            Map.Entry<String,Integer> top = minHeap.poll();
            arr.add(top.getKey());
        }
        // 逆置
        Collections.reverse(arr);
        return arr;
    }
}