前情提要——二叉樹

葉子節(jié)點(diǎn)就是左右孩子都是空的妄壶，但是并不是每一顆樹都像上圖所示的那樣這么規(guī)整豪筝，有些樹樹可以只有左孩子沒有右孩子的墩蔓。二叉樹的節(jié)點(diǎn)一定會(huì)大于左節(jié)點(diǎn)的值小于右節(jié)點(diǎn)的值样刷，每一個(gè)節(jié)點(diǎn)都要滿足蛛碌，所有每一個(gè)節(jié)點(diǎn)下面拿出來的樹都可以作為一個(gè)二叉樹。既然有大于等于了躯护，那么這科樹的元素一定要有可比較性才可以室谚。

Create a BST

package Tree.BST;

public class BST<E extends Comparable<E>> {
    /**
     * Binary Search Tree
     */

    private class Node {
        public E e;
        public Node left, right;

        public Node(E e) {
            this.e = e;
            left = right = null;
        }
    }

    private Node root;
    private int size;

    public BST() {
        root = null;
        size = 0;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }
}

和上面描述的基本一致的含潘。

Insert an element

插入一個(gè)元素也很簡單肮砾，查看當(dāng)前元素是否是大于或者小于節(jié)點(diǎn)元素洋幻，如果是大于，那么就右邊遞歸即可权旷，二叉樹的插入非遞歸寫法和鏈表很像鄙麦。

    public void add(E e) {
        root = add(root, e);
    }

    private Node add(Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        }
        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        } else {
            node.right = add(node.right, e);
        }
        return node;
    }

Select an element

判斷一個(gè)元素和查找一個(gè)元素算法基本一致矛双，小于左邊找渊抽，大于右邊找即可蟆豫。
···
public boolean contains(E e) {
return contains(root, e);
}

public boolean contains(Node node, E e) {
    if (node == null) {
        return false;
    } else if (e.equals(node.e)) {
        return true;
    } else if (e.compareTo(node.e) < 0) {
        return contains(node.left, e);
    } else {
        return contains(node.right, e);
    }
}

···

Traversal

前中后序遍歷都很簡單，代碼和前面C++都都是一樣的懒闷。對(duì)于中序遍歷的非遞歸遍歷十减。非遞歸遍歷可以對(duì)比遞歸來實(shí)現(xiàn)栈幸，數(shù)據(jù)結(jié)構(gòu)里面有遞歸屬性的只有棧了，所以可以用棧來實(shí)現(xiàn)帮辟。先把根元素壓進(jìn)棧速址，由于前序遍歷直接輸出第一個(gè)遍歷到到元素，所以先出棧輸出之后再把出棧的元素的子節(jié)點(diǎn)壓進(jìn)去由驹，要注意的是右孩子先壓芍锚，左孩子再壓，因?yàn)楸闅v的順序是先遍歷左邊再遍歷右邊蔓榄，以此類推并炮，只到空為止。
遞歸處理很簡單甥郑，幾行就好了逃魄，主要繁瑣到就是非遞歸遍歷到過程，前序遍歷的非遞歸澜搅。這個(gè)算算比較簡單到伍俘，因?yàn)橄缺闅v到是一開始遍歷到到點(diǎn)，再依次是左右子樹勉躺，沒有倒敘過程癌瘾，都是有順序性到，所以可以直接用棧處理饵溅，先把跟節(jié)點(diǎn)扔進(jìn)去柳弄，如果棧不為空，那么就要出棧概说，直接輸出當(dāng)前元素碧注，在放入左右子樹即可，但是放入左右子樹需要注意糖赔，應(yīng)當(dāng)先放入右子樹再放入左子樹萍丐，因?yàn)槭窍缺闅v左子樹再遍歷右子樹，而棧是反過來的放典。

public void preOrderNonRecur() {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            System.out.print(node.e + " ");
            if (node.right != null)
                stack.push(node.right);
            if (node.left != null)
                stack.push(node.left);
        }
        System.out.println();
    }

