目录
1.简介
哈希表(Hash table，也叫散列表)，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数存放记录的数组叫做哈希表。可以当作缓存层存放数据。
2.
?2.链表代码:
package com.ws;
public class StudentLinkList {
//链表的头 默认为null
private Student head;
/**
* 添加学生 按照学号从小到大
* @param stu
*/
public void add(Student stu) {
//如果链表为空直接赋值
if (head == null) {
head = stu;
return;
}
//如果不为空按顺序加入
Student temp = head;
//标识学生是否已经存在
boolean flag = false;
while (true) {
//遍历到最后一个退出
if (temp.getNext() == null) {
break;
}
//找到 退出
if (temp.getNext().getNo() > stu.getNo()) {
break;
}
if (temp.getNext().getNo() == stu.getNo()) {
//表示该学号已经存在
flag = true;
}
temp = temp.getNext();
}
if (flag) {
System.out.println("学号为:"+stu.getNo()+"的学生已存在不能再添加~");
} else {
stu.setNext(temp.getNext());
temp.setNext(stu);
}
}
/**
* 按照学号查询学生信息
* @param no
* @return
*/
public Student queryStudentByNo(int no) {
if (head == null) {
// System.out.println("链表为空 无法查找~");
return null;
}
Student temp = head;
while (true) {
if (temp.getNo() == no) {
return temp;
}
if (temp.getNext() == null) {
break;
}
temp = temp.getNext();
}
return null;
}
/**
* 遍历链表
*/
public void list() {
if (head == null) {
System.out.println("链表为空~");
return;
}
Student temp = head;
while (true) {
System.out.print("学号" + temp.getNo() + "姓名" + temp.getName());
if (temp.getNext() == null) {
System.out.println();
break;
}
temp = temp.getNext();
System.out.print(" ==> ");
}
}
}
2.HashTable代码实现:
package com.ws;
public class HashTable {
//装链表的数组
private StudentLinkList[] linkLists;
//数组大小
private int size;
//构造器
public HashTable(int size) {
this.size = size;
linkLists = new StudentLinkList[size];
//初始化链表
for (int i = 0; i < size; i++) {
linkLists[i] = new StudentLinkList();
}
}
/**
* 散列函数 采用简单的取模法
* @param no
* @return
*/
public int hashFunction(int no) {
return no % size;
}
/**
* 通过散列函数
* @param student
*/
public void add(Student student) {
linkLists[hashFunction(student.getNo())].add(student);
}
/**
* 遍历哈希表 显示所有学生信息
*/
public void list() {
for (int i = 0; i < size; i++) {
System.out.print(i + "号链表:");
linkLists[i].list();
}
}
/**
* 按照学号查询学生信息
* @param no 学号
* @return
*/
public Student queryByNo(int no) {
//根据散列函数决定到那个数组链表里找
return linkLists[hashFunction(no)].queryStudentByNo(no);
}
}
4.测试功能代码
package com.ws;
import java.util.Scanner;
public class Test1 {
public static void main(String[] args) {
HashTable hashTable = new HashTable(7);
char key;
int no;
String name;
//写一个简单的菜单
Scanner scanner = new Scanner(System.in);
boolean loop = true;
while (loop) {
System.out.println("a : 添加学生信息");
System.out.println("s : 显示学生信息");
System.out.println("q : 按照学号查询");
System.out.println("e : 退出");
key = scanner.next().charAt(0);
switch (key) {
case 'a' :
System.out.println("请输入学号:");
no = scanner.nextInt();
System.out.println("请输入姓名:");
name = scanner.next();
Student stu = new Student();
stu.setNo(no);
stu.setName(name);
hashTable.add(stu);
break;
case 's' :
hashTable.list();
break;
case 'q' :
System.out.println("请输入你要查找学生的学号:");
no = scanner.nextInt();
Student stu1 = hashTable.queryByNo(no);
if (stu1 != null) {
System.out.print("学号" + stu1.getNo() + "姓名" + stu1.getName());
System.out.println();
} else {
System.out.print("在哈希表中，学号为" + no + "的学生没有找到~");
System.out.println();
}
break;
case 'e' :
loop = false;
break;
default:
break;
}
}
}
}
测试结果:
a : 添加学生信息
s : 显示学生信息
q : 按照学号查询
e : 退出
a
请输入学号:
1
请输入姓名:
ws
a : 添加学生信息
s : 显示学生信息
q : 按照学号查询
e : 退出
q
请输入你要查找学生的学号:
1
学号1姓名ws
a : 添加学生信息
s : 显示学生信息
q : 按照学号查询
e : 退出
a
请输入学号:
2
请输入姓名:
ls
a : 添加学生信息
s : 显示学生信息
q : 按照学号查询
e : 退出
a
请输入学号:
8
请输入姓名:
ww
a : 添加学生信息
s : 显示学生信息
q : 按照学号查询
e : 退出
s
0号链表:链表为空~
1号链表:学号1姓名ws ==> 学号8姓名ww
2号链表:学号2姓名ls
3号链表:链表为空~
4号链表:链表为空~
5号链表:链表为空~
6号链表:链表为空~
a : 添加学生信息
s : 显示学生信息
q : 按照学号查询
e : 退出
?