哈希表介紹

一、什么是哈希表

1、哈希表也叫散串列，哈希表是一種資料結構，它提供了快速的插入操作和查找操作，無論哈希表總中有多少條資料，插入和查找的時間復雜度都是為O(1)，因為哈希表的查找速度非常快，所以在很多程式中都有使用哈希表，例如拼音檢查器，

2、哈希表也有自己的缺點，哈希表是基于陣列的，我們知道陣列創建后擴容成本比較高，所以當哈希表被填滿時，性能下降的比較嚴重，

3、哈希表是由鏈表和陣列組成的：

鏈表：增刪的效率極高，但是查詢的效率極低，

陣列：查詢效率極高，增刪效率低

所以哈希表中繼承了鏈表和陣列的優缺點，不僅查詢效率高，增刪效率也高

4、哈希表通過鍵值對的方式存盤資料，【key，value】，哈希表會通過散列函式/哈希函式將key轉換成對應的陣列下標，【采用 % 的方式】

二、哈希表的應用

通常資料都是放在資料庫中的，但是有一些資料不需要存放在資料庫中 ，太麻煩，那么就需要我們使用快取層
快取層一般有倆種：

快取產品或者自己寫一個快取層(也就是哈希表)

通過一個列子自己構建出哈希表：

看一個實際需求，google公司的一個上機題:

有一個公司,當有新的員工來報道時,要求將該員工的資訊加入(id,性別,年齡,住址..),當輸入該員工的id時,要求查找到該員工的 所有資訊.

要求: 不使用資料庫,盡量節省記憶體,速度越快越好

思路：

1、首先要求不使用資料庫，那么是能用一些快取產品用來存盤資料，所以需要構建一個哈希表

2、哈希表有陣列，鏈表組成，在鏈表中保存員工資料資訊，陣列中保存鏈表

代碼實作：

1、創建員工類：定義員工的屬性

//創建員工類
class Emp {
    int id ; // id
    String name; // 姓名
    String sex ; // 性別

    Emp next; //指向下一節點

    //構造器
    public Emp(int id, String name, String sex) {
        this.id = id;
        this.name = name;
        this.sex = sex;
    }

    @Override
    public String toString() {
        return "Emp{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", sex='" + sex + '\'' +
                '}';
    }
}

2、創建鏈表【如何創建之前有寫】

//創建鏈表
class LinkList {
    //頭結點
    Emp head = new Emp(0, "", "");

    //增加員工資訊
    public void add(Emp emp) {
        Emp temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = emp;
    }

    //根據ID查詢員工資訊
    public Emp findByID(int id) {
        if (head.next == null) {
            System.out.println("空鏈表");
            return null;
        }
        Emp temp = head;
        while (true) {
            if (temp.id == id) {
                break;
            }
            temp = temp.next;
        }
        return temp;
    }

    //遍歷員工資訊
    public void show() {
        if (head.next == null) {
            System.out.println("該鏈表沒有增加員工資訊");
            return;
        }
        Emp temp = head.next;
        while (true) {
            System.out.println("ID = " + temp.id + ", name = " + temp.name + ", 性別 = " + temp.sex);
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
    }

    //根據ID洗掉員工資訊
    public void del(int id) {
        if (head.next == null) {
            System.out.println("空鏈表");
            return;
        }
        boolean flag = false;
        Emp temp = head;
        while (true) {
            if (temp.next.id == id) { //找到洗掉節點
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
            System.out.println("洗掉成功");
        } else {
            System.out.println("沒有找到洗掉節點");
        }
    }
}

3、創建哈希表

//創建哈希表
class HashTable {
    //鏈表的個數
    int size;
    //arr[0]:第一個鏈表 arr[1]:第二個鏈表
    LinkList[] arr;

    public HashTable(int size) {
        this.size = size;
        arr = new LinkList[size];

        //初始化陣列中每個鏈表
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new LinkList();
        }
    }

    //散列函式--用來指明員工資訊保存在哪個鏈表中
    public int function(int id) {
        return id % size;
    }

    //增加
    public void add(Emp emp) {
        //增加的emp在 第 i 個鏈表中
        int i = function(emp.id);
        //增加到對應的鏈表中
        arr[i].add(emp);
    }

    //遍歷
    public void show() {
        for (int i = 0; i < size; i++) {
            arr[i].show();
        }
    }

    //通過id查詢資訊
    public Emp findByID(int id) {
        int i = function(id);
        return arr[i].findByID(id);
    }

    //洗掉
    public void del(int id) {
        int i = function(id);
        arr[i].del(id);
    }
}

public int function(int id) {
return id % size;
}

這是一個簡單的散列函式，哈希表通過這樣的一個函式將關鍵值轉換為對應的陣列下標，并將資料存入鏈表中

4、測驗

提供一個操作選單：

