【Java数据结构】Map与Set、搜索树、哈希表

Map.Entry是Map内部实现的用来存放键值对映射关系的内部类，该内部类中主要提供了的获取，value的设置以及Key的比较方式

注意：Map.Entry并没有提供设置Key的方法

	public static void main(String[] args) {
        Map map = new HashMap<>();
        map.put("abc", 2);
        map.put("bit", 5);

        for (Map.Entry entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        // abc: 2
        // bit: 5
        Set> entrySet = map.entrySet();
        for (Map.Entry set : entrySet) {
            System.out.println(set.getKey() + ": " + set.getValue());
        }
        // abc: 2
        // bit: 5
    }

import java.util.TreeMap;
import java.util.Map;

public class TestMap1 {

    public static void testMap() {
        Map 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)
        // 因为TreeMap是按照Key进行组织的，因此查找value时候就需要整体遍历
        // 找到返回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 entry : m.entrySet()) {
            System.out.println(entry.getKey() + "--->" + entry.getValue());
        }
        System.out.println();
    }
}

Set 的官方文档

Set与Map主要的不同有两点：Set是继承自Collection的接口类，Set中只存储了Key

示例：

	public static void main(String[] args) {
        Set set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(3);
        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " "); // 1 2 3
        }
    }

注意：

Set是继承自 Collection 的一个接口类Set中只存储了key，并且要求key一定要唯一Set的底层是使用 Map 来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的Set最大的功能就是对集合中的元素进行去重实现Set接口的常用类有TreeSet和HashSet，还有一个linkedHashSet，linkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入Set中不能插入 null 的 keyTreeSet和HashSet的区别

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

public class Test {
    public static void TestSet(){
        Set 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);

        // 抛出空指针异常
        // s.remove(null);
        Iterator it = s.iterator();
        while(it.hasNext()){
            System.out.print(it.next() + " ");
        }
        System.out.println();
    }

public class TestDemo {
    // 从10W个数据中 找出第一个重复的数据
    public static int func3(int[] array) {
        Set set = new HashSet<>();
        for (int x : array) {
            if(set.contains(x)) {
                return x;
            } else {
                set.add(x);
            }
        }
        return -1;
    }

        // 将10W个数据去重
    public static Set func2(int[] array) {
        Set set = new HashSet<>();
        for (int x : array) {
            set.add(x);
        }
        return set;
    }

        // 给定10W数据 统计每个数据出现的次数
    public static Map func1(int[] array) {
        Map map = new HashMap<>();
        for (int x : array) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        return map;
    }

    public static void main(String[] args) {
        int[] array = new int[1_0000];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(1000);
        }
        
        
        System.out.println(func3(array));
    }
}

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:
输入: [2,2,1]
输出: 1

代码：

class Solution {
    // list  没有-加入 有-删除
    public int singleNumber(int[] nums) {
        ArrayList list = new ArrayList<>();
        for(int n : nums) {
            if(list.contains(n)) {
                list.remove(Integer.valueOf(n)); // 
            }else {
                list.add(n);
            }
        }
        return list.get(0);
    }

    // 哈希 存储次数
    public int singleNumber2(int[] nums) {
        HashMap map = new HashMap<>();
        for(int n : nums)  { 
            int cnt = map.getOrDefault(n, 0) + 1;
            map.put(n, cnt);
        }
        for(int i : map.keySet()) {
            if(map.get(i) == 1) {
                return i;
            }
        }
        return -1;
    }

    // 按位异或
    public int singleNumber1(int[] nums) {
        int single = nums[0];
        for(int i = 1; i < nums.length; i++) {
            single ^= nums[i];
        }
        return single;
    }
}

138. 复制带随机指针的链表
给你一个长度为 n的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。 深拷贝应该正好由 n 个 全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有X和 Y 两个节点，其中 X.random --> Y。那么在复制链表中对应的两个节点x和y ，同样有x.random --> y。

返回复制链表的头节点。

用一个由n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index]表示：

val：一个表示 Node.val的整数。random_index：随机指针指向的节点索引（范围从 0 到n-1）；如果不指向任何节点，则为 null。
你的代码 **只 **接受原链表的头节点 head作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

代码：

