哈希表原理与Java HashSet、LinkedHashSet实现

本文涉及的产品
简介: 哈希表原理与Java HashSet、LinkedHashSet实现

一、哈希表原理


哈希表(Hash Table)是一种使用哈希函数组织数据的数据结构,它实现了从键(Key)到值(Value)的快速映射。在哈希表中,数据的存储位置是通过其键值经过哈希函数计算后得到的。哈希表的核心思想是使用哈希函数将键转化为数组的索引,从而在常数时间内进行数据的查找。

哈希表的主要操作包括:

  1. 哈希函数:将键转化为数组索引的函数。一个好的哈希函数应该尽可能地避免冲突,即不同的键应该尽可能地映射到不同的索引上。
  2. 插入:将键值对插入到哈希表中。首先通过哈希函数计算出键的索引,然后将值存储在该索引对应的位置。
  3. 查找:通过键查找对应的值。同样地,首先通过哈希函数计算出键的索引,然后在该索引对应的位置查找值。
  4. 删除:通过键删除对应的键值对。首先通过哈希函数计算出键的索引,然后删除该索引对应位置的值。

当两个不同的键经过哈希函数计算后得到相同的索引时,就会发生哈希冲突。为了解决哈希冲突,有两种常见的方法:开放寻址法(Open Addressing)和链地址法(Separate Chaining)。在Java的HashSetLinkedHashSet中,采用的是链地址法。


二、Java HashSet实现


HashSet是Java集合框架中的一种具体实现,它基于哈希表实现,并且使用链地址法解决哈希冲突。HashSet中的元素是无序的,并且不允许重复。由于HashSet是基于哈希表的,因此其添加、删除和查找元素的时间复杂度都是O(1)。

下面是一个简单的HashSet使用示例:

import java.util.HashSet;
import java.util.Set;
public class HashSetExample {
    public static void main(String[] args) {
        // 创建一个HashSet实例
        Set<Integer> set = new HashSet<>();
        
        // 添加元素到HashSet中
        set.add(1);
        set.add(2);
        set.add(3);
        set.add(4);
        set.add(5);
        set.add(3); // 重复元素不会被添加
        
        // 遍历HashSet中的元素(无序)
        for (Integer number : set) {
            System.out.println(number); // 输出顺序不确定,因为HashSet不保证元素的顺序
        }
        
        // 检查HashSet中是否包含某个元素
        System.out.println(set.contains(3)); // 输出true
        System.out.println(set.contains(6)); // 输出false
    }
}


三、Java LinkedHashSet实现


LinkedHashSet也是Java集合框架中的一种具体实现,它同样基于哈希表和链地址法。与HashSet不同的是,LinkedHashSet使用链表维护了元素的插入顺序,因此遍历LinkedHashSet时元素的顺序与插入时的顺序一致。但是需要注意的是,这种顺序的维护需要额外的空间来存储链表节点,因此在空间复杂度上比HashSet略高。

下面是一个简单的LinkedHashSet使用示例:

import java.util.LinkedHashSet;
import java.util.Set;
public class LinkedHashSetExample {
    public static void main(String[] args) {
        // 创建一个LinkedHashSet实例
        Set<Integer> set = new LinkedHashSet<>();
        
        // 添加元素到LinkedHashSet中(保持插入顺序)
        set.add(1);
        set.add(2);
        set.add(3);
        set.add(4);
        set.add(5);
        set.add(3); // 重复元素不会被添加,但不会影响已存在的顺序
        
        // 遍历LinkedHashSet中的元素(有序)
        for (Integer number : set) {
            System.out.println(number); // 输出顺序与插入顺序一致:1, 2, 3, 4, 5
        }
    }
}

在上面的示例中,可以看到即使尝试添加一个已经存在的元素(如数字3),也不会影响集合中其他元素的顺序。这是因为LinkedHashSet在内部使用了链表来维护元素的插入顺序。同时,由于LinkedHashSet是基于哈希表的,它仍然能够在常数时间内完成添加、删除和查找操作。这使得LinkedHashSet成为了一种既能够保持元素顺序又具有良好性能的数据结构。