這就是前序遍歷逝变。中序的非遞歸遍歷就有點(diǎn)復(fù)雜了，中序遍歷是左中右奋构，這個(gè)時(shí)候順序就不是都往下了壳影，沒有辦法一次性就遍歷完，棧里面一開始存儲(chǔ)都應(yīng)該是遍歷一開始要拿出來輸出都元素弥臼，所以可以先把左邊子樹都遍歷完存到棧里面宴咧，然后以這些存到棧里面的元素為起點(diǎn)遍歷下去。每次出來一個(gè)元素都要看看這個(gè)元素的右子樹是否存在径缅，如果存在就要遍歷掺栅，但其實(shí)不必要這樣判斷烙肺，因?yàn)樗惴ㄇ懊娴拇笱h(huán)已經(jīng)判斷了。

    public void inOrderNonRecur() {
        Stack<Node> stack = new Stack<>();
        Node node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                Node node1 = stack.pop();
                System.out.print(node1.e + " ");
                node = node1.right;
            }
        }
        System.out.println();

    

對(duì)于后序遍歷就是最復(fù)雜的了氧卧，由于后序遍歷和前序遍歷都是逆的桃笙，所以一開始也要先把左子樹放到棧里面，出的時(shí)候在看看有沒有右子樹沙绝。但是這里有個(gè)問題搏明，這里的右子樹是先輸出再到當(dāng)前節(jié)點(diǎn)的，首先要拿到當(dāng)前節(jié)點(diǎn)闪檬，然后再看看右子樹有沒有熏瞄，有就遍歷，等右子樹遍歷完之后當(dāng)前節(jié)點(diǎn)還在棧里面谬以，這個(gè)時(shí)候再拿出來的還是當(dāng)前節(jié)點(diǎn)强饮，這個(gè)時(shí)候就不知道右子樹有沒有被遍歷過了，這就進(jìn)入到了一個(gè)死循環(huán)为黎，所以這里要使用一個(gè)標(biāo)記來看看有沒有訪問了右子樹邮丰，如果訪問了右子樹，就可以放心輸出了铭乾，因?yàn)閣hile循環(huán)的時(shí)候已經(jīng)到了最左邊的了剪廉，這個(gè)時(shí)候不會(huì)再有左子樹，只需要考慮右子樹即可炕檩。

public void lastOrderNonRecur() {
        Stack<Node> stack = new Stack<>();
        Node node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                Node node1 = stack.peek();
                if (!node1.isright) {
                    node1.isright = true;
                    node = node1.right;
                } else {
                    node = stack.pop();
                    System.out.print(node.e + " ");
                    node = null;
                }
            }
        }
        System.out.println();
    }

中序遍歷和后序遍歷都從左邊擴(kuò)散到右邊斗蒋。
最后一個(gè)就是層序遍歷，層序遍歷就是廣度優(yōu)先遍歷笛质，實(shí)現(xiàn)用隊(duì)列就好了泉沾，事實(shí)上大多數(shù)的廣度優(yōu)先遍歷基本都是要使用隊(duì)列的。之前的數(shù)據(jù)結(jié)構(gòu)說過妇押，直接給出代碼即可：

levelOrder(){
        Queue<Node> nodes = new LinkedList<>();
        nodes.add(root);
        while (!nodes.isEmpty()){
            Node node = nodes.remove();
            System.out.print(node.e + " ");
            if (node.left != null){
                nodes.add(node.left);
            }
            if (node.right != null){
                nodes.add(node.right);
            }
        }
        System.out.println();
    }

remove an specific element