class Solution {
    public Node copyRandomList(Node head) {
        Map map = new HashMap<>();
        Node cur = head;
        // 第一次遍历 存储老节点与新节点的映射关系
        while(cur != null) {
            Node node = new Node(cur.val);
            map.put(cur, node);
            cur = cur.next;
        }
        // 第二次遍历 修改新节点的next 和random
        cur = head;
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        // 返回新节点的head
        return map.get(head);
    }
}

迭代：

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return head;
        }
        // 空间复杂度O(1)，将克隆结点放在原结点后面
        Node node = head;
        // 1->2->3  ==>  1->1'->2->2'->3->3'
        while(node != null){
            Node clone = new Node(node.val,node.next,null);
            Node temp = node.next;
            node.next = clone;
            node = temp;
        }
        // 处理random指针
        node = head;
        while(node != null){
            // ！！
            node.next.random = node.random == null ? null : node.random.next;
            node = node.next.next;
        }
        // 还原原始链表，即分离原链表和克隆链表
        node = head;
        Node cloneHead = head.next;
        while(node.next != null){
            Node temp = node.next;
            node.next = node.next.next;
            node = temp;
        }
        return cloneHead;
    }
}

771. 宝石与石头

给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

字母区分大小写，因此 “a” 和 “A” 是不同类型的石头。

示例 1：
输入：jewels = “aA”, stones = “aAAbbbb”
输出：3

代码：

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        int count = 0;
        HashSet set = new HashSet<>();
        
        for(Character ch : jewels.toCharArray()) {
            set.add(ch);
        }
        for(Character ch : stones.toCharArray()) {
            if(set.contains(ch)) {
                count++;
            }
        }

        return count;
    }
}

旧键盘 (20)

旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出
肯定坏掉的那些键。

输入描述:
输入在2行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过80个字符的串，由字母A-Z（包括大、小写）、数字0-9、
以及下划线“_”（代表空格）组成。题目保证2个字符串均非空。

输出描述:
按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。题目保证至少有1个坏键。

示例1

输入
7_This_is_a_test
_hs_s_a_es
输出
7TI

代码：

import java.util.*;

public class Main {
    