相关实践学习
基于函数计算一键部署掌上游戏机
本场景介绍如何使用阿里云计算服务命令快速搭建一个掌上游戏机。
建立 Serverless 思维
本课程包括: Serverless 应用引擎的概念, 为开发者带来的实际价值, 以及让您了解常见的 Serverless 架构模式
相关文章
|
11天前
|
运维 NoSQL 算法
Java开发-深入理解Redis Cluster的工作原理
综上所述,Redis Cluster通过数据分片、节点发现、主从复制、数据迁移、故障检测和客户端路由等机制,实现了一个分布式的、高可用的Redis解决方案。它允许数据分布在多个节点上,提供了自动故障转移和读写分离的功能,适用于需要大规模、高性能、高可用性的应用场景。
16 0
|
16天前
|
Java 调度
Java并发编程:深入理解线程池的原理与实践
【4月更文挑战第6天】本文将深入探讨Java并发编程中的重要概念——线程池。我们将从线程池的基本原理入手,逐步解析其工作过程,以及如何在实际开发中合理使用线程池以提高程序性能。同时,我们还将关注线程池的一些高级特性,如自定义线程工厂、拒绝策略等,以帮助读者更好地掌握线程池的使用技巧。
|
19天前
|
Java 开发者
软件工程设计原理接口隔离原则 ,具体实现及JAVA代码举例
【4月更文挑战第7天】接口隔离原则(Interface Segregation Principle, ISP)是面向对象设计原则之一,旨在减少不必要的依赖关系,通过拆分庞大且臃肿的接口为更小、更具体的接口来实现。这个原则强调“客户端不应该被迫依赖于它不使用的接口”,意味着一个类不应该被迫实现它不使用的方法。
16 1
|
19天前
|
Java
软件工程设计原理依赖倒置原则 ,具体实现及JAVA代码举例
【4月更文挑战第5天】在软件工程中,依赖倒置原则(Dependency Inversion Principle, DIP)是一项重要的设计原则,它是SOLID原则中的一个组成部分。这个原则主张高层模块不应该依赖于低层模块,而是应该依赖于抽象;抽象不应该依赖于细节,细节应该依赖于抽象。这种设计方法有助于降低代码间的耦合度,增强系统的灵活性和可维护性
20 0
|
19天前
|
Java 关系型数据库
软件工程设计原理开放封闭原则 ,具体实现及JAVA代码举例
【4月更文挑战第4天】开放封闭原则(Open/Closed Principle, OCP)是面向对象设计的核心原则之一,它指出软件实体(类、模块、函数等)应该对扩展开放,对修改封闭。这意味着在不修改已有代码的前提下,可以通过扩展来增加新的功能,从而提高软件系统的灵活性和可维护性
18 1
|
22天前
|
存储 安全 Java
Java线程池ThreadPoolExcutor源码解读详解04-阻塞队列之PriorityBlockingQueue原理及扩容机制详解
1. **继承实现图关系**: - `PriorityBlockingQueue`实现了`BlockingQueue`接口,提供了线程安全的队列操作。 - 内部基于优先级堆(小顶堆或大顶堆)的数据结构实现,可以保证元素按照优先级顺序出队。 2. **底层数据存储结构**: - 默认容量是11,存储数据的数组会在需要时动态扩容。 - 数组长度总是2的幂,以满足堆的性质。 3. **构造器**: - 无参构造器创建一个默认容量的队列,元素需要实现`Comparable`接口。 - 指定容量构造器允许设置初始容量,但不指定排序规则。 - 可指定容量和比较
40 2
|
23天前
|
缓存 Java C#
【JVM故障问题排查心得】「Java技术体系方向」Java虚拟机内存优化之虚拟机参数调优原理介绍(一)
【JVM故障问题排查心得】「Java技术体系方向」Java虚拟机内存优化之虚拟机参数调优原理介绍
64 0
|
26天前
|
Java
软件工程设计原理里氏替换原则 ,具体实现及JAVA代码举例
里氏替换原则(Liskov Substitution Principle, LSP)是面向对象设计的基本原则之一,由Barbara Liskov提出。这个原则指出,如果类 S 是类 T 的子类型,则程序中使用 T 的对象的地方都可以不经修改地使用 S 的对象。换句话说,子类的对象应该能够替换掉它们的父类对象,而不影响程序的正确性。这个原则强调了继承关系中的行为兼容性,保证了基类和派生类之间的正确抽象和继承关系。
24 3
|
28天前
|
开发框架 Java API
java反射机制的原理与简单使用
java反射机制的原理与简单使用
17 1
|
1月前
|
存储 Java C语言
Java代码解释Flash原理
Java代码解释Flash原理
32 0