個人資料結構與算法學習總結-哈希表

哈希表

本總結主要是以“尚矽谷Java算法教程”的學習教程為主，加上一些個人的了解

什麼是哈希表

散清單（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行通路的資料結構。也就是說，它通過把關鍵碼值映射到表中一個位置來通路記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散清單。結構如下圖所示

實作

1、題目

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

2、代碼實作

package datastructure.hashTable;

import java.util.Scanner;

public class HashTableDemo {

    public static void main(String[] args) {

        //建立哈希表
        HashTab hashTab = new HashTab(7);

        //寫一個簡單的菜單
        String key = "";
        Scanner scanner = new Scanner(System.in);
        while(true) {
            System.out.println("add:  添加雇員");
            System.out.println("list: 顯示雇員");
            System.out.println("find: 查找雇員");
            System.out.println("exit: 退出系統");

            key = scanner.next();
            switch (key) {
                case "add":
                    System.out.println("輸入id");
                    int id = scanner.nextInt();
                    System.out.println("輸入名字");
                    String name = scanner.next();
                    //建立 雇員
                    Emp emp = new Emp(id, name);
                    hashTab.add(emp);
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "find":
                    System.out.println("請輸入要查找的id");
                    id = scanner.nextInt();
                    hashTab.findEmpById(id);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                default:
                    break;
            }
        }

    }
}
class HashTab{
    private EmpLinkedList[] empLinkedListArray;
    private int size; //表示有多少條連結清單
    //構造器
    public HashTab(int size) {
        this.size = size;
        //初始化empLinkedListArray
        empLinkedListArray = new EmpLinkedList[size];
        for(int i = 0; i < size; i++) {
            empLinkedListArray[i] = new EmpLinkedList();
        }
    }

    //添加雇員
    public void add(Emp emp) {
        //根據員工的id ,得到該員工應當添加到哪條連結清單
        int empLinkedListNO = hashFun(emp.id);
        //将emp 添加到對應的連結清單中
        empLinkedListArray[empLinkedListNO].add(emp);

    }
    //周遊所有的連結清單,周遊hashtab
    public void list() {
        for(int i = 0; i < size; i++) {
            empLinkedListArray[i].list(i);
        }
    }

    //根據輸入的id,查找雇員
    public void findEmpById(int id) {
        //使用散列函數确定到哪條連結清單查找
        int empLinkedListNO = hashFun(id);
        Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);
        if(emp != null) {//找到
            System.out.printf("在第%d條連結清單中找到 雇員 id = %d\n", (empLinkedListNO + 1), id);
        }else{
            System.out.println("在哈希表中，沒有找到該雇員~");
        }
    }

    //編寫散列函數, 使用一個簡單取模法
    public int hashFun(int id) {
        return id % size;
    }

}


//表示一個雇員
class Emp {
    public int id;
    public String name;
    public Emp next; //next 預設為 null
    public Emp(int id, String name) {
        super();
        this.id = id;
        this.name = name;
    }
}

//建立EmpLinkedList ,表示連結清單
class EmpLinkedList {
    //頭指針，執行第一個Emp,是以我們這個連結清單的head 是直接指向第一個Emp
    private Emp head; //預設null

    //添加雇員到連結清單
    //說明
    //1. 假定，當添加雇員時，id 是自增長，即id的配置設定總是從小到大
    //   是以我們将該雇員直接加入到本連結清單的最後即可
    public void add(Emp emp) {
        //如果是添加第一個雇員
        if(head == null) {
            head = emp;
            return;
        }
        //如果不是第一個雇員，則使用一個輔助的指針，幫助定位到最後
        Emp curEmp = head;
        while(true) {
            if(curEmp.next == null) {//說明到連結清單最後
                break;
            }
            curEmp = curEmp.next; //後移
        }
        //退出時直接将emp 加傳入連結表
        curEmp.next = emp;
    }

    //周遊連結清單的雇員資訊
    public void list(int no) {
        if(head == null) { //說明連結清單為空
            System.out.println("第 "+(no+1)+" 連結清單為空");
            return;
        }
        System.out.print("第 "+(no+1)+" 連結清單的資訊為");
        Emp curEmp = head; //輔助指針
        while(true) {
            System.out.printf(" => id=%d name=%s\t", curEmp.id, curEmp.name);
            if(curEmp.next == null) {//說明curEmp已經是最後結點
                break;
            }
            curEmp = curEmp.next; //後移，周遊
        }
        System.out.println();
    }

    //根據id查找雇員
    //如果查找到，就傳回Emp, 如果沒有找到，就傳回null
    public Emp findEmpById(int id) {
        //判斷連結清單是否為空
        if(head == null) {
            System.out.println("連結清單為空");
            return null;
        }
        //輔助指針
        Emp curEmp = head;
        while(true) {
            if(curEmp.id == id) {//找到
                break;//這時curEmp就指向要查找的雇員
            }
            //退出
            if(curEmp.next == null) {//說明周遊目前連結清單沒有找到該雇員
                curEmp = null;
                break;
            }
            curEmp = curEmp.next;//以後
        }

        return curEmp;
    }

}