java数据结构和算法——哈希表

一、哈希表的基本介绍

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

二、哈希表的内存布局

三、哈希表的应用实例需求

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

要求: 1)、不使用数据库,速度越快越好=>哈希表(散列) 2)、添加时，保证按照id从低到高插入

四、哈希表的实现思路图解

五、哈希表的代码实现示例

1、代码

package com.rf.springboot01.dataStructure.hashtable;


import java.util.Scanner;

/**
 * @description:
 * @author: xiaozhi
 * @create: 2020-08-25 14:41
 */
public class HashTabDemo {
    public static void main(String[] args) {
        HashTab hashTab = new HashTab(7);

        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();
                    //创建雇员
                    Emp emp = new Emp(id, name);
                    hashTab.addEmp(emp);
                    break;
                case "list":
                    hashTab.getlist();
                    break;
                case "find":
                    System.out.println("请输入需要查找的id");
                    id=scanner.nextInt();
                    hashTab.getEmpById(id);
                    break;
                default:
                    break;
            }
        }
    }
}

/**
 * @Description: 创建HashTab 管理多条链表
 * @Param:
 * @Author: xz
 * @return:
 * @Date: 2020/8/25 14:26
 */
class HashTab{
    private EmpLinkedList[] empLinkedListArray;
    private int size;//表示有多少条链表

    //构造器
    public HashTab(int size){
        this.size=size;
        empLinkedListArray = new EmpLinkedList[size];//初始化empLinkedListArray
        for(int i=0;i