数据结构与算法学习十五:哈希表

文章目录

  • 前言
  • 一、应用实例
  • 二、哈希表基本介绍
  • 三、思路分析
  • 四、代码实现
    • 4.1Employee.java 雇员实体类
  • 4.2 EmployeeLinkedList.java 链表类
  • 4.3 HashTable.java 哈希表
  • 4.5 HashTableMain.java测试类

前言

一、应用实例

google公司的一个上机题:
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址…),当输入该员工的id时,要求查找到该员工的 所有信息.

要求: 不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)

二、哈希表基本介绍

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

 
 

三、思路分析

  • 要求

1、 不使用数据库,速度越快越好=>哈希表(散列);
2、 添加时,保证按照id从低到高插入[课后思考:如果id不是从低到高插入,但要求各条链表仍是从低到高,怎么解决?];
3、 使用链表来实现哈希表,该链表不带表头[即:链表的第一个结点就存放雇员信息];
4、 思路分析并画出示意图;
 

四、代码实现

4.1Employee.java 雇员实体类

package com.feng.ch11_hashtab;

/*
* 表示一个雇员
* */
public class Employee {
   
     

    private int id;
    private String name;
    private String sex;
    private int age;

    private Employee next; // 默认为空

    public Employee(int id, String name, String sex, int age) {
   
     
        this.id = id;
        this.name = name;
        this.sex = sex;
        this.age = age;
    }

    @Override
    public String toString() {
   
     
        return "Employee{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", sex='" + sex + '\'' +
                ", age=" + age +
                '}';
    }

    public int getId() {
   
     
        return id;
    }

    public void setId(int id) {
   
     
        this.id = id;
    }

    public String getName() {
   
     
        return name;
    }

    public void setName(String name) {
   
     
        this.name = name;
    }

    public String getSex() {
   
     
        return sex;
    }

    public void setSex(String sex) {
   
     
        this.sex = sex;
    }

    public int getAge() {
   
     
        return age;
    }

    public void setAge(int age) {
   
     
        this.age = age;
    }

    public Employee getNext() {
   
     
        return next;
    }

    public void setNext(Employee next) {
   
     
        this.next = next;
    }
}

4.2 EmployeeLinkedList.java 链表类

package com.feng.ch11_hashtab;

/*
 * 表示链表
 * */
public class EmployeeLinkedList {
   
     
    public static void main(String[] args) {
   
     
        EmployeeLinkedList employeeLinkedList = new EmployeeLinkedList();
        Employee employee01 = new Employee(1, "小刘", "男", 12);

        employeeLinkedList.addEmployee(employee01);

        employeeLinkedList.list(1);
    }

    // 头指针,执行第一个 Employee ,因此我们这个链表的 head 是直接指向第一个 Employee
    private Employee head;

    public Employee getHead() {
   
     
        return head;
    }

    /*
     * 添加
     * 说明:
     * 1、假定当添加雇员时,id 是自增的,即 id的分配总是从小到大
     * 2、因此我们将该雇员直接加入到本链表的最后即可。
     * */
    public void addEmployee(Employee employee) {
   
     
        // 如果是添加第一个雇员
        if (head == null) {
   
     
            head = employee;
            return;
        }
        // 如果不是第一个雇员,则使用一个辅助指针,帮助定位到最后
        Employee temp = head;
        while (true) {
   
     
            if (temp.getNext() == null) {
   
     
                break;
            }
            temp = temp.getNext();
        }
        // 添加雇员
        temp.setNext(employee);
    }

    /*
     * 遍历
     * */
    public void list(int no) {
   
     
        if (head == null) {
   
      // 说明链表为空
            System.out.println("第" + (no+1) + "条链表为空");
            return;
        }
        // 使用辅助指针 帮助遍历
        Employee temp = head;
        System.out.print("第" + (no+1) + "条链表信息为:");
        while (true) {
   
     
            System.out.printf("=>id=%d name=%s sex=%s age=%d\t", temp.getId(), temp.getName(), temp.getSex(), temp.getAge());
            if (temp.getNext() == null) {
   
     
                break;
            }
            temp = temp.getNext();
        }
        System.out.println();
    }