     HashTable hashTable = new HashTable(7);

        //寫一個簡單的選單
        String key = "";//接受用戶輸入
        Scanner scanner = new Scanner(System.in);
        boolean flag = true;
        while (flag) {
            System.out.println("輸入：a 表示增加員工資訊");
            System.out.println("輸入：l 表示遍歷員工資訊");
            System.out.println("輸入：e 表示退出程式");
            System.out.println("輸入：f 表示 通過ID獲取員工資訊");
            System.out.println("輸入：d 表示 通過ID洗掉員工資訊");
            System.out.print("請輸入關鍵字：");
            key = scanner.next();
            switch (key) {
                case "a":
                    System.out.println("請填寫增加的資料：");
                    System.out.print("請輸入ID：");
                    int id = scanner.nextInt();
                    System.out.print("請輸入姓名：");
                    String name = scanner.next();
                    System.out.print("請輸入性別：");
                    String sex = scanner.next();

                    Emp emp = new Emp(id, name, sex);
                    hashTable.add(emp);
                    break;
                case "l":
                    hashTable.show();
                    break;
                case "f":
                    System.out.print("請輸入要查找員工的ID:");
                    int id1 = scanner.nextInt();
                    Emp emp1 = hashTable.findByID(id1);
                    System.out.println(emp1);
                    break;
                case "d":
                    System.out.print("請輸入洗掉員工的ID:");
                    int id2 = scanner.nextInt();
                    hashTable.del(id2);
                    break;
                case "e":
                    scanner.close();
                    flag = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("您已經退出程式！");

測驗結果

輸入：a 表示增加員工資訊
輸入：l 表示遍歷員工資訊
輸入：e 表示退出程式
輸入：f 表示 通過ID獲取員工資訊
輸入：d 表示 通過ID洗掉員工資訊
請輸入關鍵字：a
請填寫增加的資料：
請輸入ID：1
請輸入姓名：張三
請輸入性別：男
輸入：a 表示增加員工資訊
輸入：l 表示遍歷員工資訊
輸入：e 表示退出程式
輸入：f 表示 通過ID獲取員工資訊
輸入：d 表示 通過ID洗掉員工資訊
請輸入關鍵字：a
請填寫增加的資料：
請輸入ID：2
請輸入姓名：李四
請輸入性別：女
輸入：a 表示增加員工資訊
輸入：l 表示遍歷員工資訊
輸入：e 表示退出程式
輸入：f 表示 通過ID獲取員工資訊
輸入：d 表示 通過ID洗掉員工資訊
請輸入關鍵字：l
該鏈表沒有增加員工資訊
ID = 1, name = 張三, 性別 = 男
ID = 2, name = 李四, 性別 = 女
該鏈表沒有增加員工資訊
該鏈表沒有增加員工資訊
該鏈表沒有增加員工資訊
該鏈表沒有增加員工資訊
輸入：a 表示增加員工資訊
輸入：l 表示遍歷員工資訊
輸入：e 表示退出程式
輸入：f 表示 通過ID獲取員工資訊
輸入：d 表示 通過ID洗掉員工資訊
請輸入關鍵字：f
請輸入要查找員工的ID:2
Emp{id=2, name='李四', sex='女'}
輸入：a 表示增加員工資訊
輸入：l 表示遍歷員工資訊
輸入：e 表示退出程式
輸入：f 表示 通過ID獲取員工資訊
輸入：d 表示 通過ID洗掉員工資訊
請輸入關鍵字：d
請輸入洗掉員工的ID:1
洗掉成功
輸入：a 表示增加員工資訊
輸入：l 表示遍歷員工資訊
輸入：e 表示退出程式
輸入：f 表示 通過ID獲取員工資訊
輸入：d 表示 通過ID洗掉員工信息
請輸入關鍵字：l
該鏈表沒有增加員工資訊
該鏈表沒有增加員工資訊
ID = 2, name = 李四, 性別 = 女
該鏈表沒有增加員工資訊
該鏈表沒有增加員工資訊
該鏈表沒有增加員工資訊
該鏈表沒有增加員工資訊
輸入：a 表示增加員工資訊
輸入：l 表示遍歷員工資訊
輸入：e 表示退出程式
輸入：f 表示 通過ID獲取員工資訊
輸入：d 表示 通過ID洗掉員工資訊
請輸入關鍵字：e
您已經退出程式！