[[388064]]

 基本介紹

散列表(Hash Table，也叫哈希表),是根據(jù)關(guān)鍵碼值(Key Value)而直接進(jìn)行訪(fǎng)問(wèn)的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)，它通過(guò)把關(guān)鍵碼值映射到表中的一個(gè)位置來(lái)訪(fǎng)問(wèn)記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表

Google上機(jī)題

有一個(gè)公司，當(dāng)有新員工來(lái)報(bào)到時(shí)，要求將該員工的信息加入(id,性別，年齡，地址….)，當(dāng)輸入該員工的id時(shí)，要求查找該員工的所有信息。

要求：不使用數(shù)據(jù)庫(kù)，盡量節(jié)省內(nèi)存，速度越快越好。

package com.xie.hashtable; 
 
import java.util.Scanner; 
 
public class HashTableDemo { 
    public static void main(String[] args) { 
        //創(chuàng)建一個(gè)HashTab 
        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("delete:刪除雇員"); 
            System.out.println("exit:退出程序"); 
            key = scanner.next(); 
            switch (key) { 
                case "add": 
                    System.out.println("輸入id"); 
                    int id = scanner.nextInt(); 
                    System.out.println("輸入name"); 
                    String name = scanner.next(); 
                    Emp emp = new Emp(id, name); 
                    hashTab.add(emp); 
                    break; 
                case "list": 
                    hashTab.list(); 
                    break; 
                case "find": 
                    System.out.println("請(qǐng)輸入編號(hào)"); 
                    int no = scanner.nextInt(); 
                    hashTab.findEmpById(no); 
                    break; 
                case "delete": 
                    System.out.println("請(qǐng)輸入編號(hào)"); 
                    int deleteNo = scanner.nextInt(); 
                    hashTab.deleteEmpById(deleteNo); 
                    break; 
                case "exit": 
                    scanner.close(); 
                    System.exit(0); 
                    break; 
                default: 
                    break; 
            } 
        } 
    } 
} 
 
//創(chuàng)建哈希表，管理多條鏈表 
class HashTab { 
    private int size; 
    private EmpLinkedList[] empLinkedListArray; 
 
    public HashTab(int size) { 
        this.size = size; 
        empLinkedListArray = new EmpLinkedList[size]; 
        for (int i = 0; i < size; i++) { 
            empLinkedListArray[i] = new EmpLinkedList(); 
        } 
 
    } 
 
    //添加雇員 
    public void add(Emp emp) { 
        //根據(jù)員工的id，得到該員工應(yīng)當(dāng)添加到哪條鏈表 
        int empLinkedListNo = hashFun(emp.id); 
        //將emp添加到對(duì)應(yīng)的鏈表 
        empLinkedListArray[empLinkedListNo].add(emp); 
    } 
 
    //查找員工 
    public Emp findEmpById(int id) { 
        int no = hashFun(id); 
        Emp empById = empLinkedListArray[no].findEmpById(id); 
        if (empById == null) { 
            System.out.println("不存在id=" + id + "元素"); 
            return null; 
        } else { 
            System.out.println("存在id=" + id + ",name=" + empById.name); 
            return empById; 
        } 
    } 
 
    //刪除雇員 
    public void deleteEmpById(int id) { 
        int no = hashFun(id); 
        empLinkedListArray[no].deleteEmp(id); 
    } 
 
    //遍歷哈希表 
    public void list() { 
        for (int i = 0; i < size; i++) { 
            empLinkedListArray[i].list(i); 
        } 
    } 
 
    //編寫(xiě)散列函數(shù),使用簡(jiǎn)單的取模法 
    private int hashFun(int id) { 
        return id % size; 
    } 
 
} 
 
//表示雇員 
class Emp { 
    public int id; 
    public String name; 
    public Emp next; 
 
    public Emp(int id, String name) { 
        this.id = id; 
        this.name = name; 
    } 
 
    @Override 
    public String toString() { 
        return "Emp{" + 
                "id=" + id + 
                ", name='" + name + '\'' + 
                '}'; 
    } 
} 
 
//表示鏈表 
class EmpLinkedList { 
    //頭指針 
    private Emp head; 
 
    //添加雇員到鏈表 
    //說(shuō)明: 
    //1.當(dāng)添加雇員時(shí)，id時(shí)自增的，即id分配總是從小到大,因此我們將該雇員直接加到本鏈表的最后即可 
    public void add(Emp emp) { 
        //如果是添加第一個(gè)雇員 
        if (head == null) { 
            head = emp; 
        } else { 
            Emp curr = head; 
            while (true) { 
                if (curr.next == null) { 
                    break; 
                } 
                curr = curr.next; 
            } 
            curr.next = emp; 
        } 
    } 
 
    //遍歷 
    public void list(int no) { 
        if (head == null) { 
            System.out.println("第" + (no + 1) + "鏈表為空"); 
            return; 
        } 
        System.out.print("第" + (no + 1) + "鏈表信息為:"); 
        Emp curr = head; 
        while (true) { 
            if (curr != null) { 
                System.out.printf("=> id=%d,name=%s\t", curr.id, curr.name); 
                curr = curr.next; 
            } else { 
                break; 
            } 
        } 
        System.out.println(); 
    } 
 
    //根據(jù)id查找雇員 
    public Emp findEmpById(int id) { 
        if (head == null) { 
            System.out.println("鏈表為空"); 
            return null; 
        } 
        Emp temp = head; 
        while (temp != null) { 
            if (temp.id == id) { 
                return temp; 
            } 
            temp = temp.next; 
        } 
        return null; 
    } 
 
    //根據(jù)id刪除雇員 
    public void deleteEmp(int id) { 
        if (head == null) { 
            System.out.println("沒(méi)有id=" + id + "的雇員"); 
            return; 
        } 
        Emp curr = head; 
        boolean flag = false; 
        while (true) { 
            if (curr == null) { 
                break; 
            } 
            if (curr.next.id == id) { 
                flag = true; 
                break; 
            } 
            curr = curr.next; 
        } 
        if (flag) { 
            curr.next = curr.next.next; 
        } else { 
            System.out.println("沒(méi)有id=" + id + "的雇員"); 
        } 
    } 
 
} 

 【編輯推薦】