    /*
    * 根究 id 查找雇员
    * 如果查找到,就返回 employee ,如果没有找到,就返回 null
    * */
    public Employee findEmployeeById(int id){
   
     
        // 判断链表是否为空
        if (head == null){
   
     
            System.out.println("链表为空");
            return null;
        }
        Employee temp = head;
        while (true){
   
     
            if (temp.getId() == id){
   
      // 找到
                break;
            }
            if (temp.getNext() == null){
   
      // 没有找到
                temp = null;
                break;
            }
            temp = temp.getNext();
        }
        return temp;
    }
}

4.3 HashTable.java 哈希表

package com.feng.ch11_hashtab;
/*
 * 创建 HashTable 管理多条链表
 * */
public class HashTable {
   
     

    private EmployeeLinkedList[] employeeLinkedListArray;
    private int size; // 表示共有多少条链表

    // 构造器
    public HashTable(int size) {
   
     
        this.size = size;
        // 初始化 employeeLinkedListArray
        this.employeeLinkedListArray = new EmployeeLinkedList[size];
        // 留一个坑,这样能不能用这个链表数组?
        // 这时不要忘记分别初始化每个链表
        // 好好想一想
        for (int i = 0; i < size; i++) {
   
     
            employeeLinkedListArray[i] = new EmployeeLinkedList();
        }
    }

    // 添加雇员
    public void add(Employee employee) {
   
     
        // 根据员工的 id 得到该员工应当添加到 哪条链表
        int employeeLinkedListNo = hashFun(employee.getId());
        // 将 employee 添加到对应的链表中
        employeeLinkedListArray[employeeLinkedListNo].addEmployee(employee);
    }

    // 遍历所有的 链表
    public void list() {
   
     
        for (int i = 0; i < size; i++) {
   
     
            employeeLinkedListArray[i].list(i);
        }
    }

    /*
     * 根据输入的id ,查找雇员
     * */
    public void findEmployeeByid(int id) {
   
     
        // 使用散列函数确定到哪条链表查找
        int employeeLinkedListNo = hashFun(id);
        Employee employee = employeeLinkedListArray[employeeLinkedListNo].findEmployeeById(id);
        if (employee != null) {
   
     
            System.out.printf("在第%d条链表中找到 雇员 id=%d\n", (employeeLinkedListNo + 1), id);
        } else {
   
     
            System.out.println("在哈希表中,没有找到该雇员~");
        }
    }
    /*
     * 编写一个散列函数
     * 有很多方法,这里使用 简单取模法
     *
     * */
    public int hashFun(int id) {
   
     
        return id % size;
    }
}

4.5 HashTableMain.java测试类

package com.feng.ch11_hashtab;

import java.util.Scanner;

/*
 * 创建 HashTable 管理多条链表
 * */
public class HashTableMain {
   
     

    public static void main(String[] args) {
   
     
        // 创建一个 哈希表
        HashTable hashTable = new HashTable(7); // 说明哈希表的数组 长度为7,下标从 0->6

        // 写一个简单菜单
        String key = "";
        Scanner scanner = new Scanner(System.in);

        while (true) {
   
     
            System.out.println("add:添加雇员");
            System.out.println("list:显示雇员");
            System.out.println("find:查找雇员");
            System.out.println("exit:退出系统");
            key = scanner.next();

            switch (key) {
   
     
                case "add":
                    System.out.println("输入id");
                    int id = scanner.nextInt();
                    System.out.println("输入名字");
                    String name = scanner.next();
                    System.out.println("输入性别");
                    String sex = scanner.next();
                    System.out.println("输入年龄");
                    int age = scanner.nextInt();
                    // 创建雇员
                    Employee employee = new Employee(id, name, sex, age);
                    hashTable.add(employee);
                    break;
                case "list":
                    hashTable.list();
                    break;
                case "find":
                    System.out.println("请输入要查找的id");
                    id = scanner.nextInt();
                    hashTable.findEmployeeByid(id);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                    break;
                default:
                    break;
            }
        }
    }
}

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: