哈希表（对员工信息进行操作）Java代码实现

冷不防 2023-03-13 13:06 37阅读 0赞

➢ **基本介绍**  
散列表(Hash table，也叫哈希表)，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

➢ **实现问题**  
把员工的信息进行插入，不使用数据库，根据id进行查找员工的时候越快越好

➢ **思路分析图解**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]  
**代码实现**  
首先需要定义一个员工类，包含了id和姓名以及指向下一个节点的next指针：

class Emp { 
    	public int id;
    	public String name;
    	public Emp next;
    
    	public Emp(int id, String name) { 
    		super();
    		this.id = id;
    		this.name = name;
    	}
    }

多个员工类连成一起的链表类

//EmpLinkedList 员工链表，存放员工信息
    class EmpLinkedList { 
    	private Emp head = null;
    
    	// 添加信息
    	public void add(Emp emp) { 
    		// 添加的是第一个
    		if (head == null) { 
    			head = emp;
    			return;
    		}
    		// 不是第一个，定位到链表的最后
    		Emp curemp = head;
    		while (true) { 
    			if (curemp.next == null) { 
    				break;
    			}
    			curemp = curemp.next;
    		}
    		// 找到最后一个，直接添加上去
    		curemp.next = emp;
    	}
    
    	public void show(int no) { 
    		if (head == null) { 
    			System.out.println("第 " + (no + 1) + " 条链表为空");
    			return;
    		}
    		System.out.print("第 " + (no + 1) + " 条链表信息为： ");
    		Emp curemp = head;
    		while (true) { 
    			System.out.println("id:" + curemp.id + ", name:" + curemp.name);
    			if (curemp.next == null) { 
    				break;
    			}
    			curemp = curemp.next;
    		}
    		// System.out.println();
    	}
    	
    	// 根据id查找员工信息，
    	public Emp find(int id) { 
    		if (head == null) { 
    			System.out.println("链表为空，");
    			return null;
    		}
    		Emp curemp = head;
    		while (true) { 
    			if (curemp.id == id) { 
    				break;
    			}
    			if (curemp.next == null) { 
    				curemp = null;
    				break;
    			}
    			curemp = curemp.next;
    		}
    		return curemp;
    	}
    }

但在操作过程当中，我们是对数组进行操作，而不是对链表进行操作：

class HashTable { 
    	private EmpLinkedList[] ListArray;
    	private int size;
    
    	// 构造方法
    	public HashTable(int size) { 
    		// 初始化链表长度
    		ListArray = new EmpLinkedList[size];
    		// 创建的数组是一个空值，初始化每一条链表
    		for (int i = 0; i < size; i++) { 
    			ListArray[i] = new EmpLinkedList();
    		}
    
    		this.size = size;
    	}
    
    	// 添加
    	public void add(Emp emp) { 
    		// 根据员工的id判断添加到哪条链表
    		int EmpLinkedListNo = hashfun(emp.id);
    		// 加入到链表当中
    		ListArray[EmpLinkedListNo].add(emp);
    	}
    
    	// 遍历所有链表即遍历哈希表
    	public void show() { 
    		for (int i = 0; i < size; i++) { 
    			ListArray[i].show(i);
    		}
    	}
    
    	public void find(int id) { 
    		int EmpLinkedListNo = hashfun(id);
    		Emp emp = ListArray[EmpLinkedListNo].find(id);
    		if (emp != null) { 
    			System.out.println("在第 " + (EmpLinkedListNo + 1) + " 条链表上存在，id为：" + id);
    		} else { 
    			System.out.println("没有这个员工");
    		}
    	}
    
    	// 散列函数 取模法
    	public int hashfun(int id) { 
    		return id % size;
    	}
    }

最后定义测试：使用一个“菜单”

public static void main(String[] args) { 
    		// 创建哈希表
    		HashTable hashtable = new HashTable(7);
    
    		String key = " ";
    		Scanner sc = new Scanner(System.in);
    		while (true) { 
    			System.out.println("a : 添加员工");
    			System.out.println("s : 显示员工信息");
    			System.out.println("f : 查找员工");
    
    			System.out.println("e : 退出");
    
    			key = sc.next();
    			switch (key) { 
    			case "a":
    				System.out.println("输入id : ");
    				int id = sc.nextInt();
    				System.out.println("输入姓名 ：");
    				String name = sc.next();
    				// 创建员工
    				Emp emp = new Emp(id, name);
    				hashtable.add(emp);
    				break;
    			case "s":
    				hashtable.show();
    				break;
    			case "f":
    				System.out.println("输入id : ");
    				id = sc.nextInt();
    				hashtable.find(id);
    				break;
    			case "e":
    				System.exit(0);
    				break;
    			default:
    				System.out.println("输入有误！请重新输入。");
    				break;
    			}
    		}
    	}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]: /images/20230312/c6696b24e39a4302a1bb5875d9e04ec1.png