刪除一個(gè)元素有點(diǎn)麻煩跷究，如果只有一邊有元素，那么就只需要把一邊的移動(dòng)上去替代即可敲霍，如果兩邊都有子樹俊马，那么就需要把右子樹最小的一個(gè)移動(dòng)上去，當(dāng)然肩杈，其實(shí)也可以把左子樹最大的移動(dòng)上去柴我，替代原來的即可。

    private Node remove(Node node, E e) {
        if (node == null) {
            return null;
        } else if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);
            return node;
        } else if (e.compareTo(node.e) > 0) {
            node.right = remove(node.right, e);
            return node;
        } else{
            if (node.left == null){
                Node node1 = node.right;
                node.right = null;
                size--;
                return node1;
            }else if (node.right == null){
                Node node1 = node.left;
                node.left = null;
                size--;
                return node1;
            }else {
                Node successor = new Node(minimum(node.right).e);
                successor.left = node.left;
                successor.right = removeMin(node.right);
                node.left = node.right = null;
                return successor;
            }
        }

    }

集合Set

集合這種數(shù)據(jù)結(jié)構(gòu)有點(diǎn)像高中數(shù)學(xué)那種集合扩然，集合有一個(gè)特點(diǎn)艘儒，就是每一個(gè)元素只能有一個(gè)，這個(gè)性質(zhì)可以用來做去重工作。再上面實(shí)現(xiàn)的二分搜索樹是不可以存放重復(fù)數(shù)據(jù)的彤悔，所以可以作為集合的一種底層實(shí)現(xiàn)方式。二叉樹的實(shí)現(xiàn)是有要求的索守，要求一定要是二叉樹的結(jié)構(gòu)來實(shí)現(xiàn)晕窑，而集合只是要求有這么多功能就OK，所以集合屬于一種高級(jí)數(shù)據(jù)結(jié)構(gòu)卵佛，沒有具體實(shí)現(xiàn)方法杨赤。

集合基本方法

Set創(chuàng)建一個(gè)集合，remove移除集合的一個(gè)元素截汪，contains查看集合是否包含這個(gè)元素疾牲，getSize獲得集合大小，isEmpty查看集合是否為空衙解，add添加一個(gè)元素阳柔，不能添加重復(fù)的元素。
集合的應(yīng)用很廣蚓峦，訪問量的統(tǒng)計(jì)舌剂，詞匯量的統(tǒng)計(jì)等等都可以用到集合去重。首先是基于BST的集合暑椰，上面實(shí)現(xiàn)的BST完全包含了集合的功能霍转。直接包裝一下即可。

Leecode804

Leecode804一汽，摩斯碼的判斷：

這個(gè)題目非常簡單避消，直接替換一下扔到集合里面就好了，這里使用的就是treeSet召夹，是使用的紅黑樹實(shí)現(xiàn)方式：

class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String [] codes = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        TreeSet<String> set = new TreeSet<>();
        for (String word : words){
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < word.length(); i++) {
                stringBuilder.append(codes[word.charAt(i) - 'a']);
            }
            set.add(stringBuilder.toString());
        }
        return set.size();
    }
}

之前所實(shí)現(xiàn)的集合岩喷，二分搜索樹，紅黑樹這些實(shí)現(xiàn)的集合都是有順序性的监憎，因?yàn)檫@些結(jié)構(gòu)實(shí)現(xiàn)的集合是很容易可以排序（中序遍歷）均驶，找到下一個(gè)上一個(gè)等等，是屬于有序集合枫虏，而鏈表這些就屬于無序性的了妇穴。

優(yōu)先隊(duì)列和堆

堆的基本結(jié)構(gòu)， 這里的堆實(shí)現(xiàn)也和樹有關(guān)系隶债，二叉堆腾它。二叉堆是一個(gè)完全二叉樹。

package Heap;

import Array.Array;

public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;

    public MaxHeap(int capacity) {
        data = new Array<E>(capacity);
    }

    public MaxHeap() {
        data = new Array<E>();
    }

    public int size() {
        return data.getSize();
    }

    public boolean isEmpty() {
        return data.isEmpty();
    }

    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("No parents when index equal zero!");
        }
        return (index - 1) / 2;
    }

    private int leftChild(int index) {
        return index * 2 + 1;
    }

    private int rightChild(int index) {
        return index * 2 + 2;
    }

    
}

堆的實(shí)現(xiàn)之前的C++有寫過死讹，對(duì)于插入一個(gè)元素瞒滴，插入在數(shù)組的最后面,然后再按照規(guī)則慢慢的shiftUp上去，如果這個(gè)元素是大于它的父母，那么就要浮上去妓忍，然后以父母為當(dāng)前元素繼續(xù)循環(huán)判斷：

    private void shiftUp(int index) {
        while (index > 0 && data.get(index).compareTo(data.get(parent(index))) > 0) {
            data.swap(index, parent(index));
            index = parent(index);
        }
    }

輸出最大值的元素就只需要把第一個(gè)元素輸出虏两，把最后一個(gè)元素補(bǔ)上，再把新的第一個(gè)元素進(jìn)行shiftDown操作：

    private void shiftDown(int index){
        while (leftChild(index) < data.getSize()){
            int j = leftChild(index);
            if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0){
                j = rightChild(index);
            }
            if (data.get(index).compareTo(data.get(j)) >= 0){
                break;
            }
            data.swap(index, j);
            index = j;
        }
    }

堆還有一個(gè)replace操作世剖，取出最大值定罢，用另一個(gè)值替代，可以先輸出最大值旁瘫，然后再添加另一個(gè)值祖凫，但是這樣這樣復(fù)雜度就是〕甑剩可以直接用新的元素替換最大值惠况，然后做shiftDown操作即可。

    public E replace(E e) {
        E max = data.get(0);
        data.set(0, e);
        shiftDown(0);
        return max;
    }

如果存在一個(gè)數(shù)組宁仔，想要直接在數(shù)組上操作稠屠，使得這個(gè)數(shù)組直接變成一個(gè)堆，那就需要heapify操作了翎苫。從最后一個(gè)葉子節(jié)點(diǎn)開始不斷做shiftdown操作即可：

        for (int i = parent(this.data.getSize() - 1); i >= 0; i --){
            shiftDown(i);
        }

基于堆的優(yōu)先隊(duì)列就很簡單了完箩，出隊(duì)列的時(shí)候就直接extract最大值即可。

優(yōu)先隊(duì)列347

給定一個(gè)數(shù)組拉队，數(shù)組元素可以重復(fù)弊知，那么數(shù)字就會(huì)出現(xiàn)重復(fù)這個(gè)問題，在這種情況下粱快，就需要求出前N個(gè)頻率最高的元素秩彤，這就有點(diǎn)像優(yōu)先隊(duì)列了。先用Treemap把頻率存儲(chǔ)到樹里面事哭，然后放到優(yōu)先隊(duì)列里面輸出即可：

package Queue.Leecode347;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.TreeMap;

class Solution {

    private class Freq implements Comparable<Freq>{

        int e, freq;

        public Freq(int e, int freq){
            this.e = e;
            this.freq = freq;
        }

        @Override
        public int compareTo(Freq another) {
            if (this.freq < another.freq){
                return -1;
            }
            else if (this.freq > another.freq){
                return 1;
            }else {
                return 0;
            }
        }

    }

    public List<Integer> topKFrequent(int[] nums, int k) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int n : nums) {
            if (map.containsKey(n)) {
                map.put(n, map.get(n) + 1);
            } else {
                map.put(n, 1);
            }
        }

        PriorityQueue<Freq> priorityQueue = new PriorityQueue<>();
        for(int key: map.keySet()){
            if(priorityQueue.size() < k)
                priorityQueue.add(new Freq(key, map.get(key)));
            else if(map.get(key) > priorityQueue.peek().freq){
                priorityQueue.remove();
                priorityQueue.add(new Freq(key, map.get(key)));
            }
        }
        List<Integer> linkedList = new LinkedList<>();
        while (!priorityQueue.isEmpty()){
            linkedList.add(priorityQueue.remove().e);
        }
        return linkedList;
    }

    public static void main(String[] args) {
        int[] nums = {1,1,1,2,2,3};
        Solution solution = new Solution();
        System.out.println(solution.topKFrequent(nums, 2));
    }

}

