哈希表基于數組和連結清單java資料結構篇

本章學習目錄

• 頁内目錄

  一，哈希表的介紹

  二，哈希表的圖解

  三，哈希表的連結清單部分

  四，哈希表的實作類

  五，結果測試與展示

一，哈希表的介紹

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

二，哈希表的圖解

三，哈希表的連結清單部分

• 節點類

public 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 + '\'' +
                '}';
    }
}

           

• 連結清單實作類

public class EmpLinkedList {
    //定義頭節點
    private Emp head;

    //添加雇員方法
    public void add(Emp emp){
        //二種情況：1.連結清單為空；2.連結清單有節點
        //1.連結清單為空
        if (head==null){
            head=emp;
            return;
        }
        //2.連結清單存在節點
        //定義一個輔助指針，找到連結清單的最後位置，再進行插入
        Emp temp=head;
        //通過while循環，找到最後
        while (temp.next!=null){
            temp=temp.next;
        }//循環退出時temp即為最後的節點
        //将新添的節點指派于最後節點的下一個
        temp.next=emp;
    }

    //周遊連結清單方法
    public void list(){
        if (head==null){
            System.out.println("該連結清單為空");
            return;
        }
        //輔助節點
        Emp temp=head;
        //通過while循環周遊
        System.out.print("該連結清單資訊為：");
        while (temp!=null){
            System.out.print("==>"+temp.id);
            temp=temp.next;
        }
        System.out.println();
    }
    
    //根據id查找方法
    public Emp findByid(int id){
        //三種情況：1.表為空；2.找到；3.周遊完了，還未找到
        //傳回兩種情況：1.null：沒有找到；2.找到！傳回該節點
        //1表為空
        if (head==null){
            return null;
        }
        //2找到
        //定義輔助節點
        Emp temp=head;
        //while循環周遊
        while (temp.id!=id){
            temp=temp.next;
            //周遊完了，還未找到
            if (temp==null){
                return null;
            }
        }
        return temp;
    }
}

           

四，哈希表的實作類

public class HashTab {
    //建立一個連結清單的數組
    EmpLinkedList[] empLinkedListArr;
    private int size;

    //構造方法，初始化數組大小
    public HashTab(int size) {
        this.size = size;
        empLinkedListArr=new EmpLinkedList[size];
        //很重要，初始化每個連結清單
        for (int i = 0; i <size ; i++) {
            empLinkedListArr[i]=new EmpLinkedList();
        }
    }

    //添加節點
    public void add(Emp emp){
        //确定添加到哪個連結清單，這裡寫一個散列函數hashFun
        int Arrnum=hashFun(emp.id);
        //将節點添加到對應的連結清單中
        empLinkedListArr[Arrnum].add(emp);
    }
    //散列函數
    private int hashFun(int id){
        return id%size;
    }

    //周遊哈希表
    public void list(){
        for (int i = 0; i <size ; i++) {
            empLinkedListArr[i].list();
        }
    }
    //查找
    public void findEmpBYId(int id){
        //得到在數組中的位置
        int empArr = hashFun(id);
        //獲得該節點
        Emp byid = empLinkedListArr[empArr].findByid(id);
        //判斷
        if (byid!=null){
            System.out.println(byid.toString());
        }else {
            System.out.println("沒有找到該節點");
        }
    }
}

           

五，結果測試展示

HashTab hashTab = new HashTab(7);
        Emp emp1=new Emp(7,"aa");
        Emp emp5=new Emp(14,"aa");
        Emp emp2=new Emp(8,"bb");
        Emp emp3=new Emp(9,"cc");
        Emp emp4=new Emp(10,"cc");
        hashTab.add(emp1);
        hashTab.add(emp2);
        hashTab.add(emp3);
        hashTab.add(emp4);
        hashTab.add(emp5);
        hashTab.list();
        System.out.println("-----------");
        hashTab.findEmpBYId(11);
        hashTab.findEmpBYId(10);
        hashTab.findEmpBYId(9);
        hashTab.findEmpBYId(8);
        hashTab.findEmpBYId(7);