Java数据结构与算法——哈希表

简介: Java数据结构与算法——哈希表

1.关于哈希


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




2.代码案例


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




package com.szh.hashtab;
import java.util.Objects;
import java.util.Scanner;
/**
 * 哈希表
 */
//雇员类
class Employee {
    public int id;
    public String name;
    public Employee next;
    public Employee(int id, String name) {
        this.id = id;
        this.name = name;
    }
}
//创建EmpLinkedList, 表示链表
class EmployeeLinkedList {
    //头指针,指向第一个Emp。因此我们这个链表的head 是直接指向第一个Emp
    private Employee head; //默认为null
    //添加雇员到链表
    //假定,当添加雇员时,id 是自增长,即id的分配总是从小到大,因此我们将该雇员直接加入到本链表的最后即可
    public void add(Employee employee) {
        //如果添加的是第一个雇员
        if (head == null) {
            head = employee;
            return;
        }
        //如果不是第一个雇员,则使用一个辅助的指针,帮助定位到最后
        Employee curEmp = head;
        while (true) {
            if (curEmp.next == null) { //此时说明已经到了链表的最后
                break;
            }
            curEmp = curEmp.next;
        }
        //最后将要添加的雇员放在链表的最后
        curEmp.next = employee;
    }
    //根据传入的no,确定要遍历哪条链表的雇员信息
    public void list(int no) {
        if (head == null) { //说明链表为空
            System.out.println("第 " + (no + 1) + " 链表为空....");
            return;
        }
        System.out.print("第 " + (no + 1) + " 链表的信息为: ");
        Employee curEmp = head; //辅助指针
        while (true) {
            System.out.printf(" => id = %d, name = %s\t", curEmp.id, curEmp.name);
            if (curEmp.next == null) { //说明curEmp已经是最后节点
                break;
            }
            curEmp = curEmp.next; //后移,遍历
        }
        System.out.println();
    }
    //根据id查找雇员
    //如果查找到,就返回Emp, 如果没有找到,就返回null
    public Employee findEmployeeById(int id) {
        //判断链表是否为空
        if (head == null) {
            System.out.println("链表为空....");
            return null;
        }
        //辅助指针
        Employee curEmp = head;
        while (true) {
            if (curEmp.id == id) { //找到了,此时curEmp就是要查找的雇员信息
                break;
            }
            if (curEmp.next == null) { //说明遍历当前链表没有找到该雇员
                curEmp = null; //没找到则将curEmp置为null
                break;
            }
            curEmp = curEmp.next; //向后移动
        }
        return curEmp;
    }
}
//创建HashTab,使用哈希表来管理多条链表
class HashTab {
    private EmployeeLinkedList[] employeeLinkedLists;
    private int size; //表示共有多少条链表
    public HashTab(int size) {
        this.size = size;
        employeeLinkedLists = new EmployeeLinkedList[size];
        //这里需要分别初始化每条链表
        for (int i = 0; i < size; i++) {
            employeeLinkedLists[i] = new EmployeeLinkedList();
        }
    }
    //添加雇员
    public void add(Employee employee) {
        //根据员工的id,得到该员工应当添加到哪条链表
        int empLinkedListNo = hashFun(employee.id);
        //将emp添加到对应的链表中
        employeeLinkedLists[empLinkedListNo].add(employee);
    }
    //遍历所有的链表,即遍历哈希表
    public void list() {
        for (int i = 0; i < size; i++) {
            employeeLinkedLists[i].list(i);
        }
    }
    //根据输入的id,查找雇员
    public void findEmployeeById(int id) {
        //使用散列函数确定到哪条链表查找
        int empLinkedListNo = hashFun(id);
        Employee employee = employeeLinkedLists[empLinkedListNo].findEmployeeById(id);
        if (Objects.nonNull(employee)) { //找到
            System.out.printf("在第 %d 条链表中找到 雇员 id = %d\n", (empLinkedListNo + 1), id);
        } else { //未找到
            System.out.println("在哈希表中,没有找到该雇员~");
        }
    }
    //编写散列函数, 使用一个简单取模法
    public int hashFun(int id) {
        return id % size;
    }
}
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();
                    Employee employee = new Employee(id, name);
                    hashTab.add(employee);
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "find":
                    System.out.println("请输入要查找的id: ");
                    id = scanner.nextInt();
                    hashTab.findEmployeeById(id);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                default:
                    break;
            }
        }
    }
}


代码中的注释已经写的很清楚了,我就不再多说了,下面是测试相关截图。