并查集

之前包括前面博客所討論的樹問題都是樹問題漫雷，這些樹問題都是由父親指向孩子，而這個(gè)并查集是孩子指向樹鳍咱，可以由孩子找到跟節(jié)點(diǎn)降盹。并查集可以用來回答連接問題。給出兩個(gè)點(diǎn)谤辜，看看這兩個(gè)點(diǎn)是否是連接的蓄坏。前面博客提到的就是找到根然后比較兩個(gè)根是不是一樣的即可。這里的并查集主要實(shí)現(xiàn)兩個(gè)操作丑念，Union和isConnected涡戳，連接兩個(gè)節(jié)點(diǎn)和查看兩個(gè)節(jié)點(diǎn)是否是連接的。

并查集Quick Find

每個(gè)元素的下標(biāo)都會(huì)有一個(gè)標(biāo)記脯倚，如果標(biāo)記相同那么就是同一個(gè)類別渔彰，也就是連接在了一起嵌屎。一開始每一個(gè)數(shù)字就是一個(gè)類別，所以一開始下標(biāo)都是不一樣的恍涂。

    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p is out of range!");
        }
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot){
            return;
        }
        parent[pRoot] = qRoot;
    }

這種情況下的的查找復(fù)雜度是很快的宝惰，但是合并就很慢了，需要的復(fù)雜度再沧。

基于樹的Quick union

每一個(gè)節(jié)點(diǎn)都指向上一個(gè)節(jié)點(diǎn)尼夺，最后指向的就是根，根的parent就是他自己产园，如果根相同汞斧，那么這兩個(gè)節(jié)點(diǎn)就是相同的夜郁。

    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p is out of range!");
        }
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot){
            return;
        }
        parent[pRoot] = qRoot;
    }

合并的時(shí)候直接把根節(jié)點(diǎn)合并就好了什燕。但是這種合并有個(gè)弊端，如果合并的時(shí)候恰好把大的哪一組數(shù)據(jù)合并到了小的哪一組數(shù)據(jù)上竞端，就容易出現(xiàn)類似鏈表那樣長長的數(shù)據(jù)段屎即，這個(gè)時(shí)候就可以先做判斷，看看哪一邊的數(shù)據(jù)量大就把小數(shù)據(jù)的合并到大的一邊去即可事富。所以就需要一個(gè)記錄數(shù)量的數(shù)組技俐。

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        if (sz[pRoot] < sz[qRoot]) {
            parent[pRoot] = qRoot;
            sz[qRoot] += sz[pRoot];
        }else {
            parent[qRoot] = pRoot;
            sz[pRoot] += sz[qRoot];
        }
    }

其他都是一樣的。這樣其實(shí)不太嚴(yán)謹(jǐn)统台，如果數(shù)據(jù)都是分散開的雕擂，那么就應(yīng)該反著過來，所以應(yīng)該以高度作為對(duì)比的條件:

    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        if (rank[pRoot] < rank[qRoot]){
            parent[pRoot] = qRoot;
        }else if (rank[pRoot] > rank[qRoot]){
            parent[qRoot] = pRoot;
        }else {
            parent[qRoot] = pRoot;
            rank[pRoot] += 1;
        }

路徑壓縮 Path Compression

這種情況下就只需要指向父親的父親即可井赌，只要加上一行代碼就可以。

    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p is out of range!");
        }
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

哈希表HashTable

首先看一個(gè)簡單的問題：

返回第一個(gè)不重復(fù)的字符贵扰。最簡單的處理方式就是使用一個(gè)映射仇穗，先計(jì)算一遍所有字符的頻率是多少，然后再遍歷一遍所有的字符戚绕，看看第一個(gè)字符出現(xiàn)次數(shù)為一是索引下標(biāo)是多少即可纹坐。
但是這樣比較麻煩，我們可以使用一個(gè)數(shù)組包含了二十六個(gè)字母舞丛。

