【笔记】数据结构与算法——哈希表

标签: 数据结构与算法  数据结构  java

哈希表

1.基本介绍

  • 散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,**它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。**这个映射函数叫做散列函数,存放记录的数组叫做散列表

2.应用举例

1)题目
  • 有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址…等),当输入员工的id时,要求查到到该员工的所有信息
  • 要求:不适用数据库,尽量节省内存,速度越快越好 ==> 哈希表
  • 添加时,保证按照id从低到高插入
2)分析
  • 使用链表来实现哈希表,该链表不带表头【即:链表的第一个结点就存放雇员信息】

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0KNYCLiA-1598192432012)(D:\Typora\img\哈希表举例.png)]

3)代码实现
package com.hashtab;
/*
@author qw
@date 2020/8/22 - 22:10
**/
import java.util.Scanner;
public class HashTabDemo {
    public static void main(String[] args) {
        HashTab hashTab = new HashTab(7);

        //菜单
        String key = "";
        Scanner sc = new Scanner(System.in);
        while (true) {
            System.out.println("add:添加雇员");
            System.out.println("find:查找雇员");
            System.out.println("del:删除雇员");
            System.out.println("show:显示雇员雇员");
            System.out.println("exit:退出系统雇员");

            key = sc.next();
            switch (key) {
                case "add":
                    System.out.println("输入id");
                    int id = sc.nextInt();
                    System.out.println("输入名字");
                    String name=sc.next();
                    System.out.println("输入年龄");
                    int age = sc.nextInt();
                    System.out.println("输入地址");
                    String address=sc.next();
                    //创建雇员
                    Emp emp = new Emp(id, name,age,address);
                    hashTab.add(emp);
                    break;
                case "find":
                    System.out.println("输入查找的雇员id");
                    id=sc.nextInt();
                    hashTab.findEmpById(id);
                    break;
                case "del":
                    System.out.println("输入删除的雇员id");
                    id=sc.nextInt();
                    hashTab.deleteEmpById(id);
                    break;
                case "show":
                    hashTab.show();
                    break;
                case "exit":
                    sc.close();
                    System.exit(0);
                default:
                    break;
            }
        }

    }
}

//创建HashTab 管理多条链表
class HashTab {
    private EmpLinkedList[] empLinkedListArray;
    private  int size;//表示有多少条链表
    //构造器
    public HashTab(int size) {
        this.size=size;
        //初始化empLinkedListArray
        empLinkedListArray = new EmpLinkedList[size];
        //分别初始化 每个链表
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i]=new EmpLinkedList();
        }
    }

    //添加雇员
    public void add(Emp emp) {
        //根据员工id,得到该员工应该添加到哪条链表
        int empLinkedListNO = hashFun(emp.id);
        //将emp添加到对应的链表中
        empLinkedListArray[empLinkedListNO].add(emp);
    }

    //遍历所有的链表 即遍历哈希表
    public void show() {
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i].show(i);
        }
    }

    //根据输入的id 查找雇员
    public void findEmpById(int id) {
        int empLinkedListNO = hashFun(id);
        Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);
        if (emp != null) {
            System.out.printf("在第%d条链表中找到雇员id=%d\n",(empLinkedListNO+1),id);
        } else {
            System.out.println("在哈希表中,没有找到该雇员");
        }
    }

    //根据输入的id删除雇员
    public void deleteEmpById(int id) {
        int empLinkedListNO = hashFun(id);
        int i = empLinkedListArray[empLinkedListNO].deleteEmpById(id);
        if (i > 0) {
            System.out.println("已删除编号为" + id + "的雇员");
        } else {
            System.out.println("编号为"+id+"的雇员不存在,无法删除");
        }

    }

    //编写散列函数 使用 取模法
    public int hashFun(int id) {
        return id % size;
    }
}
//表示一个雇员
class Emp {
    public int id;
    public String name;
    public int age;
    public String address;
    public Emp next;//默认为null

    public Emp(int id, String name,int age,String address) {
        super();
        this.id = id;
        this.name = name;
        this.age=age;
        this.address=address;
    }
}

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

    //添加雇员到链表
    //说明:
    //1.假定雇员添加时,id是自增长,即id的分配总是从小到大
    public void add(Emp emp) {
        //如果是添加第一个雇员
        if (head == null) {
            head = emp;
            return;
        }
        //如果不是第一个雇员,则使用一个辅助指针定位到最后
        Emp curEmp = head;
        while (curEmp.next != null) {
            curEmp=curEmp.next;
        }
        curEmp.next = emp;
    }

    //遍历链表的雇员信息
    public void show(int no) {
        if (head == null) {
            System.out.println("第"+(no+1)+"条链表为空");
            return;
        }
        System.out.print("第"+(no+1)+"条链表的信息为:");
        Emp curEmp = head;
        while (true) {
            System.out.printf(" => id=%d name=%s age=%d address=%s\t", curEmp.id, curEmp.name,curEmp.age,curEmp.address);
            if (curEmp.next == null) {
                break;
            }
            curEmp = curEmp.next;
        }
        System.out.println();
    }

    //根据id查找雇员
    public Emp findEmpById(int id) {
        //判断链表是否为空
        if (head == null) {
            System.out.println("链表为空");
            return null;
        }
        Emp curEmp=head;
        while (true) {
            if (curEmp.id == id) {
                break;//此时curEmp指向查找的雇员
            }
            //退出
            if (curEmp.next == null) {//当前链表没有找到该雇员
                curEmp = null;
                break;
            }
            curEmp = curEmp.next;
        }
        return curEmp;
    }

    //根据id删除雇员
    public int deleteEmpById(int id) {
        //判断链表是否为空
        if (head == null) {
            System.out.println("链表为空");
            return -1;
        }
        Emp curEmp=head;
        if (curEmp.id == id) {//若首结点即为需删除结点
            head = curEmp.next; //head后移
            return 1;
        } else { //遍历中间结点
            Emp temp=curEmp.next; //temp指向需删除结点,curEmp作为删除结点的前一结点,方便删除
            while (temp != null) {
                if (temp.id == id && temp.next == null) { //若尾结点为需删除结点
                    curEmp.next = null; //删除结点的前一结点的next置为null
                    return 1;
                }
                if (temp.id == id) {
                    curEmp.next = temp.next;
                   return 1;
                }
                curEmp = curEmp.next;
                temp = curEmp.next;
            }
            return -1;
        }
    }
}
版权声明:本文为Gu_jiaguaren原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Gu_jiaguaren/article/details/108189820