相关文章
|
5月前
|
负载均衡 算法 关系型数据库
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
本文聚焦 MySQL 集群架构中的负载均衡算法,阐述其重要性。详细介绍轮询、加权轮询、最少连接、加权最少连接、随机、源地址哈希等常用算法,分析各自优缺点及适用场景。并提供 Java 语言代码实现示例,助力直观理解。文章结构清晰,语言通俗易懂,对理解和应用负载均衡算法具有实用价值和参考价值。
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
|
5月前
|
存储 缓存 监控
上网行为监控系统剖析:基于 Java LinkedHashMap 算法的时间序列追踪机制探究
数字化办公蓬勃发展的背景下,上网行为监控系统已成为企业维护信息安全、提升工作效能的关键手段。该系统需实时记录并深入分析员工的网络访问行为,如何高效存储和管理这些处于动态变化中的数据,便成为亟待解决的核心问题。Java 语言中的LinkedHashMap数据结构,凭借其独有的有序性特征以及可灵活配置的淘汰策略,为上网行为监控系统提供了一种兼顾性能与功能需求的数据管理方案。本文将对LinkedHashMap在上网行为监控系统中的应用原理、实现路径及其应用价值展开深入探究。
111 3
|
5月前
|
存储 监控 算法
基于 C++ 哈希表算法实现局域网监控电脑屏幕的数据加速机制研究
企业网络安全与办公管理需求日益复杂的学术语境下,局域网监控电脑屏幕作为保障信息安全、规范员工操作的重要手段,已然成为网络安全领域的关键研究对象。其作用类似网络空间中的 “电子眼”,实时捕获每台电脑屏幕上的操作动态。然而,面对海量监控数据,实现高效数据存储与快速检索,已成为提升监控系统性能的核心挑战。本文聚焦于 C++ 语言中的哈希表算法,深入探究其如何成为局域网监控电脑屏幕数据处理的 “加速引擎”,并通过详尽的代码示例,展现其强大功能与应用价值。
117 2
|
5月前
|
人工智能 算法 NoSQL
LRU算法的Java实现
LRU(Least Recently Used)算法用于淘汰最近最少使用的数据,常应用于内存管理策略中。在Redis中,通过`maxmemory-policy`配置实现不同淘汰策略,如`allkeys-lru`和`volatile-lru`等,采用采样方式近似LRU以优化性能。Java中可通过`LinkedHashMap`轻松实现LRUCache,利用其`accessOrder`特性和`removeEldestEntry`方法完成缓存淘汰逻辑,代码简洁高效。
209 0
|
6月前
|
前端开发 Java
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现,包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构,支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列,并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例(如`enqueue`入队和`dequeue`出队),展示了队列的操作逻辑,帮助读者深入理解其工作机制。
169 1
|
4月前
|
存储 算法 安全
Java中的对称加密算法的原理与实现
本文详细解析了Java中三种常用对称加密算法(AES、DES、3DES)的实现原理及应用。对称加密使用相同密钥进行加解密,适合数据安全传输与存储。AES作为现代标准,支持128/192/256位密钥,安全性高;DES采用56位密钥,现已不够安全;3DES通过三重加密增强安全性,但性能较低。文章提供了各算法的具体Java代码示例,便于快速上手实现加密解密操作,帮助用户根据需求选择合适的加密方案保护数据安全。
353 58
|
7月前
|
存储 算法 数据处理
公司局域网管理中的哈希表查找优化 C++ 算法探究
在数字化办公环境中,公司局域网管理至关重要。哈希表作为一种高效的数据结构,通过哈希函数将关键值(如IP地址、账号)映射到数组索引,实现快速的插入、删除与查找操作。例如,在员工登录验证和设备信息管理中,哈希表能显著提升效率,避免传统线性查找的低效问题。本文以C++为例,展示了哈希表在局域网管理中的具体应用,包括设备MAC地址与IP分配的存储与查询,并探讨了优化哈希函数和扩容策略,确保网络管理高效准确。
|
3月前
|
存储 负载均衡 算法
我们来说一说 Java 的一致性 Hash 算法
我是小假 期待与你的下一次相遇 ~
118 1
|
3月前
|
存储 监控 算法
企业上网监控场景下布隆过滤器的 Java 算法构建及其性能优化研究
布隆过滤器是一种高效的数据结构,广泛应用于企业上网监控系统中,用于快速判断员工访问的网址是否为违规站点。相比传统哈希表,它具有更低的内存占用和更快的查询速度,支持实时拦截、动态更新和资源压缩,有效提升系统性能并降低成本。
78 0
|
4月前
|
存储 安全 Java
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架,涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口,逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变,包括数组+链表+红黑树优化,以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例,展示集合框架的应用价值,助你全面掌握相关知识,轻松应对面试与开发需求。
201 3

热门文章

最新文章