本文共 6536 字，大约阅读时间需要 21 分钟。

1、基本结构与底层原理

2、应用实例

3、代码实现

1、单个节点的结构

/** * @author zhihua.li * @date 2021/2/10 - 8:28 **/public class Employee {       private Integer id;    private String name;    @Override    public String toString() {           return "Employee{" +                "id=" + id +                ", name='" + name + '\'' +                ", next=" + next +                '}';    }    public Integer getId() {           return id;    }    public void setId(Integer id) {           this.id = id;    }    public String getName() {           return name;    }    public void setName(String name) {           this.name = name;    }    public Employee getNext() {           return next;    }    public void setNext(Employee next) {           this.next = next;    }    private Employee next;    public Employee(Integer id, String name) {           this.id = id;        this.name = name;    }}

2、多个节点组成的链表结构

/** * @author zhihua.li * @date 2021/2/10 - 8:30 **/public class EmpLinkedList {       //    头指针，指向第一个Emloyee，不需要额外的头结点    private Employee head;    /*     * 将雇员添加到链表     * 假定当添加雇员时，直接添加到链表尾部     * */    public void add(Employee employee) {           //判断当前首节点是否为空，若为空则直接将结点添加到链表尾        if (head == null) {               head = employee;            return;        }//        首节点非空        Employee curEmp = head;        while (true) {               if (curEmp.getNext() == null) {                   break;            }//            找到当前链表的最后一个节点            curEmp = curEmp.getNext();        }        curEmp.setNext(employee);    }    /*     *   遍历列表     */    public void list(int no) {           if (head == null) {               System.out.println("第" + (no + 1) + "条链表为空");            return;        }//        链表非空        System.out.print("第" + (no + 1) + "条链表信息为");        Employee cur = head;        while (true) {               System.out.print(" -> id = " + cur.getId() + "，name = " + cur.getName() + "\t");            if (cur.getNext() == null) {                   break;            }            cur = cur.getNext();        }        System.out.println();    }    /*     * 根据指定id查找链表中元素     * */    public Employee getEmpById(Integer id) {           if (head == null) {               System.out.println("链表为空");            return null;        }        //辅助指针        Employee cur = head;        while(true){               if(cur.getId()==id){       //找到                break;            }            if(cur.getNext()==null){       //没找到                cur = null;            }            cur = cur.getNext();        }        return cur;    }}

3、多个链表组成的Hash表结构

/** * @author zhihua.li * @date 2021/2/10 - 8:43 * **/public class EmpHashTable {   //    定义一个链表数组    private EmpLinkedList[] empLinkedLists;//    定义链表数组的大小    private Integer size;    //    初始化HashTable    public EmpHashTable(Integer size) {           this.size = size;        empLinkedLists = new EmpLinkedList[size];//         初始化HashTable中的每个链表        for (int i = 0; i < size; i++) {               empLinkedLists[i] = new EmpLinkedList();        }    }    //    通过取模运算来求得新添加的emp应该放在哪个链表中    public int getPosition(Integer id) {           return id % size;    }    //    根据哈希表分配算法得到链表序号插入employee    public void add(Employee employee) {           int position = getPosition(employee.getId());        empLinkedLists[position].add(employee);    }    //    遍历哈希表中所有链表    public void list() {           System.out.println("当前链表信息为：");        for (int i = 0; i < size; i++) {   //            遍历到单个链表时，调用该链表的list方法来遍历该链表中的节点元素            empLinkedLists[i].list(i);        }    }    //    通过id获取元素位置    public void getEmpById(Integer id){   //        获取该id对应元素在哪个链表上        int position = getPosition(id);//        通过上一步获取到该元素对应的链表上是否存在id为指定值的元素节点        Employee emp = empLinkedLists[position].getEmpById(id);        if(emp != null){               System.out.println("在第"+(position+1)+"条链表中找到该雇员，其id为："+id);        }else{               System.out.println("在哈希表中未找到该雇员");        }    }}

4、测试

测试代码：

import org.junit.Test;import java.util.Scanner;/** * @author zhihua.li * @date 2021/2/10 - 8:58 **/public class EmpHashTableTest {       //    初始化一个长度为7的链表数组为Hash表    private EmpHashTable empHashTable = new EmpHashTable(7);    @Test    public void test() {   //        通过一个简单的菜单来测试HashTable的功能        String key = "";        Scanner scanner = new Scanner(System.in);        boolean loop = false;        while (!loop) {               System.out.println("===========================================================");            System.out.println("add:添加雇员");            System.out.println("list:显示雇员");            System.out.println("search:查找雇员");            System.out.println("exit:退出程序");            key = scanner.next();            switch (key) {                   case "add":                    System.out.print("请输入id：");                    int id = scanner.nextInt();                    System.out.print("请输入名字：");                    String name = scanner.next();                    Employee employee = new Employee(id, name);                    empHashTable.add(employee);                    break;                case "list":                    System.out.println("所有雇员信息如下：");                    empHashTable.list();                    break;                case "search":                    System.out.print("请输入要查找的id：");                    id = scanner.nextInt();                    empHashTable.getEmpById(id);                    break;                case "exit":                    scanner.close();                    loop = true;                    break;                default:                    System.out.println("您的输入有误，请重试！");                    break;            }        }        System.out.println("程序退出！");    }}

测试结果：

===========================================================add:添加雇员list:显示雇员search:查找雇员exit:退出程序请输入id：请输入名字：===========================================================add:添加雇员list:显示雇员search:查找雇员exit:退出程序请输入id：请输入名字：===========================================================add:添加雇员list:显示雇员search:查找雇员exit:退出程序请输入id：请输入名字：===========================================================add:添加雇员list:显示雇员search:查找雇员exit:退出程序所有雇员信息如下：当前链表信息为：第1条链表为空第2条链表为空第3条链表信息为 -> id = 2，name = zhangsan	第4条链表信息为 -> id = 10，name = lisi	 -> id = 234，name = wangwu	第5条链表为空第6条链表为空第7条链表为空===========================================================add:添加雇员list:显示雇员search:查找雇员exit:退出程序请输入要查找的id：在第3条链表中找到该雇员，其id为：2===========================================================add:添加雇员list:显示雇员search:查找雇员exit:退出程序程序退出！Process finished with exit code 0