智能推荐

Python学习练习6----列表、字典的运用2

range 用法参见http://blog.csdn.net/chiclewu/article/details/50592368 直接在 在线编程工具中练习: https://www.tutorialspoint.com/execute_python_online.php 代码如下,增加range、列表的len()、字典的items()函数,for 函数也有了新变化 练习2: 2的运行结果,注意p...

PoolThreadCache

缓存构成   PoolThreadCache的缓存由三部分构成:tiny、small 和 normal。 tiny   缓存数据大小区间为[16B, 496B]数据,数组长度为32,根据数据大小计算索引的办法:数据大小除以16,如下代码所示: small   缓存数据大小区间为[512B, 4KB]数据,数组长度为4,根据数据大小计算索引的办法:数据大小除以512,然后log2得到指数,如下代码所...

Intellij IDEA 搭建Spring Boot项目(一)

Intellij IDEA 搭建Spring Boot项目 标签(空格分隔): SpringBoot JAVA后台 第一步 选择File –> New –> Project –>Spring Initialer –> 点击Next  第二步 自己修改 Group 和 Artif...

CentOS学习之路1-wget下载安装配置

参考1: https://blog.csdn.net/zhaoyanjun6/article/details/79108129 参考2: http://www.souvc.com/?p=1569 CentOS学习之路1-wget下载安装配置 1.wget的安装与基本使用 安装wget yum 安装软件 默认安装保存在/var/cache/yum ,用于所有用户使用。 帮助命令 基本用法 例子:下载...

深入浅出Spring的IOC容器,对Spring的IOC容器源码进行深入理解

文章目录 DispatcherServlet整体继承图 入口:DispatcherServlet.init() HttpServletBean.init() FrameworkServlet.initServletBean() 首先大家,去看Spring的源码入口,第一个就是DispatcherServlet DispatcherServlet整体继承图 入口:DispatcherServlet....

猜你喜欢

laravel框架的课堂知识点概总

1. MVC 1.1 概念理解 MVC全名是Model View Controller,是模型(model)-视图(view)-控制器(controller)的缩写,一种软件设计典范,用一种业务逻辑、数据、界面显示分离的方法组织代码,将业务逻辑聚集到一个部件里面,在改进和个性化定制界面及用户交互的同时,不需要重新编写业务逻辑 MVC 是一种使用 MVC(Model View Controller ...

Unity人物角色动画系统学习总结

使用动画系统控制人物行走、转向、翻墙、滑行、拾取木头 混合树用来混合多个动画 MatchTarget用来匹配翻墙贴合墙上的某一点,人物以此为支点翻墙跳跃 IK动画类似于MatchTarget,控制两只手上的两个点来指定手的旋转和位置,使得拾取木头时更逼真 创建AnimatorController: 首先创建一个混合树,然后双击 可以看到该混合树有五种状态机,分别是Idle、WalkForward、...

Composer 安装 ThinkPHP6 问题

Composer 安装 ThinkPHP6 问题 先说说问题 一.运行环境要求 二.配置 参考: ThinkPHP6.0完全开发手册 先说说问题 执行ThinkPHP6的安装命令 遇到问题汇总如下: 看提示是要更新版本,执行命令更新。 更新之后,再次安装ThinkPHP,之后遇到如下问题。 尝试了很多方法,依然不能解决。其中包括使用https://packagist.phpcomposer.com...

Spring Boot 整合JDBC

今天主要讲解一下SpringBoot如何整合JDBC,没啥理论好说的,直接上代码,看项目整体结构 看一下对应的pom.xml 定义User.java 定义数据源配置,这里使用druid,所以需要写一个配置类 上面指定druid的属性配置,和用户登录的账号信息以及对应的过滤规则: 下面定义数据访问接口和对应的实现: 数据访问层很简单,直接注入JdbcTemplate模板即可,下面再看对应的servi...

html鼠标悬停显示样式

1.显示小手:     在style中添加cursor:pointer 实现鼠标悬停变成小手样式     实例:         其他参数: cursor语法: cursor : auto | crosshair | default | hand | move | help | wait | tex...