HashTa哈希表
哈希表也称为散列表，是根据关键码值（key value）而直接进行访问的数据结构。就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。下面就以一个通过哈希表管理链表的例子说明，此处的哈希表实质上就是一个数组，即用数组管理链表。
从Google的一道真题开始
- 看一个实际需求，google 公司的一个上机题:
- 有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址…),当输入该员工的id 时,要求查
找到该员工的所有信息. - 要求: 不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)
分析
所有员工在不考虑查找和存储开销的前提下是可以直接使用链表存储的，而每一个员工都可以看做是一个头结点。但是对于这种大型公司员工的数量多，员工信息庞杂，一条链表显然是不合理的，那么就可以考虑用哈希表管理。可以看成是将一条长链表分成几段，这些小链表组成一个数组就是哈希表，小链表（们）以及他们的每个节点与整个哈希表之间会有一个映射关系，方便直接定位查找，这个映射关系就是哈希函数，哈希函数的选择有很多种，这里我们选择的是取模函数（%）。
示图说明
单个员工、员工链表（小）以及哈希表之间的对应关系如图所示：
理解了这个图，就理解了最基本的哈希表的含义。这里使用的哈希函数是取模函数。具体的，已经定义了哈希表的长度size，根据员工的id号决定要将该员工存储在哪一个链表上:id%size。
代码
代码的实现和描述的顺序一致：定义员工类作为链表的节点，员工包括id、姓名等关键信息–>定义链表类，其中包括增删改查等操作–>用哈希表管理链表。
定义员工个体类
// 定义员工作为链表节点
class Emp {
public int id;
public String name;
public Emp next;
public Emp(int id, String name) {
super();
this.id = id;
this.name = name;
}
}
定义员工链表类
// 员工链表
class EmpLinkList {
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 list(int num) {
if (head == null) {
System.out.println("第 " + (num+1) + " 条链表为空!");
return;
}
Emp curEmp = head;
System.out.print("第 " + (num+1) + " 条链表的信息为: ");
while (true) {
System.out.printf("员工id = %d | 该员工姓名 = %s\t ", curEmp.id, curEmp.name);
if (curEmp.next == null) {
break;
}
curEmp = curEmp.next;
}
System.out.println();
}
// 按照id查找
public void findById(int id) {
if (head == null) {
System.out.println("未找到，因为该链表为空！");
return;
}
Emp curEmp = head;
while (true) {
if (curEmp.id == id) {
System.out.printf("找到id为%d的员工：%s", id, curEmp.name);
return;
}
if (curEmp.next == null) {
System.out.println("未找到该员工！");
return;
}
curEmp = curEmp.next;
}
}
}
定义HashTable类
// HashTable 管理链表的数组 关键是哈希函数 此处哈希函数为取模函数 %
class HashTable {
// 初始化链表
private int size;
private EmpLinkList[] empLinkListArray;
public HashTable(int size) {
super();
this.size = size;
empLinkListArray = new EmpLinkList[size];
for (int i = 0; i < size; i++) {
empLinkListArray[i] = new EmpLinkList();
}
}
// 哈希函数
public int hashFun(int id) {
return id % size;
}
// 添加雇员
public void add(Emp emp) {
empLinkListArray[hashFun(emp.id)].add(emp);
}
// 遍历并显示
public void list(){
for (int i = 0; i < size; i++) {
empLinkListArray[i].list(i);
}
}
// 查找雇员
public void find(int id) {
int arrayNum = hashFun(id);
empLinkListArray[arrayNum].findById(id);
}
}
测试代码
public class HashTableDemo {
public static void main(String[] args) {
HashTable hashTable = new HashTable(7);
String key = "";
Scanner scanner = new Scanner(System.in);
while(true) {
System.out.println();
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);
hashTable.add(emp);
break;
case "list":
hashTable.list();
break;
case "find":
System.out.println("请输入所查员工的id：");
id = scanner.nextInt();
hashTable.find(id);
break;
case "exit":
scanner.close();
System.exit(0);
default:
break;
}
}
}
}