public class HashBucket {
    static 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 = new Node[10];
    public int usedSize;
}

    // 默認(rèn)負(fù)載因子的限制值
    public static final double DEFAULT_LOAD_FACTOR = 0.75;

    public void push(int key, int val){
        int index = key % array.length;

        Node cur = array[index];
        // 找到有無(wú)該節(jié)點(diǎn)
        while(cur != null){
            if (cur.key == key){
                cur.val = val;  // 更新 value值
                return;
            }
            cur = cur.next;
        }

        // 沒(méi)有找到該節(jié)點(diǎn)，那么插入
        Node node = new Node(key,val);
        node.next = array[index];
        array[index] = node;
        usedSize++;
        if (doLoadFactor() >= DEFAULT_LOAD_FACTOR){
            resize();
        }
    }

    private double doLoadFactor(){  // 計(jì)算當(dāng)前的負(fù)載因子
        return usedSize*1.0 / array.length;  // 乘1.0的目的是將整型隱式轉(zhuǎn)換為浮點(diǎn)型
    }

    private void resize(){
        // 錯(cuò)誤寫(xiě)法，擴(kuò)容不僅僅是將容器放大容量，還應(yīng)該重新哈希
        //array = Arrays.copyOf(array,2*array.length);
        Node[] newArray = new Node[2*array.length];  // 存放到新的數(shù)組

        // 遍歷原來(lái)的數(shù)組，重新哈希
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur != null) {
                int newIndex = cur.key % newArray.length;
                Node curNext = cur.next;  // 記錄原先數(shù)組的下一個(gè)節(jié)點(diǎn)

                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;

                cur = curNext;  // 回到原先數(shù)組的下一個(gè)節(jié)點(diǎn)，而不是新數(shù)組的下一個(gè)節(jié)點(diǎn)
            }
        }
        array = newArray;
    }

public class Test {
    public static void main(String[] args) {
        HashBucket h = new HashBucket();
        h.push(1,111);
        h.push(2,222);
        h.push(4,444);
        h.push(14,141414);
        h.push(21,212121);
        h.push(12,121212);
        h.push(24,242424);
}

