死磕数据结构与算法——哈希表（java实现）。才疏学浅，如有错误，及时指正

死磕数据结构与算法——哈希表（java实现）。才疏学浅，如有错误，及时指正

• 1. 什么是哈希表？
• 2. 示意图
• 3. 功能详解
• 4. 示意代码
• 总结

1. 什么是哈希表？

哈希表是一种数据结构。
散列表（也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

2. 示意图

3. 功能详解

1. 哈希表的构造

形式：数组+链表
创建一个数组，数组中的值为一个链表。初始化数组时，还要使用一个循环来初始化每一条链表。

2. 功能（看代码中的注释，都与链表的操作类似）

4. 示意代码

package HashTab;

import java.util.Hashtable;
import java.util.Scanner;

public class HashTabDemo {
    public static void main(String[] args) {
        //创建哈希表
        HashTab hashtab = new HashTab(7);

        //测试
        String key = "";
        Scanner in = new Scanner(System.in);
        while(true){
            System.out.println("add:添加学生");
            System.out.println("list:显示学生");
            System.out.println("find:查找学生");
            System.out.println("exist:退出");
            
            key = in.next();
            switch (key){
                case "add":
                    System.out.println("输入id");
                    int id = in.nextInt();
                    System.out.println("输入名字");
                    String name = in.next();
                    //创建雇员
                    Stu stu = new Stu( id, name );
                    hashtab.add(stu);
                    break;
                case "list":
                    hashtab.list();
                    break;
                case "find":
                    System.out.println("请输入要查找的id");
                    id = in.nextInt();
                    hashtab.findStuById(id);
                    break;
                case "exit":
                    in.close();
                    System.exit(0);
                default:
                    break;
            }
        }
    }

}

/**
 * 定义学生
 * id为编号
 * name为学生姓名
 */
class Stu {
    public int id;
    public String name;
    public Stu next; //next默认为空

    public Stu(int id, String name) {
        super();
        this.id = id;
        this.name = name;
    }
}

/**
 * 创建HashTab,用来管理多条链表
 */
class HashTab {
    private EmpLinkedList[] empLinkedListArray; //创建多条链表数组
    public int size;  //表示共有多少条链表

    //构造器
    public HashTab(int size){
        //初始化
        this.size = size;
        empLinkedListArray = new EmpLinkedList[size]; //初始化数组
        //分别初始化每一条链表
        for (int i = 0; i < size ; i++) {
            empLinkedListArray[i] = new EmpLinkedList();
        }
    }
    //添加学生
    public void add(Stu stu) {
        //根据员工的id，得到该员工应当添加到哪条链表
        int stuLinkedListNo = hashfun( stu.id );
        //将emp添加到对应的链边中
        empLinkedListArray[stuLinkedListNo].add( stu );
    }

    //遍历所有的链表，遍历hashTab
    public void list(){
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i].list(i); //调用链表的list方法，遍历。
        }
    }

    //根据输入的id查找雇员
    public void findStuById(int id){
        //使用散列函数确认在哪条链表种查找
        int stuLinkedListNo = hashfun( id );
        Stu stu = empLinkedListArray[stuLinkedListNo].findStuById( id );
        if(stu != null){
            //找到
            System.out.printf( "在第%d条链表中找到 学生id = %d\n",stuLinkedListNo + 1, id );
        }else{
            System.out.println("在哈希表中，没有找到该学生~");
        }
    }

    //编写散列函数，使用简单的取模法
    public int hashfun(int id) {
        return id % size;
    }
}


/**
 * 创建EmpLinkedList,表示链表
 */
class EmpLinkedList{
    //头指针，执行第一个Stu，因此我们这个链表的head，是直接指向第一个Stu
    private Stu head; //默认为空

    /**
     * 添加学生到链表
     *     说明:
     *          假定当添加学生时，id是自增长的，即id的分配是从小到大
     *     因为我们将该学生加入到本链表的最后即可
     * @param stu
     */
    public void add(Stu stu){
        //如果是添加第一个雇员
        if(head == null){
            head = stu;
            return;
        }
        //如果不是第一个雇员，则使用一个辅助的指针curStu，帮助定位到最后
        Stu curStu = head;
        while(true){
            if(curStu.next == null){ //说明链表到最后
               break; //退出while循环
            }
            curStu = curStu.next; //后移
        }
        //退出时说明已经到了当前链表最后，直接将emp加入到链表
        curStu.next = stu;
    }

    /**
     * 遍历雇员的信息
     */
    public void list(int no){
        if(head == null){ //说明链表为空
            System.out.println("第" + (no + 1) + "条链表为空");
            return;
        }
        System.out.print("第" + (no + 1) + "条链表为");
        Stu curStu = head; //辅助指针
        while(true) {
            //输出当前节点的信息
            System.out.printf("=> id = %d name=%s\t",curStu.id, curStu.name);
            if(curStu.next == null){
                //说明curEmp已经是最后节点
                break;  //退出循环
            }
            //指针后移
            curStu = curStu.next;
        }
        System.out.println();
    }

    /**
     * 根据id查找学生
     * @param id
     * @return
     */
    public Stu findStuById(int id){
        //判断链表是否为空
        if(head == null){
            System.out.println("链表为空");
            return null;
        }
        //辅助指针
        Stu curStu = head;
        while(true){
            if(curStu.id == id){
                //找到了
                break;  //curStu就指向要查找的雇员
            }
            //退出
            if(curStu.next == null){
                //没找到该雇员
                curStu = null;
                break;
            }
            curStu = curStu.next;
        }
        return curStu;
    }
}

总结

该文章通过数组+链表的形式实现了一个最基本的哈希表操作，完全了对哈希表的插入，遍历，查找的操作。通过学习，对哈希表这个数据结构有了更深一步的认识。

本文地址：https://blog.csdn.net/qq_41497756/article/details/109254482