一、思路
二、总结
看图说话,哈希表是由数组和单链表组成。
当创建一个引用类型的数组时,每个位置上的初始值都为null。所有得对数组进行初始化
添加节点时,需要根据哈希函数确定其数组中的位置。简单的哈希函数
no%array.leng
要使链表为有序链表。需要用到一个虚拟头结点去指向每个链表的头结点,然后在遍历比较
三、代码
/** * @Description 哈希表 数组+链表 * @Author Meng * @Versions * @Date 2021-07-21-15:27 */ public class HashTabDemo { 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(); //创建 雇员 Emp emp = new Emp(id, name); hashTab.add(emp); break; case "list": hashTab.list(); break; case "find": System.out.println("请输入要查找的id"); id = scanner.nextInt(); hashTab.findEmpById(id); break; case "exit": scanner.close(); System.exit(0); default: break; } } } } // 哈希表 class HashTab{ private EmpLinkedList[] empLinkedListArr; private int size; public HashTab( int size) { this.empLinkedListArr = new EmpLinkedList[size]; this.size = size; // 基本类型初始化为0,boolean类型为false 引用类型初始化为null // 所有这里得把EmpLikedList[]数组进行初始化 for (int i = 0; i < empLinkedListArr.length; i++) { empLinkedListArr[i] = new EmpLinkedList(); } } public void add(Emp emp){ int index = hashFun(emp.id); empLinkedListArr[index].addByOrder(emp); } public void list(){ for (int i = 0; i < empLinkedListArr.length; i++) { empLinkedListArr[i].list(); } } public void findEmpById(int id){ int index = hashFun(id); empLinkedListArr[index].find(id); } // hash函数,用于确定数组下标 private int hashFun(int id){ return id % size; } } // 链表 class EmpLinkedList{ private Emp head = null; public Emp getHead() { return head; } /** * 有序添加节点 * @param emp */ public void addByOrder(Emp emp){ // 创建一个虚拟节点 Emp virtualHeadNode = new Emp(0,null); virtualHeadNode.next= head;// 虚拟头结点指向hashTab 中的第一个节点 Emp current = virtualHeadNode;// 指向当前节点 while (true){ if (current.next == null){ current.next = emp; break; } // 若传进来的emp.id比temp.id小,那么久 if (emp.id < current.next.id){ emp.next = current.next; current.next = emp; break; } current = current.next; } head = virtualHeadNode.next; // 最后将virtualHeadNode指向的节点赋给head } /** * 遍历显示所有节点 */ public void list (){ if (head == null){ System.out.println("此链表没有节点!"); return; } if (head.next == null){ System.out.println("=>" + head.id + "," + head.name + " "); return; } Emp temp = head; while (true){ if (temp == null){ break; } System.out.print("=>" + temp.id + "," + temp.name + " "); temp = temp.next; } System.out.println(); } /** * 根据id查找节点 * @param id */ public void find(int id){ Emp temp = head; while (true){ if (temp == null){ System.out.println("没有找到id为[" + id +"]的节点"); break; } if (temp.id == id){ System.out.println(temp.id + "," + temp.name); break; } temp = temp.next; } } } // 节点 class Emp{ public int id; public String name; public Emp next; public Emp(int id, String name) { this.id = id; this.name = name; } public Emp() { } @Override public String toString() { return "Emp{" + "id=" + id + ", name='" + name + '\'' + ", next=" + next + '}'; } }