    // 查找有無(wú)key，與push方法中的查找類似
    public int getVal(int key){
        int index = key % array.length;
        Node cur = array[index];
        while (cur != null){
            if (cur.key == key){
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }

package hash;

public class HashBucket2<K, V> {
    static class Node<K,V>{
        public K key;
        public V val;
        public Node<K, V> next;

        public Node(K key, V val){
            this.key = key;
            this.val = val;
        }
    }

    public Node<K, V>[] array = (Node<K, V>[])new Node[10]; // 強(qiáng)轉(zhuǎn)
    public int usedSize;

    public static final double DEFAULT_LOAD_FACTOR = 0.75;

    public void push(K key, V val){
        int hashcode = key.hashCode();  // 調(diào)用 hashCode，使引用類型轉(zhuǎn)換為整數(shù)類型
        int index = hashcode % array.length;
        Node<K,V> cur = array[index];
        while(cur != null){
            if (cur.key.equals(key)){  // 引用類型用 .equals()
                cur.val = val;
                return;
            }
            cur = cur.next;
        }

        Node<K, V> node = new Node<>(key,val);
        node.next = array[index];
        array[index] = node;
        usedSize++;
        if (doLoadFactor() >= DEFAULT_LOAD_FACTOR){
            resize();
        }
    }

    private double doLoadFactor() {  // 計(jì)算當(dāng)前的負(fù)載因子
        return usedSize * 1.0 / array.length;
    }

    private void resize(){
        Node<K,V>[] newArray = (Node<K, V>[])new Node[2*array.length];  // 存放到新的數(shù)組

        // 遍歷原來(lái)的數(shù)組，重新哈希
        for (int i = 0; i < array.length; i++) {
            Node<K,V> cur = array[i];
            while (cur != null) {
                int hashcode = cur.key.hashCode();
                int newIndex = hashcode % newArray.length;
                Node<K,V> curNext = cur.next;  // 記錄原先數(shù)組的下一個(gè)節(jié)點(diǎn)
                cur.next = newArray[newIndex];
                newArray[newIndex] = cur;
                cur = curNext;  // 回到原先數(shù)組的下一個(gè)節(jié)點(diǎn)，而不是新數(shù)組的下一個(gè)節(jié)點(diǎn)
            }
        }
        array = newArray;
    }

    public V getVal(K key){
        int hashcode = key.hashCode();
        int index = hashcode % array.length;
        Node<K,V> cur = array[index];
        while(cur != null){
            if (cur.key.equals(key)){
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }
}

package hash;

import java.util.Objects;

class Student{
    public String id;
    public Student(String id){
        this.id = id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(id, student.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

public class Test {
    public static void main(String[] args) {
        Student student1 = new Student("409");
        Student student2 = new Student("409");

        System.out.println(student1.hashCode());
        System.out.println(student2.hashCode());

        // 當(dāng)自定義類沒(méi)有重寫(xiě) equals() 和 hashCode() 方法時(shí)，下面輸出false
        System.out.println(student1.equals(student2));

        HashBucket2<Student, String> h = new HashBucket2<>();
        h.push(student1,"Li");
        h.push(student2,"NAZA");
        System.out.println(h.getVal(student1));
    }
}

package hash;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class Test {
    public static Map<String, Integer> countWords(String[] str) {
        Map<String, Integer> map = new HashMap<>();
        for (String s : str) {
            if (map.get(s) != null){
                int val = map.get(s);  // 取得當(dāng)前的value值
                map.put(s,val+1);
            }else{
                map.put(s,1);
            }
        }
        return map;
    }

    public static void main(String[] args) {
        String[] str = {"Long","Long","Long","time","age","there","is","a","pig","live","in","a","house"};
        Map<String, Integer> map = countWords(str);
        Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
        for (Map.Entry<String, Integer> s : entrySet) {
            System.out.println("word: "+s.getKey() + "  nums: "+s.getValue());
        }
    }
}

    public int singleNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int n : nums) {
            if (set.contains(n)){
                set.remove(n);
            }else {
                set.add(n);
            }
        }
        for (int n : nums) {
            if (set.contains(n)){
                return n;
            }
        }
        return -1;
    }

    public Node copyRandomList(Node head) {
        HashMap<Node, Node> map = new HashMap<>();
        // 1、根據(jù)val值新建節(jié)點(diǎn)
        Node cur = head;
        while (cur != null){
            Node node = new Node(cur.val);
            map.put(cur,node);  // 將舊節(jié)點(diǎn)地址和新節(jié)點(diǎn)地址一起放到map中
            cur = cur.next;
        }

        // 2、重新遍歷,設(shè)置next和random
        cur = head;
        while (cur != null){
            // get()返回的是val值，即返回的是存放在map中的 新地址
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);  // 返回的是頭節(jié)點(diǎn)的新地址
    }

    public int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> jewelsSet = new HashSet<>();
        for(int i = 0; i < jewels.length(); i++){
            char s = jewels.charAt(i);
            jewelsSet.add(s);
        }

        int count = 0;
        for(int i = 0; i < stones.length(); i++){
            char s = stones.charAt(i);
            if(jewelsSet.contains(s)){
                count++;
            }
        }
        return count;
    }

    public static void findBrokenKey(String str1, String str2){
        // 1、先全部轉(zhuǎn)化為大寫(xiě)
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();

        // 2、將實(shí)際輸出的按鍵存儲(chǔ)到 set 中
        HashSet<Character> setAct = new HashSet<>();
        for (int i = 0; i < str2.length(); i++) {
            char c2 = str2.charAt(i);
            setAct.add(c2);
        }

        // 3、遍歷應(yīng)該輸出的字符串
        /*for (int i = 0; i < str1.length(); i++) {
            char c1 = str1.charAt(i);
            if (!setAct.contains(c1)) {
                System.out.print(c1);
            }
        }*/  // 存在問(wèn)題：重復(fù)輸出

        // 4、修正，避免重復(fù)輸出的情況
        HashSet<Character> setBroken = new HashSet<>();
        for (int i = 0; i < str1.length(); i++) {
            char c1 = str1.charAt(i);
            // 如果已經(jīng)存放到 setBroken ，即已經(jīng)被包含，就跳過(guò)if語(yǔ)句塊
            if (!setAct.contains(c1) && !setBroken.contains(c1)) {
                setBroken.add(c1);
                System.out.print(c1);
            }
        }
    }

    public static void main(String[] args) {
        String s1 = "7_This_is_a_test";
        String s2 = "_hs_s_a_es";
        findBrokenKey(s1,s2);
    }

    public List<String> topKFrequent(String[] words, int k) {
        // 1、統(tǒng)計(jì)單詞詞頻
        HashMap<String, Integer> wordFrequency = new HashMap<>();
        for (String word: words) {
            if (wordFrequency.get(word) == null){
                wordFrequency.put(word,1);
            }else{
                int val = wordFrequency.get(word);
                wordFrequency.put(word,val+1);
            }
        }

        // 2、建堆
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0){ // 如果詞頻一樣，就按照字典順序比較
                    return o2.getKey().compareTo(o1.getKey());   // 此處應(yīng)該建大根堆，因?yàn)槿绻⑿「眩竺鎟everse之后與題目要求不符
                }
                return o1.getValue().compareTo(o2.getValue());  // 根據(jù)詞頻建堆
            }
        });

        // 3、遍歷HashMap
        for (Map.Entry<String,Integer> entry: wordFrequency.entrySet()) {
            if (minHeap.size() < k) {  // 前k個(gè)單詞建立小根堆
                minHeap.offer(entry);
            }else{
                Map.Entry<String, Integer> top = minHeap.peek(); // 得到目前堆頂?shù)脑?
                // 進(jìn)行比較
                if (top.getValue().compareTo(entry.getValue()) < 0){  // 如果后面的元素詞頻大于前面最小的單詞的詞頻，就“交換”
                    minHeap.poll();
                    minHeap.add(entry);
                }else if(top.getValue().compareTo(entry.getValue()) == 0){  // 如果字母詞頻相同
                    if (top.getKey().compareTo(entry.getKey()) > 0){  // 字母較大的，存放到堆里面
                        minHeap.poll();
                        minHeap.add(entry);
                    }
                }
            }
        }

        ArrayList<String> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> tmp = minHeap.poll();
            list.add(tmp.getKey());
        }

        Collections.reverse(list);  // ArrayList 繼承的Collections接口可以翻轉(zhuǎn)
        return list;
    }