哈希表
解释
哈希表是一种根据关键码去寻找值的数据映射结构，该结构通过把关键码映射的位置去寻找存放值的地方
内存结构分析图
- 1、定义一个类为结点，存储的信息
- 2、定义链表的相关操作
- 3、定义一个数组存储多条链表
各个部分的分析
1、结点：
//定义链表的节点
class Student {
public int id;
public String name;
public String sex;
public Student next;//指向下一个节点
public Student(int id, String name, String sex) {
this.id = id;
this.name = name;
this.sex = sex;
}
}
2、定义链表
（这里和单链表不同的一点是头节点的初始化，在单链表中为了确定链表的开始位置，设置head结点不存储任何数据，只是用来确定链表开始的位置。在哈希表中，链表的头位置存储在数组中，为链表的开始，可以存储数据）
class linkList {
private Student head;//定义一个头节点，下一个指向为null
//增加操作
public void add(Student student) {
//1、当前链表为空，则直接将节点加在后边
if (head == null) {
head = student;
return;
}
Student temp = head;//定义辅助节点
while (true) {
if (temp.next == null) {
break;
}
temp = temp.next;//移动节点
}
temp.next = student;//将新的节点链接到链表尾
}
//遍历节点
public void list() {
if (head == null) {
System.out.println("链表为空");
return;
}
Student temp = head;
while (true) {
System.out.printf("==>id=%d name=%s sex=%s\t", temp.id, temp.name, temp.sex);
if (temp.next == null) {
break;
}
temp = temp.next;
}
System.out.println("");
}
//根据id查询某个学生的相关信息
public void getStudentById(int id){
if(head==null){
return;//当前链表没有
}
Student temp=head;//辅助节点
while (true){
if(temp.id==id){
System.out.println("id为"+id+"学生的信息为：id:"+temp.id+" 姓名："+temp.name+" 性别："+temp.sex);
break;
}
if(temp.next==null){
return;//该链表不存在
}
temp=temp.next;//指向下一个节点
}
}
}
3、定义储存多条链表
（注意的点：需要初始化每一条存储在数组中的链表。使用for循环）
class ArrayHashTable {
public int sizeMax;
public linkList[] hashtabl;
//初始化数组
public ArrayHashTable(int sizeMax) {
super();
this.sizeMax = sizeMax;
hashtabl = new linkList[this.sizeMax];
for (int i = 0; i < sizeMax; i++) {
hashtabl[i] = new linkList();
}
}
//添加数据
public void addArray(Student student) {
int index = fun(student.id);
hashtabl[index].add(student);
}
//定义一个散列函数
public int fun(int id) {
return id % 10;
}
//遍历哈希表
public void list1() {
for (int i = 0; i < hashtabl.length; i++) {
System.out.printf("当前第%d链表信息：", i + 1);
hashtabl[i].list();
}
}
//查询某个学生的id
public void getStudentById(int id){
for (int i = 0; i < sizeMax; i++) {
hashtabl[i].getStudentById(id);
}
}
}
代码实现
举例：
package com.zheng.demo6;
public class MyHashTable {
public static void main(String[] args) {
//定义几个节点
Student student1 = new Student(1, "小明", "女");
Student student2 = new Student(2, "小红", "女");
Student student3 = new Student(3, "小青", "女");
Student student4 = new Student(4, "小黑", "男");
Student student5 = new Student(5, "小刚", "男");
Student student6 = new Student(11, "李白", "男");
Student student7 = new Student(13, "张三", "男");
Student student8 = new Student(23, "李四", "男");
Student student9 = new Student(10, "麻子", "男");
ArrayHashTable hashTable = new ArrayHashTable(8);
hashTable.addArray(student1);
hashTable.addArray(student2);
hashTable.addArray(student3);
hashTable.addArray(student4);
hashTable.addArray(student5);
hashTable.addArray(student6);
hashTable.addArray(student7);
hashTable.addArray(student8);
hashTable.addArray(student9);
System.out.println("遍历哈希表");
hashTable.list1();
System.out.println("查询数据");
hashTable.getStudentById(23);
}
}
class ArrayHashTable {
public int sizeMax;
public linkList[] hashtabl;
//初始化数组
public ArrayHashTable(int sizeMax) {
super();
this.sizeMax = sizeMax;
hashtabl = new linkList[this.sizeMax];
for (int i = 0; i < sizeMax; i++) {
hashtabl[i] = new linkList();
}
}
//添加数据
public void addArray(Student student) {
int index = fun(student.id);
hashtabl[index].add(student);
}
//定义一个散列函数
public int fun(int id) {
return id % 10;
}
//遍历哈希表
public void list1() {
for (int i = 0; i < hashtabl.length; i++) {
System.out.printf("当前第%d链表信息：", i + 1);
hashtabl[i].list();
}
}
//查询某个学生的id
public void getStudentById(int id){
for (int i = 0; i < sizeMax; i++) {
hashtabl[i].getStudentById(id);
}
}
}
class linkList {
private Student head;//定义一个头节点，下一个指向为null
//增加操作
public void add(Student student) {
//1、当前链表为空，则直接将节点加在后边
if (head == null) {
head = student;
return;
}
Student temp = head;//定义辅助节点
while (true) {
if (temp.next == null) {
break;
}
temp = temp.next;//移动节点
}
temp.next = student;//将新的节点链接到链表尾
}
//遍历节点
public void list() {
if (head == null) {
System.out.println("链表为空");
return;
}
Student temp = head;
while (true) {
System.out.printf("==>id=%d name=%s sex=%s\t", temp.id, temp.name, temp.sex);
if (temp.next == null) {
break;
}
temp = temp.next;
}
System.out.println("");
}
//根据id查询某个学生的相关信息
public void getStudentById(int id){
if(head==null){
return;//当前链表没有
}
Student temp=head;//辅助节点
while (true){
if(temp.id==id){
System.out.println("id为"+id+"学生的信息为：id:"+temp.id+" 姓名："+temp.name+" 性别："+temp.sex);
break;
}
if(temp.next==null){
return;//该链表不存在
}
temp=temp.next;//指向下一个节点
}
}
}
//定义链表的节点
class Student {
public int id;
public String name;
public String sex;
public Student next;//指向下一个节点
public Student(int id, String name, String sex) {
this.id = id;
this.name = name;
this.sex = sex;
}
}
// public void add(Student student) {
// //1、当前链表为空，则直接将节点加在后边
// if (head == null) {
// head = student;
// }
// Student temp = head;//定义辅助节点
// while (true) {
// if (temp.next == null) {
// temp.next = student;
// break;//遍历到链表的尾部
// }
// temp = temp.next;//移动节点
// }
//
// }
