哈希表

傷城~ 2021-08-11 17:13 588阅读 0赞

【一】哈希表

> 他通过把关键码值映射到表中的一个位置来访问记录，以加快查找的速度。这个映射函数就是散列函数。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70][]

【二】哈希表的价值

相当于一个缓存区，将常用的加入哈希表，减少对数据库的操作。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70 1][]

【三】自己写的哈希表

import java.util.Scanner;
    
    public class HashTableTest {
    	//4.测试
    	public static void main(String[] args) {
    		Scanner sc=new Scanner(System.in);
    		StudentHashTab sht=new StudentHashTab(3);
    		String key="";
    		System.out.println("show:表示遍历栈");
    		System.out.println("exit:表示退出程序");
    		System.out.println("add:表示添加");
    		System.out.println("find:表示查询");
    		while(true) {
    			
    			key=sc.next();
    			switch(key) {
    			case "show":
    				sht.list();
    				break;
    			case "exit":
    				sc.close();
    				System.exit(0);
    			case "add":
    				System.out.println("请输入id：");
    				int id=sc.nextInt();
    				System.out.println("请输入name：");
    				String name=sc.next();
    				sht.add(new Student(id,name));
    				break;
    			case "find":
    				System.out.println("请输入id：");
    				int sid=sc.nextInt();
    				sht.findStudentById(sid);
    				break;
    			default:
    				break;
    			}
    		}
    	}
    }
    
    //3.HashTable=数组+链表
    class StudentHashTab{
    	//定义数组大小以及数组
    	private int size;
    	private StudentList[] slist;
    	
    	StudentHashTab(int size){
    		this.size=size;
    		slist=new StudentList[size];
    		//分别初始化每条链表
    		for(int i=0;i<size;i++) {
    			slist[i]=new StudentList();
    		}
    	}
    	
    	//添加元素
    	public void add(Student stu) {
    		int stuNo=hashFun(stu.id);
    		slist[stuNo].add(stu);
    	}
    	
    	//遍历数组
    	public void list() {
    		for(int i=0;i<size;i++) {
    			slist[i].list(i);;
    		}
    	}
    	
    	public void findStudentById(int id) {
    		int no=hashFun(id);
    		Student stu=slist[no].findStudentById(id);
    		if(stu!=null) {
    			System.out.printf("在哈希表第%d条链表中找到该学生信息，学生名字为%s",no,stu.name);
    		}else {
    			System.out.printf("在哈希表中没有找到id为%d该雇员信息",id);
    		}
    	}
    	
    	//添加散列函数
    	public int hashFun(int id) {
    		return id%size;
    	}
    }
    
    //2.链表
    class StudentList{
    	private Student head;
    	
    	//添加节点
    	public void add(Student stu) {
    		//如果链表为空，则直接在头结点之后添加元素
    		if(head==null) {
    			head=stu;
    			return;
    		}
    		//如果头结点不为空，遍历指针至尾节点，在尾节点后添加元素
    		Student temp=head;
    		while(true) {
    			if(temp.next==null) {
    				break;
    			}
    			temp=temp.next;
    		}
    		temp.next=stu;
    	}
    	
    	public Student findStudentById(int id) {
    		if(head==null) {
    			System.out.println("链表为空，没有学生信息");
    			return null;
    		}
    		Student temp=head;
    		//两种情况：1.找到学生，返回学生信息   2.没有该学生相关的信息
    		while(true) {
    			if(temp.id==id) {
    				break;
    			}
    			if(temp.next==null) {
    				temp=null;
    				break;
    			}
    			temp=temp.next;
    		}
    		return temp;
    	}
    	
    	//遍历链表
    	public void list(int no) {
    		if(head==null) {
    			System.out.println("第"+no+"链表为空");
    			return;
    		}
    		System.out.print("第"+no+"链表信息为：");
    		Student temp=head;
    		while(temp!=null) {
    			System.out.print("==>"+temp.id+"="+temp.name);
    			temp=temp.next;
    		}
    		System.out.println();
    	}
    }
    
    //1.节点
    class Student{
    	public int id;
    	public String name;
    	public Student next;
    	
    	Student(int id,String name){
    		this.id=id;
    		this.name=name;
    	}
    }

【四】代码部分输出示例

![20190913204130390.png][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70]: /images/20210811/aced0dacd21f45c7b29a0edf5951c17f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70 1]: /images/20210811/35824bcdae17431c80a640fefa119327.png
[20190913204130390.png]: /images/20210811/18c35beffeb842fe9cd856fc993bd031.png