class Solution {
    public int firstUniqChar(String s) {
        int[] freq = new int[26];
        for (int i = 0; i < s.length(); i++) {
            freq[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            if (freq[s.charAt(i) - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }
}

在這個(gè)問題就隱藏著哈希表這種數(shù)據(jù)結(jié)構(gòu)耘子。上面的frequency數(shù)組就是一個(gè)哈希表，每一個(gè)字符都和一個(gè)索引對(duì)應(yīng)球切。數(shù)組的查找是支持下表操作的拴还，所有復(fù)雜度可以是的復(fù)雜度。哈希其實(shí)就是使用一個(gè)下標(biāo)來指示一個(gè)數(shù)值或者是字符欧聘，然后解決哈希沖突片林。簡單的來說，哈希就體現(xiàn)了用空間換時(shí)間的思想。
鍵通過哈希函數(shù)得到的索引分布越均勻越好费封。對(duì)于一些特殊的領(lǐng)域焕妙，有特殊領(lǐng)域的哈希函數(shù)設(shè)計(jì)方式甚至有專門的論文。
首先是整型哈希函數(shù)的設(shè)計(jì)弓摘，小范圍整數(shù)直接使用焚鹊，負(fù)整數(shù)就要進(jìn)行偏移。對(duì)于大整數(shù)韧献，就需要對(duì)這個(gè)大整數(shù)進(jìn)行處理末患，使得變成一個(gè)計(jì)算機(jī)可以處理的數(shù)據(jù)。常用的方法就是取模了锤窑。但是有時(shí)候取模使得分布不會(huì)有均勻的分布璧针，所以可以使用素?cái)?shù)作為取模數(shù)值。
對(duì)于字符串的處理渊啰，就需要轉(zhuǎn)成整型處理

hash沖突——鏈地址法

如果沒有沖突隧膏，那么就按照下標(biāo)直接存放，如果產(chǎn)生了沖突嚷那，也就是一個(gè)索引下有兩個(gè)相同的哈希值胞枕，那么就用鏈表把他們都串起來，如果還是有相同的那么繼續(xù)接上魏宽，所以每一個(gè)空間等于是存上了一個(gè)鏈表腐泻，也就是一個(gè)查找表，既然是查找表那么久不一定是鏈表了湖员，可以是樹結(jié)構(gòu)贫悄，紅黑樹二叉樹都可以。在Java8之前娘摔，一直都是一個(gè)位置對(duì)應(yīng)一個(gè)鏈表窄坦，Java8開始如果沖突達(dá)到了一定程度，也就是鏈表里面元素過多了凳寺，那么就會(huì)把每一個(gè)位置自動(dòng)轉(zhuǎn)成紅黑樹鸭津。因?yàn)槿绻跀?shù)據(jù)量少的情況下，使用鏈表查找是更加快的肠缨，因?yàn)闆]有紅黑樹的維護(hù)過程逆趋，而數(shù)據(jù)量多的時(shí)候就需要使用紅黑樹了。

public class Hash_Table<K, V> {
    private TreeMap<K, V>[] hashtable;
    private int M;
    private int size;

    public Hash_Table(int M) {
        this.M = M;
        size = 0;
        hashtable = new TreeMap[M];
        for (int i = 0; i < hashtable.length; i++) {
            hashtable[i] = new TreeMap<>();
        }
    }

    public Hash_Table() {
        this(97);
    }

