哈希表-蒲公英云

哈希表

傷城~ 2021-08-11 17:13 738阅读 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;
    }
}