Java数据结构之哈希表

Love The Way You Lie 2024-04-01 13:11 73阅读 0赞

## 0.题目引出: ##

看一个实际需求，google公司的一个上机题;  
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址..),当输入该员工的id时,要求查找到该员工的所有信息.  
要求:不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)

添加时，保证按照id从低到高插入

## 1.哈希表的介绍 ##

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

![b5a78e3b1d064d688d54da96c87abefc.png][]

![69f568582ca34bfdac06dc77436f34c8.png][]

## 2.哈希表实现思路 ##

![daad44539ed84f10a8984ab756dc31d9.png][]

## 3.代码实现 ##

public class HashTableDemo {
        public static void main(String[] args) {
            HashTable hashTable = new HashTable(7);
            Scanner scan = new Scanner(System.in);
            while (true){
                System.out.println("添加员工:add");
                System.out.println("显示员工:list");
                System.out.println("退出系统:exit");
                System.out.println("查找员工:find");
                System.out.println("删除员工:delete");
                String key = scan.next();
                switch (key){
                    case "add":
                        System.out.print("输入id:");
                        int id = scan.nextInt();
                        System.out.print("输入名字:");
                        String name=scan.next();
                        Employee employee = new Employee(id, name);
                        hashTable.add(employee);
                        break;
                    case "list":
                        hashTable.list();
                        break;
                    case "find":
                        System.out.print("请输入id:");
                        hashTable.findEmployeeById(scan.nextInt());
                        break;
                    case "delete":
                        System.out.print("请输入id:");
                        hashTable.deleteEmployeeById(scan.nextInt());
                        break;
                    case "exit":
                        scan.close();
                        System.exit(0);
                    default:
                        break;
    
                }
    
    
            }
    
    
    
        }
    }
    //创建哈希表
    class HashTable{
         public EmployeeLinkedList[]  employeeLinkedListArray;
        public int size;
    
        public HashTable(int size){
            //初始化
            employeeLinkedListArray=new EmployeeLinkedList[size];
            this.size=size;
            //初始化每个链表
            for(int i=0;i<size;i++)
                employeeLinkedListArray[i]=new EmployeeLinkedList();
        }
    
        //添加雇员
        public void add(Employee employee){
            int employeeLinkedListNo = hashFun(employee.id);
            //将emp添加到对应的链表中
            employeeLinkedListArray[employeeLinkedListNo].add(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 employeeById = employeeLinkedListArray[employeeLinkedListNo].findEmployeeById(id);
            if (employeeById==null){
                System.out.println("未找到");
            }
            else {
                System.out.println("在第"+(employeeLinkedListNo+1)+"条链表找到:"+employeeById);
            }
        }
        //根据id删除员工
        public void deleteEmployeeById(int id){
            int employeeLinkedListNo = hashFun(id);
            boolean flag = employeeLinkedListArray[employeeLinkedListNo].deleteEmployeeById(id);
            if(flag){
                System.out.println("成功删除id="+id+"的员工");
            }
            else
                System.out.println("未找到指定员工");
    
        }
    
    
    
        //编写散列函数,这里使用一个简单的取模法
        public int hashFun(int id){
            return id%size;
        }
    
    
    
    
    
    }
    //创建链表
    class EmployeeLinkedList {
        //头指针.直接指向第一个员工
        Employee head;
    
        //默认为尾插法
        public void add(Employee employee) {
            if (head == null) {
                head = employee;
                return;
            }
            Employee temp = head;
            while (temp.next!= null) {
                temp = temp.next;
    
            }
            temp.next=employee;
    
    
        }
        //遍历链表
        public void list(int i){
            i++;
            if(head==null){
                System.out.println("第"+i+"条链表为空");
                return;
            }
            Employee temp = head;
            System.out.print("第"+i+"条链表的信息为:");
            while (temp != null) {
                System.out.print("=====>"+temp);
                temp = temp.next;
    
            }
            System.out.println();
    
    
    
        }
        //根据id查找员工
        public Employee findEmployeeById(int id){
            if(head==null){
                return null;
            }
            Employee temp=head;
            while (temp!=null&&temp.id!=id){
                temp=temp.next;
            }
            return temp;
    
        }
        //根据id删除雇员
        public boolean deleteEmployeeById(int id){
            if(head==null)
                return false;
            Employee temp=head;
            if (temp.id==id)
                temp=null;
            while(temp.next!=null&&temp.next.id==id){
                temp=temp.next;
            }
            if (temp.next==null)
                return false;
            temp.next=temp.next.next;
            return true;
    
        }
    
    
    }
    
    //表示雇员
    class Employee {
        public int id;
        public String name;
        public Employee next;
    
        public Employee() {
        }
    
        public Employee(int id, String name) {
            this.id = id;
            this.name = name;
        }
    
        @Override
        public String toString() {
            return "Employee{" +
                    "id=" + id +
                    ", name='" + name + '\'' +
                    '}';
        }
    }

**结果:**

> 添加员工:add  
> 显示员工:list  
> 退出系统:exit  
> 查找员工:find  
> 删除员工:delete

添加和遍历

> add
> 
> list
> 
> 第1条链表为空  
> 第2条链表的信息为:=====>Employee\{id=1, name='zxn'\}=====>Employee\{id=8, name='ql'\}  
> 第3条链表的信息为:=====>Employee\{id=2, name='xcl'\}  
> 第4条链表为空  
> 第5条链表为空  
> 第6条链表为空  
> 第7条链表为空

查找

> find  
> 请输入id:2  
> 在第3条链表找到:Employee\{id=2, name='xcl'\}

删除

> delete  
> 请输入id:1  
> 成功删除id=1的员工

## 4.总结 ##

哈希表适用于解决给你一个值,判断这个值是否在这个集合里面出现过,

哈希表主要就是解决了查找的效率很低的问题,仅仅通过一个hashCode(),将查找的效率变得很高

[b5a78e3b1d064d688d54da96c87abefc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/1e7c5cd012004cc7aba9fe40c3065b22.png
[69f568582ca34bfdac06dc77436f34c8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/318a0a4c951341c78c7a51a396e0afdd.png
[daad44539ed84f10a8984ab756dc31d9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/626fc3c1c7314a2b9821f38edc74077b.png