    private int hash(K key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    public int getSize() {
        return size;
    }

    public void add(K key, V value) {
        if (hashtable[hash(key)].containsKey(key)) {
            hashtable[hash(key)].put(key, value);
        } else {
            hashtable[hash(key)].put(key, value);
            size++;
        }
    }

    public V remove(K key){
        TreeMap<K, V> treeMap = hashtable[hash(key)];
        V ret = null;
        if (treeMap.containsKey(key)){
            ret = treeMap.remove(key);
            size--;
        }
        return ret;
    }

    public void set(K key, V value){
        TreeMap<K, V> treeMap = hashtable[hash(key)];
        if (!treeMap.containsKey(key)){
            throw new IllegalArgumentException("no element!");
        }else {
            treeMap.put(key, value);
        }
    }

    public boolean contains(K key){
        return hashtable[hash(key)].containsKey(key);
    }

    public V get(K key){
        return hashtable[hash(key)].get(key);
    }
}

每一個(gè)位置都使用紅黑樹晒奕，插入的數(shù)據(jù)帶鍵值和數(shù)據(jù)闻书，根據(jù)鍵值取哈希值然后求余名斟。過程很簡單。如果插入的數(shù)據(jù)是N個(gè)魄眉，哈希表大小是M砰盐，如果每一個(gè)位置是鏈表的話，那么平均復(fù)雜度就是坑律，如果是平衡樹就是岩梳。可以看到這個(gè)復(fù)雜度并沒有如期望的那樣晃择，因?yàn)檫@是一個(gè)靜態(tài)數(shù)組冀值，當(dāng)N大于M的時(shí)候那么就會(huì)趨向N了，復(fù)雜度就會(huì)回到鏈表的查找宫屠。所以可以考慮使用動(dòng)態(tài)數(shù)組的方法進(jìn)行擴(kuò)展列疗。也就是讓M產(chǎn)生變化，當(dāng)N/M大于一定元素的時(shí)候就需要進(jìn)行擴(kuò)容激况，改變M了作彤，當(dāng)插入數(shù)據(jù)過少那么久可以縮榮膘魄。
首先就是要實(shí)現(xiàn)一個(gè)resize方法了：

    private void resize(int capacity){
        TreeMap<K, V>[] newHashTable = new TreeMap[capacity];
        for (int i = 0; i < capacity; i++) {
            newHashTable[i] = new TreeMap<>();
        }
        int oldM = this.M;
        this.M = capacity;
        for (int i = 0; i < oldM; i++) {
            TreeMap<K, V> treeMap = hashtable[i];
            for (K key : treeMap.keySet()){
                newHashTable[hash(key)].put(key, treeMap.get(key));
            }
        }

        this.hashtable = newHashTable;
    }

注意到M和新的M之間有一個(gè)陷阱乌逐，hash中用的是原來的M，而遍歷的時(shí)候要遍歷的是原來的M创葡，所以應(yīng)該要保存一份浙踢。之后就只需要在添加和移除兩個(gè)操作修改容量即可。
由于均攤復(fù)雜度是由決定的灿渴，所以復(fù)雜度是在洛波。但事實(shí)上這樣擴(kuò)容還有一個(gè)問題，乘上兩倍之后M就不是素?cái)?shù)了骚露，所以動(dòng)態(tài)擴(kuò)容的時(shí)候還需要選取素?cái)?shù)的問題蹬挤。
哈希表的均攤復(fù)雜度那么久接近于，很快棘幸，但是得到了什么就會(huì)失去了什么焰扳，這里哈希表久犧牲了順序性，樹結(jié)構(gòu)都是有順序性的误续，所以稍微慢一點(diǎn)吨悍。哈希表其實(shí)也是一個(gè)集合，有序集合可以用樹結(jié)構(gòu)作為底層數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)蹋嵌，無序集合可以用哈希表來實(shí)現(xiàn)育瓜。

hash沖突——開放地址法

如果遇到了沖突，那么就用線性探測的方法栽烂，加一看看有沒有空的躏仇，沒有繼續(xù)加一恋脚。但是這樣效率有時(shí)候是很低的，這里就可以采用類似計(jì)算機(jī)網(wǎng)絡(luò)里面的碰撞檢測方法焰手，平方探測慧起，一開始是1，又沖突了就4册倒，9蛇耀，16這樣既可延刘。另外還可以使用二次哈希的方法。

最后附上所有GitHub代碼：https://github.com/GreenArrow2017/DataStructure_Java