[数据结构与算法]哈希表的简单实现

学习目的：使用哈希函数去存储雇员信息，并实现查找，删除函数。
功能：

1. 插入
2. 查找
3. 删除
   哈希函数使用取余函数，哈希表的总长度可以在初始化时设置。
   下面是实现类和Test类，两个Java文件在一个包下就可以运行。

HashTable.java

package com.wyz.HashTable;

public class HashTable {
    private int size = 0;
    private EmpLinkedList[] list;

    public HashTable(int listSize) {
        this.size = listSize;
        list = new EmpLinkedList[listSize];
        for (int i = 0; i < size; i++) {
            list[i] = new EmpLinkedList();
        }
    }

    public void add(Emp emp) {
        int listNo = hash(emp.id);
        list[listNo].addEmp(emp);

    }

    //散列函数
    public int hash(int id) {
        return id % size;
    }

    public void showList() {
        for (int i = 0; i < size; i++) {
            list[i].showList(i);
        }
    }

    public void selectEmpById(int id) {
        int listNo = hash(id);
        Emp emp = list[listNo].selectEmpById(id);
        if (emp == null) {
            System.out.println("找不到该雇员");
        } else {
            System.out.println("在第" + listNo + "条链表中找到该雇员");
        }
    }
    
    public void deleteEmpById(int id) {
        int listNo = hash(id);
        list[listNo].deleteEmpById(id, listNo);
    }
}

// 雇员信息
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;

    public void addEmp(Emp emp) {
        //首次插入
        if (head == null) {
            head = emp;
            return;
        }

        Emp helpPoint = head;
        while (true) {
            //到达链表尾部，跳出循环，此时helpPoint指向尾结点。
            if (helpPoint.next == null) {
                break;
            }
            //指针后移
            helpPoint = helpPoint.next;
        }
        // 跳出循环时已经找到了插入位置，直接插入到链表尾部。
        helpPoint.next = emp;
    }

    
    //传入链表序号的目的是为了打印链表的序号信息
    public void showList(int listNo) {
        //空链表提示信息
        if (head == null) {
            System.out.println("第" + (listNo + 1) + "条链表为空");
            return;
        }
        //非空链表
        System.out.print("第" + (listNo + 1) + "链表的信息为=>");
        Emp currentPoint = head;
        while (true) {
            System.out.print(currentPoint);
            if (currentPoint.next == null) {
                break;
            } else {
                currentPoint = currentPoint.next;
            }
        }
        System.out.println();
    }

    
    public Emp selectEmpById(int id) {
        if (head == null) {
            System.out.println("链表为空");
            return null;
        }
        Emp helperPoint = head;
        while (true) {
            if (helperPoint.id == id) {
                break;
            }
            if (helperPoint.next == null) {
                helperPoint = null;
                break;
            }
            helperPoint = helperPoint.next;
        }
        return helperPoint;
    }

    public void deleteEmpById(int id, int listNo) {
        if (head == null) {
            System.out.println("链表为空,无法删除！");
            return;
        }
        Emp helperPoint = head;
        while (true) {
            // 寻找该雇员的位置

            // 该雇员在头结点的位置
            if (helperPoint.id == id) {
                head = head.next;
            } else if (helperPoint.next.id == id) {
                helperPoint.next = helperPoint.next.next;
                System.out.println("在第" + listNo + "条链表中该删除该雇员！");
                break;
            }
            if (helperPoint.next == null) {
                System.out.println("链表为空,无法删除！");
                break;
            }
            helperPoint = helperPoint.next;
        }
    }
}

HashTableTest.java

package com.wyz.HashTable;

import org.junit.Test;

public class HashTableTest {
    HashTable hashTable = new HashTable(7);
    
    @Test
    public void addTest() {
        hashTable.add(new Emp(3, "wyz"));
        hashTable.add(new Emp(0, "wzx"));
        hashTable.add(new Emp(7, "ysz"));
        hashTable.add(new Emp(4, "wan"));
        hashTable.showList();
    }
    

    @Test
    public void selectTest() {
        hashTable.add(new Emp(3, "wyz"));
        hashTable.add(new Emp(0, "wzx"));
        hashTable.add(new Emp(7, "ysz"));
        hashTable.add(new Emp(4, "wan"));
        hashTable.selectEmpById(56);
        hashTable.showList();
    }

    @Test
    public void deleteTest() {
        hashTable.add(new Emp(3, "wyz"));
        hashTable.add(new Emp(0, "wzx"));
        hashTable.add(new Emp(7, "ysz"));
        hashTable.add(new Emp(4, "wan"));
        hashTable.deleteEmpById(7);
        hashTable.showList();
    }
}