    public static void findbroken(String strExcept, String strActual) {
        // 实际加入set 大写
        Set set = new HashSet<>();       
        for(int i = 0; i < strActual.length(); i++) {
            char ch = strActual.charAt(i);
            set.add(Character.toUpperCase(ch));
        }
        // 答案字符只出现一次
        Set result = new HashSet<>();
        for(int i = 0; i < strExcept.length(); i++) {
            char ch = strExcept.charAt(i);
            ch = Character.toUpperCase(ch); // 大写
            if(!set.contains(ch)) { // 期望的字符没有 就是坏键盘
                if(!result.contains(ch)) {
                    result.add(ch);
                    System.out.print(ch);
                }
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String strExcept = scanner.nextLine();
        String strActual = scanner.nextLine();
        findbroken(strExcept, strActual);
    }
    
}

692. 前K个高频单词

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

示例 1：
输入: words = [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
输出: [“i”, “love”]
解析: “i” 和 “love” 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 “i” 在 “love” 之前。

代码：

class Solution {
    // 2、优先级队列
    public List topKFrequent(String[] words, int k) {
        // 1、统计每个单词出现的次数
        Map map = new HashMap<>();
        for(String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        // 2、建立一个大小为 K 的小根堆
        PriorityQueue> minHeap = new PriorityQueue<>(k, new Comparator>() {
            @Override
            public int compare(Map.Entry o1, Map.Entry o2) {
                // 如果不满k个 a-2 b-2 最后会逆置
                // 如果频率相同 相反
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue() - o2.getValue();
            }
        });
        // 3、遍历 map
        for (Map.Entry entry : map.entrySet()) {
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                // 拿出堆顶元素
                Map.Entry top = minHeap.peek();
                // 堆中放满 k 个元素，比较堆顶的元素的数据，和当前数据的大小关系
                if(top.getValue().compareTo(entry.getValue()) == 0) {
                    // 和堆顶元素出现次数相同 比较单词次数 单词小的入堆
                    if(top.getKey().compareTo(entry.getKey()) > 0) {
                        minHeap.poll(); // 堆顶元素大
                        minHeap.offer(entry);
                    }
                } else {
                    // 频率不相等时 小堆的堆顶元素最小 如果当前单词单词频率比堆顶大 出堆
                    if (top.getValue().compareTo(entry.getValue()) < 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        // 4、返回
        List ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry top = minHeap.poll();
            ret.add(top.getKey());
        }
        Collections.reverse(ret); // 逆置
        return ret;
    }

    // 1、哈希表 排序
    public List topKFrequent1(String[] words, int k) {
        // 统计 word 次数
        Map map = new HashMap<>();
        for(String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        // Key 加入 List
        List list = new ArrayList<>();
        for(Map.Entry entry : map.entrySet()) {
            list.add(entry.getKey());
        }
        // 重写 Comparator 方法。按出现次数比较，次数相同，按字典顺序比较
        Collections.sort(list, new Comparator() {
            @Override
            public int compare(String o1, String o2) {
                return map.get(o1) == map.get(o2) ? o1.compareTo(o2) : map.get(o2) - map.get(o1);
            }
        });
        // 返回前 k 个
        return list.subList(0, k);
    }
}

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

	
    public Node search(int key) {
        Node cur = root;
        while(cur != null) {
            if(cur.val < key) { // cur的val比val小 在cur的右边
                cur = cur.right;
            } else if (cur.val == key) {
                return cur;
            } else {
                cur = cur.left;
            }
        }
        return null; // 没有这个数据
    }

	
    public boolean insert(int val) {
        if(root == null) {
            root = new Node(val);
            return true;
        }
        // cur parent 找val需要存储的位置
        Node cur = root;
        Node parent = null;
        while(cur != null) {
            if(cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val == val) {
                return false; // 不能有相同的数据
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
        // parent.val 和 val 比较大小，确定在插入的在左树还是右树
        Node node = new Node(val);
        if(parent.val < val) { // parent小 就在parent的右边
            parent.right = node;
        } else {
            parent.left = node;
        }
        return true;
    }

	
    public void remove(int key) {
        Node cur = root;
        Node parent = null;
        while(cur != null) {
            if(cur.val == key) { // 找到了
                removeNode(cur, parent); // 此处是删除
                break;
            } else if (cur.val < key) { // 在右边
                parent = cur;
                cur = cur.right;
            } else { // 在左边
                parent = cur;
                cur = cur.left;
            }
        }
    }

    public void removeNode(Node cur, Node parent) {
        if(cur.left == null) { // 一、cur左为空
            if(cur == root) { // 1.
                root = cur.right;
            } else if (cur == parent.left) { // 2.
                parent.left = cur.right;
            } else { // 3. cur == parent.right
                parent.right = cur.right;
            }
        } else if (cur.right == null) { // 二、cur右为空
            if(cur == root) { // 1.
                root = cur.left;
            } else if (cur == parent.left) { // 2.
                parent.left = cur.left;
            } else { // 3.cur == parent.right
                parent.right = cur.left;
            }
        } else { // 三、cur左不为空 右也不为空
            // cur 的左树中 找最大值
            // cur 的右树中 找最小值
            Node targetParent = cur;
            Node target = cur.right;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val; // 替换 val
            // 删除
            if (target == targetParent.left) {
                targetParent.left = target.right;
            } else {
                targetParent.right = target.right;
            }
        }
    }

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：log N最差情况下，二叉搜索树退化为单支树，其平均比较次数为 N / 2

TreeMap 和 TreeSet 即 java 中利用搜索树实现的 Map 和 Set；实际上用的是红黑树，而红黑树是一棵近似平衡的二叉搜索树，即在二叉搜索树的基础之上 + 颜色以及红黑树性质验证

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node(int val) {
        this.val = val;
    }
}

public class BinarySearchTree {
    public Node root;

    
    public Node search(int key) {
        Node cur = root;
        while(cur != null) {
            if(cur.val < key) { // cur的val比val小 在cur的右边
                cur = cur.right;
            } else if (cur.val == key) {
                return cur;
            } else {
                cur = cur.left;
            }
        }
        return null; // 没有这个数据
    }
    

    
    public boolean insert(int val) {
        if(root == null) {
            root = new Node(val);
            return true;
        }
        // cur parent 找val需要存储的位置
        Node cur = root;
        Node parent = null;
        while(cur != null) {
            if(cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val == val) {
                return false; // 不能有相同的数据
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
        // parent.val 和 val 比较大小，确定在插入的在左树还是右树
        Node node = new Node(val);
        if(parent.val < val) { // parent小 就在parent的右边
            parent.right = node;
        } else {
            parent.left = node;
        }
        return true;
    }

    
    public void remove(int key) {
        Node cur = root;
        Node parent = null;
        while(cur != null) {
            if(cur.val == key) { // 找到了
                removeNode(cur, parent); // 此处是删除
                break;
            } else if (cur.val < key) { // 在右边
                parent = cur;
                cur = cur.right;
            } else { // 在左边
                parent = cur;
                cur = cur.left;
            }
        }
    }

    public void removeNode(Node cur, Node parent) {
        if(cur.left == null) { // 一、cur左为空
            if(cur == root) { // 1.
                root = cur.right;
            } else if (cur == parent.left) { // 2.
                parent.left = cur.right;
            } else { // 3. cur == parent.right
                parent.right = cur.right;
            }
        } else if (cur.right == null) { // 二、cur右为空
            if(cur == root) { // 1.
                root = cur.left;
            } else if (cur == parent.left) { // 2.
                parent.left = cur.left;
            } else { // 3.cur == parent.right
                parent.right = cur.left;
            }
        } else { // 三、cur左不为空 右也不为空
            // cur 的左树中 找最大值
            // cur 的右树中 找最小值
            Node targetParent = cur;
            Node target = cur.right;
            while (target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val; // 替换 val
            // 删除
            if (target == targetParent.left) {
                targetParent.left = target.right;
            } else {
                targetParent.right = target.right;
            }
        }
    }


    public void inorder(Node root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        int[] array = {5, 13, 7, 11, 9, 3, 8};
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        for (int i = 0; i < array.length; i++) {
            binarySearchTree.insert(array[i]);
        }
        binarySearchTree.inorder(binarySearchTree.root); // 3 5 7 8 9 11 13
        System.out.println('n' + "插入重复的数据");
        System.out.println(binarySearchTree.insert(3)); // false
        System.out.println("删除数据3");
        binarySearchTree.remove(3);
        binarySearchTree.inorder(binarySearchTree.root); // 5 7 8 9 11 13
    }
}

定义在方法当中的类
缺点：只能在当前方法中使用

public class TestDemo {
    public void func() {
        class Test { // 内部类
            public int num;
        }
    }
}

在实例内部类当中，不能定义一个静态的成员变量，如果非要定义，只能定义一个静态常量public static final int data6 = 6;如何实例化，实例内部类对象
OuterClass.InnerClass innerClass = outerClass.new InnerClass();
外部类名.内部类名 变量 = 外部类对象的引用.new 内部类()被其他类继承等

public class TestDemo extends OuterClass.InnerClass {
    public TestDemo(OuterClass out) {
        out.super();
    }

字节码文件：外部类类名 美元符号 内部类类名.class

实例内部类中，如果包含了和外部类同名的成员变量，如何在实例内部类当中访问
实例内部类，包含了两个 this ，一个是外部类的 this，一个是自己的 this

System.out.println(OuterClass.this.data1); // 外部类的 this
System.out.println(this.data1); // 加this还是999999 当前类的引用

测试代码：

class OuterClass {
    public int data1 = 1;
    private int data2 = 2;
    public static int data3 = 3;

    //实例内部类：你可以把他当做 是外部类的一个普通实例的成员
    class InnerClass { // 实例内部类
        // public static int num = 10; // 1. err
        public int data1 = 999999;
        public int data4 = 4;
        private int data5 = 5;
        public static final int data6 = 6;

        public InnerClass() {
            System.out.println("不带参数的内部类的构造方法！");
        }

        public void test() {
            // 实例内部类中，如果包含了和外部类同名的成员变量，如何在实例内部类当中访问
            System.out.println(OuterClass.this.data1); // 外部类的 this
            System.out.println(this.data1); // 加this还是999999 当前类的引用

            System.out.println(data2);
            System.out.println(data3);
            System.out.println(data4);
            System.out.println(data5);
            System.out.println(data6);
            System.out.println("InnerClass::test()");
        }
    }

    public void func1() {
        //static int a = 10; 属于类的  不属于对象的
        System.out.println("OuterClass::func1()");
    }
}

public class TestDemo extends OuterClass.InnerClass {
    public TestDemo(OuterClass out) {
        out.super();
    }

    public static void main(String[] args) {
        OuterClass outerClass = new OuterClass();
        // 2、实例化内部类对象
        // 外部类名.内部类名 变量 = 外部类对象的引用.new 内部类()
        OuterClass.InnerClass innerClass = outerClass.new InnerClass(); // 运行：不带参数的内部类的构造方法！

        innerClass.test(); // 1 999999 2 3 4 5 6 InnerClass::test()
    }

可以定义一个静态的成员变量如何实例化，静态内部类对象：
OuterClass2.InnerClass innerClass = new OuterClass2.InnerClass();在静态内部类中，访问外部类的普通的成员变量：

class OuterClass2 {
    public int data1 = 1;
    private int data2 = 2;
    
    static class InnerClass { // 静态内部类
        public void test() {
            // System.out.println(data1); // err 需要外部类的引用
            
            // 1、
            OuterClass2 outerClass2 = new OuterClass2();
            System.out.println(outerClass2.data1);

            System.out.println(new OuterClass2().data1); // 2、

            //System.out.println(out.data2); // 私有成员需要get set方法
        }
}

class OuterClass2 {
    public int data1 = 1;
    
    static class InnerClass { // 静态内部类
		public OuterClass2 out;
        public InnerClass(OuterClass2 out) {
            this.out = out;
        }
  
        public void test() {
            // System.out.println(data1); // err 需要外部类的引用
            System.out.println(out.data1); // 3、
        }
}

public class TestDemo2 {
    public static void main(String[] args) {
        OuterClass2 o = new OuterClass2();
        OuterClass2.InnerClass innerClass = new OuterClass2.InnerClass(o);
    }
}

class OuterClass2 {
    public int data1 = 1;
    
    static class InnerClass { // 静态内部类
		public OuterClass2 out;
        public InnerClass(OuterClass2 out) {
            this.out = out;
        }

		public InnerClass() { // 
        }
  
        public void test() {
            // System.out.println(data1); // err 需要外部类的引用
            System.out.println(out.data1); // 4、
        }
}

public class TestDemo2 {
    public static void main(String[] args) {
        OuterClass2.InnerClass innerClass = new OuterClass2.InnerClass();
    }
}

匿名对象加花括号就是一个匿名内部类

class Test {
    public void test() {
        System.out.println("test()");
    }
}

public class TestDemo3 {
    public static void main(String[] args) {
        new Test();// 匿名对象

        new Test() {  // 匿名内部类
            
        };
    }
}

访问 test 方法：
输出：test()->

	public static void main(String[] args) {
        new Test() {

        }.test(); // 
    }

重写方法
此时运行输出的是：

	public static void main(String[] args) {
        new Test();// 匿名对象

        new Test() {  // 匿名内部类

            @Override
            public void test() {
                System.out.println("重写的test方法"); // 重写后：重写的test方法
            }
        }.test(); // 重写前：test()->
    }

优先级队列的使用：
匿名内部类实现 Comparator 接口

	public static void main(String[] args) {
        PriorityQueue pri = new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return 0;
            }
        });
    }

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( log n)，搜索的效率取决于搜索过程中元素的比较次数。

理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数 (hashFunc) 使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：

插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table) (或者称散列表)

例如：数据集合{1，7，6，4，5，9}；
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小

该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快 问题：按照上述哈希方式，向集合中插入元
素44，会出现什么问题？

冲突：
对于两个数据元素的关键字ki和 kj(i != j)，有ki != kj，但有：Hash( ki) == Hash(kj )，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

避免;
首先，我们需要明确一点，由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一个问题，冲突的发生是必然的，但我们能做的应该是尽量地降低冲突率

两种方法：

哈希函数的设计调节负载因子

注意：此二者皆无法避免冲突，我们需要解决冲突：闭散列和开散列

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

哈希函数设计原则：

1.哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
2.哈希函数计算出来的地址能均匀分布在整个空间中
3.哈希函数应该比较简单

常见哈希函数

直接定制法–(常用)
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀 缺点：需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况
面试题：字符串中第一个只出现一次字符

除留余数法–(常用)
设散列表中允许的**地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，**按照哈希函数：
Hash(key) = key% p(p<=m)，将关键码转换成哈希地址

平方取中法–(了解)
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况

折叠法–(了解)
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，
并按散列表表长，取后几位作为散列地址。
折叠法适合事先不需要知道关键字的分布，适合关键字位数比较多的情况

随机数法–(了解)
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。
通常应用于关键字长度不等时采用此法

数学分析法–(了解)
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。例如：

假设要存储某家公司员工登记表，如果用手机号作为关键字，那么极有可能前7位都是 相同的，那么我们可以选择后面的四位作为散列地址，如果这样的抽取工作还容易出现 冲突，还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环移位、前两数与后两数叠加(如1234改成12+34=46)等方法。

数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

负载因子 = 存储散列表的元素的个数 / 散列表的长度
HashMap 负载因子：0.75

负载因子和冲突率的关系粗略演示

所以当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率，也就是扩容。

已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小。

冲突的发生是必然的，我们只能最大程度地降低冲突率

解决哈希冲突两种常见的方法是：闭散列和开散列

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。

那如何寻找下一个空位置呢？

1、线性探测
比如上面的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，下标为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。（会把冲突的元素都放在一起）

线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

插入
通过哈希函数获取待插入元素在哈希表中的位置
如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素

删除
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

2、二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：Hi = (H0 + i^2)% m， 或者：Hi = (H0 - i^2)% m。其中：i = 1,2,3…，H0 是通过散列函数 Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。 对于2.1中如果要插入44，产生冲突，使用解决后的情况为：

研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。

因此：比散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。

开散列法又叫链地址法(开链法)，（数组 + 链表），首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

链表的长度不会很长，控制在常数范围内JDK1.8开始，当链表的长度超过8这个链表就会变成红黑树，但是：数组的长度要长度64，就是 HashMap的处理方法

开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了

刚才我们提到了，哈希桶其实可以看作将大集合的搜索问题转化为小集合的搜索问题了，那如果冲突严重，就意味着小集合的搜索性能其实也时不佳的，这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化，例如：

每个桶的背后是另一个哈希表每个桶的背后是一棵搜索树

put

在put的过程中，检查负载因子，如果超过了，需要增加散联保的长度，如果扩容数组那么数组里面的每个链表的每个元素都要进行重新哈希!! !

代码

public class HashBuck {

    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;
    public int usedSize;
    // 负载因子
    public static final double DEFAULT_LOAD_FACTOR = 0.75;

    public HashBuck() {
        this.array = new Node[10];
    }

    
    public void put(int key, int val) {
        // 1、找到 key 所在的位置
        int index = key % this.array.length;
        // 2、遍历这个下标的链表，看是不是有相同 key的节点，如果有，更新它的 val值
        Node cur = array[index];
        while (cur != null) {
            if(cur.key == key) {
                cur.val = val; // 更新完 结束
                return;
            }
            cur = cur.next;
        }
        // 3、如果没有 key 这个元素，头插法插入
        Node node = new Node(key, val);
        node.next = array[index]; // 先后
        array[index] = node; // 再前
        this.usedSize++;
        // 4、插入元素成功之后，检查当前散列表的负载因子
        if(loadFactor() > DEFAULT_LOAD_FACTOR) {
            // 增加散链表的长度
            resize();
        }
    }

    // 增加散链表的长度
    private void resize() {
        Node[] newArray = new Node[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i]; // 每个下标下的链表
            while (cur != null) {
                int index = cur.key % newArray.length; // 获取新的下标
                // 就是把cur这个节点，以头插/尾插的形式插入到新的数组对应下标的链表当中
                Node curNext = cur.next; // 如果cur的后面还有节点
                cur.next = newArray[index]; // 先绑定后面
                newArray[index] = cur; // 再绑定前面
                cur = curNext;
            }
        }
        array = newArray;
    }

    // 检查当前散列表的负载因子
    private double loadFactor() {
        return 1.0 * this.usedSize / array.length;
    }

    
    public int get(int key) {
        // 1、找到 key 所在的位置
        int index = key % this.array.length;
        // 2、遍历这个下标的链表，看是不是有相同 key的节点
        Node cur = array[index];
        while (cur != null) {
            if(cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }

    public static void main(String[] args) {
        HashBuck hashBuck = new HashBuck();
        hashBuck.put(1,1);
        hashBuck.put(12,12);
        hashBuck.put(3,3);
        hashBuck.put(6,6);
        hashBuck.put(7,7);
        hashBuck.put(2,2);
        hashBuck.put(11,11);
        // hashBuck.put(8,8); // 8/10>0.75 扩容
        System.out.println(hashBuck.get(11));
    }
}

假设接下来的key是一个person。身份证号是一样的我们认为是同一个人
又因为：要把person1和person2放到散列表当中，假设接下来的key是一个person。

调用 hashcode() : 生成一个整数 % length = index
我们猜测这个index一定是一样的，
但是 运行结果：
1908153060
116211441

class Person {
    public String ID;

    public Person(String ID) {
        this.ID = ID;
    }

    @Override
    public String toString() {
        return "Person{" +
                "ID='" + ID + ''' +
                '}';
    }
}

public class HashBuck2 {
    public static void main(String[] args) {
        Person person1 = new Person("123");
        Person person2 = new Person("123");
        System.out.println(person1.hashCode());
        System.out.println(person2.hashCode());
    }
}

所以我们需要重写 equals 与 hashCode
此时运行：
48721
48721
结果相同

自定义类型一定要重写 equals 与 hashCode方法

HashMap map = new HashMap<>();

hashcode一样equals不一定一样
equals一样hashcode一定一样

代码：

import java.util.HashMap;
import java.util.Objects;

class Person {
    public String ID;

    public Person(String ID) {
        this.ID = ID;
    }

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

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

    @Override
    public String toString() {
        return "Person{" +
                "ID='" + ID + ''' +
                '}';
    }
}

public class HashBuck2 {

    static class Node {
        public K key;
        public V val;
        public Node next;

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

    public Node[] array;
    public int usedSize;

    public HashBuck2() {
        this.array = (Node[]) new Node[10];
    }

    
    public void put(K key, V val) {
        // 1、找到 key 所在的位置
        int hash = key.hashCode();
        int index = hash % array.length;
        // 2、遍历这个下标的链表，看是不是有相同 key的节点，如果有，更新它的 val值
        Node cur = array[index];
        while (cur != null) {
            if(cur.key.equals(key)) { // 通过重写的 equals 比较
                cur.val = val; // 更新完 结束
                return;
            }
            cur = cur.next;
        }
        // 3、如果没有 key 这个元素，头插法插入
        Node node = new Node<>(key, val);
        node.next = array[index]; // 先后
        array[index] = node; // 再前
        this.usedSize++;
    }

    
    public V get(K key) {
        // 1、找到 key 所在的位置
        int hash = key.hashCode();
        int index = hash % array.length;
        // 2、遍历这个下标的链表，看是不是有相同 key的节点，如果有，更新它的 val值
        Node cur = array[index];
        while (cur != null) {
            if(cur.key.equals(key)) { // 通过重写的 equals 比较
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }

    public static void main(String[] args) {
        Person person1 = new Person("123");
        Person person2 = new Person("123");

        HashBuck2 hashBuck2 = new HashBuck2<>();
        hashBuck2.put(person1, "bit");

        System.out.println(hashBuck2.get(person2)); // bit
        // 以person2获取val 重写了equals方法 拿到的也是bit
    }
}

虽然哈希表一直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的，也就是每个桶中的链表的长度是一个常数，所以，通常意义下，我们认为哈希表的插入/删除/查找时间复杂度是
O(1) 。

HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Setjava 中使用的是哈希桶方式解决冲突的java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）java 中计算哈希值实际上是调用的类的 hashCode 方法，进行 key 的相等性比较是调用 key 的 equals 方法。所以如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方法，而且要做到 equals 相等的对象，hashCode 一定是一致的。

哈希表