資料結構系列第四部分：散列

1）文筆有限，如果發現部落格有書寫有誤的地方懇請讀者直言不諱，我一定會第一時間改正。

2）代碼的具體實作可以參考代碼中的注釋，如果由于注釋不清楚而不明白相應原理，可以與作者私聊。碼字不易，有興趣的小夥伴點個贊呗，大家互相學習。

3）本篇部落格為資料結構系列第四部分：散列，如需了解資料結構的其它部分，歡迎點選連結。

1. 資料結構系列緒論部分：為什麼需要資料結構
2. 資料結構系列第一部分：表
3. 資料結構系列第二部分：樹
4. 資料結構系列第三部分：圖
5. 資料結構系列第四部分：散列
6. 資料結構系列第五部分：遞歸
7. 資料結構系列第六部分：排序
8. 資料結構系列第七部分：查找

傳送門：

• 1 定義
• 2 為什麼需要散列這種資料結構
• 3 執行個體分析

1 定義

散清單（Hash table，也叫哈希表），是根據

Key-Value

而直接進行通路的資料結構。也就是說，它通過把

Key-Value

映射到表中一個位置來通路記錄，以加快查找的速度。

這個映射函數叫做散列函數，存放記錄的數組叫做哈希表。

2 為什麼需要散列這種資料結構

為什麼使用哈希表呢？在平常的資料管理中，我們常常将資料放在資料庫中，但資料庫實際上是一個硬碟，如果直接從 Java 程式向資料庫中存取資料的速度會比較慢，這個時候，我們有兩種方法來解決這個問題。

1. 使用現在的緩存産品，比如Redis或者Mencache；
2. 自己寫哈希表。

之是以這兩種方式方式會更快，是因為它們是存儲在記憶體中的，相比于硬碟，存取速度會更快。

哈希表（Hashtab）由以下部分組成，存放連結清單的數組，以及存放資料的連結清單，而資料存放的連結清單在資料中的索引則由散列函數得到。 圖解如下：

3 執行個體分析

執行個體：将某學校的學生資訊存入到某一資料結構中，資訊包括 id、姓名，實作該系統的增、查與周遊。要求: 不使用資料庫，速度越快越好。

思路分析：見上圖。

代碼實作：

import java.util.Scanner;

/**
 * 需求：利用哈希表（散清單）的方法來管理學生資訊，不使用資料庫的方式
 */
public class StudentManageWindow {
    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();
                    //建立 學生
                    Student student = new Student(id, name);
                    hashTab.add(student);
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "find":
                    System.out.println("請輸入要查找的id");
                    id = scanner.nextInt();
                    hashTab.findStudentById(id);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                default:
                    break;
            }
        }
    }
}


/**
 * 建立Hashtab 管理多條連結清單
 */
class Hashtab {
    private StudentLinkedList[] studentLinkedListArr;
    //表示有多少條連結清單
    private int size;

    //構造器
    public Hashtab(int size) {
        this.size = size;
        //初始化StudentLinkedList
        studentLinkedListArr = new StudentLinkedList[size];
        //這時不要忘了分别初始化每個連結清單
        for(int i = 0; i < size; i++) {
            studentLinkedListArr[i] = new StudentLinkedList();
        }
    }

    /**
     * 添加學生
     * @param student
     */
    public void add(Student student) {
        //根據員工的id ,得到該員工應當添加到哪條連結清單
        int studentID = hashFun(student.id);
        //将student添加到對應的連結清單中
        studentLinkedListArr[studentID].add(student);

    }
    /**
     *     周遊所有的連結清單,周遊hashtab
     */
    public void list() {
        for(int i = 0; i < size; i++) {
            studentLinkedListArr[i].list(i);
        }
    }
    /**
     * 根據輸入的id,查找雇員
     * @param id
     */
    public void findStudentById(int id) {
        //使用散列函數确定到哪條連結清單查找
        int studentID = hashFun(id);
        Student student = studentLinkedListArr[studentID].findStudentById(id);
        if(student != null) {//找到
            System.out.printf("在第%d條連結清單中找到 雇員 id = %d\n", (studentID + 1), id);
        }else{
            System.out.println("在哈希表中，沒有找到該雇員~");
        }
    }
    /**
     * 編寫散列函數, 使用一個簡單取模法
     * @param id
     * @return
     */
    public int hashFun(int id) {
        return id % size;
    }


}

/**
 *  描述：用于存放學生的連結清單
 *  頭指針，指向目前連結清單的第一個雇員（相當于都節點也放資料）
 */
class StudentLinkedList {
    //預設null
    private Student head;

    //添加雇員到連結清單
    //說明

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

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

    /**
     *  根據id查找學生。如果查找到，就傳回student, 如果沒有找到，就傳回null
     */
    public Student findStudentById(int id) {
        //判斷連結清單是否為空
        if(head == null) {
            System.out.println("連結清單為空");
            return null;
        }
        //輔助指針
        Student curStudent = head;
        while(true) {
            if(curStudent.id == id) {
                break;//這時curEmp就指向要查找的雇員
            }
            //說明周遊目前連結清單沒有找到該雇員。要在curStudent.next前寫，否則會報空指針錯誤
            if(curStudent.next == null) {
                curStudent = null;
                break;
            }
            curStudent = curStudent.next;
        }
        return curStudent;
    }
}

/**
 * 描述：表述基本的學生類
 */
class Student {
    public int id;
    public String name;
    //next 預設為 null
    public Student next; 
    public Student(int id, String name) {
        super();
        this.id = id;
        this.name = name;
    }
}