数据结构===散列表
文章目录
- 概要
- 散列思想
- 散列函数
- 散列冲突
- 开放寻址法
- 装载因子
- 链表法
- 代码Java
- 小结
概要
散列表是一种很有趣的数据结构。
散列表是一个很有用的数据结构。它是数组演练而来的,又是一个基于数组的扩展的数据结构。接下来看看。
散列思想
散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。
散列表是由key和hash组成的。
散列函数
散列函数很重要的,牵扯到后边的散列冲突。
构造散列函数,三点基本要求:
- 散列函数计算得到的散列值是一个非负整数
- 如果key1 = key2,那么hash(key1) == hash(key2)
- 如果key1 != key2, 那么hash(key1) != hash(key2)
散列冲突无法完全避免。散列函数的应用挺多的,像MD5,SHA,CRC等等,都是应用了散列函数。接下来看看散列冲突。
散列冲突
散列冲突无法避免。
散列冲突无法避免,那我们聊聊散列冲突怎么解决。通常由2种方式,及开放寻址法和链表法。
开放寻址法
基于数组的解决方案。
开放寻址法的核心思想是,如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。其中有线性检测,二次探测,双重散列。其中,不管哪种,如果列表空闲位置不多,都会增加散列冲突发生的概率。为了减小散列冲突发生的概率,一般都会保证有一定比例的空闲槽位。用装载因子表示空闲槽位的多少。
装载因子
计算公式:
散列表的装载因子=填入表中的元素个数/散列表的长度
这个也更重要。
链表法
链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它要简单很多。也就是一个槽位对应一个链表。这就不难,当散列表效率最差的时候,就退化成链表了。当然,如果比较均匀,它的效果还是很好的。
代码Java
public class HashTable<K, V> {/*** 散列表默认长度*/private static final int DEFAULT_INITAL_CAPACITY = 8;/*** 装载因子*/private static final float LOAD_FACTOR = 0.75f;/*** 初始化散列表数组*/private Entry<K, V>[] table;/*** 实际元素数量*/private int size = 0;/*** 散列表索引数量*/private int use = 0;public HashTable() {table = (Entry<K, V>[]) new Entry[DEFAULT_INITAL_CAPACITY];}static class Entry<K, V> {K key;V value;Entry<K, V> next;Entry(K key, V value, Entry<K, V> next) {this.key = key;this.value = value;this.next = next;}}/*** 新增** @param key* @param value*/public void put(K key, V value) {int index = hash(key);// 位置未被引用,创建哨兵节点if (table[index] == null) {table[index] = new Entry<>(null, null, null);}Entry<K, V> tmp = table[index];// 新增节点if (tmp.next == null) {tmp.next = new Entry<>(key, value, null);size++;use++;// 动态扩容if (use >= table.length * LOAD_FACTOR) {resize();}}// 解决散列冲突,使用链表法else {do {tmp = tmp.next;// key相同,覆盖旧的数据if (tmp.key == key) {tmp.value = value;return;}} while (tmp.next != null);Entry<K, V> temp = table[index].next;table[index].next = new Entry<>(key, value, temp);size++;}}/*** 散列函数* <p>* 参考hashmap散列函数** @param key* @return*/private int hash(Object key) {int h;return (key == null) ? 0 : ((h = key.hashCode()) ^ (h >>> 16)) % table.length;}/*** 扩容*/private void resize() {Entry<K, V>[] oldTable = table;table = (Entry<K, V>[]) new Entry[table.length * 2];use = 0;for (int i = 0; i < oldTable.length; i++) {if (oldTable[i] == null || oldTable[i].next == null) {continue;}Entry<K, V> e = oldTable[i];while (e.next != null) {e = e.next;int index = hash(e.key);if (table[index] == null) {use++;// 创建哨兵节点table[index] = new Entry<>(null, null, null);}table[index].next = new Entry<>(e.key, e.value, table[index].next);}}}/*** 删除** @param key*/public void remove(K key) {int index = hash(key);Entry e = table[index];if (e == null || e.next == null) {return;}Entry pre;Entry<K, V> headNode = table[index];do {pre = e;e = e.next;if (key == e.key) {pre.next = e.next;size--;if (headNode.next == null) use--;return;}} while (e.next != null);}/*** 获取** @param key* @return*/public V get(K key) {int index = hash(key);Entry<K, V> e = table[index];if (e == null || e.next == null) {return null;}while (e.next != null) {e = e.next;if (key == e.key) {return e.value;}}return null;}
}
小结
散列表学习总结
散列表是一种基于数组数据结构。有key和hash组成。重点是散列冲突如何解决,怎么减少散列碰撞发生的概率,设计装载因子和散列函数。如何解决散列冲突呢?有开放寻址法和链表法2种方法。然后就是看看java如何实现的,当然也有其他语言的,只是没有一一列举出来。关键是算法学会了,什么语言实现都不重要了。
相关文章:
数据结构===散列表
文章目录 概要散列思想散列函数散列冲突开放寻址法装载因子 链表法 代码Java小结 概要 散列表是一种很有趣的数据结构。 散列表是一个很有用的数据结构。它是数组演练而来的,又是一个基于数组的扩展的数据结构。接下来看看。 散列思想 散列表用的是数组支持按照下…...
10G MAC层设计系列-(2)MAC RX模块
一、概述 MAC RX模块的需要进行解码、对齐、CRC校验。 因为在空闲的时候10G PCS/PMA会一直向外吐空闲符(x07)所以需要根据开始符、结束符将有效数据从码流中截取,也就是解码。 因为开始字符的所在位置有两种形式,而结束字符的位…...
解码Starknet Verifier:深入逆向工程之旅
1. 引言 Sandstorm为: 能提交独立proof给StarkWare的Ethereum Verifier,的首个开源的STARK prover。 开源代码见: https://github.com/andrewmilson/sandstorm(Rust) L2Beat 提供了以太坊上Starknet的合约架构图&…...
【C++语言】类和对象--默认成员函数 (中)
文章目录 前言类的六个默认成员函数:1. 构造函数概念特性做了什么?易错注意:显式定义和默认构造函数 2. 析构函数概念特征做了什么?注意事项: 3.拷贝构造函数概念特征做了什么?注意事项: 4.赋值运算符重载…...
前端递归常见应用
概览 在 JavaScript 中,递归是一种编程技术,指的是函数直接或间接调用自身的过程。 递归通常用于解决可以分解为相同子问题的问题。通过不断地将问题分解成更小的、相似的子问题,直到达到某种基本情况(不再需要进一步递归的简单情…...
AI工具如何改变我们的工作与生活
AI工具在当今社会中扮演着越来越重要的角色,它们已经开始改变着我们的工作方式和生活方式。在接下来的2000字篇幅中,我将详细探讨AI工具如何影响我们的工作和生活。 AI工具在工作中的影响: 自动化和智能化生产流程: AI工具可以通…...
深入了解C/C++的内存区域划分
🔥个人主页:北辰水墨 🔥专栏:C学习仓 本节我们来讲解C/C的内存区域划分,文末会附加一道题目来检验成果(有参考答案) 一、大体有哪些区域?分别存放什么变量开辟的空间? …...
C++构造函数和析构函数的调用顺序
一般情况下,调用析构函数的次序正好与调用构造函数的次序相反,也就是最先被调用的构造函数,其对应的析构函数最后被调用,而最后被调用的构造函数,其对应的析构函数最先被调用。 当然对象的构造函数和析构函数调用时机和…...
智能家居1 -- 实现语音模块
项目整体框架: 监听线程4: 1. 语音监听线程:用于监听语音指令, 当有语音指令过来后, 通过消息队列的方式给消息处理线程发送指令 2. 网络监听线程:用于监听网络指令,当有网络指令过来后, 通过消息队列的方…...
Leetcode 3139. Minimum Cost to Equalize Array
Leetcode 3139. Minimum Cost to Equalize Array 1. 解题思路2. 代码实现 题目链接:3139. Minimum Cost to Equalize Array 1. 解题思路 这一题是一道hard的题目,而且看了一下答出率低的离谱,就一开始被吓到了,不过实际做了一下…...
【element-ui】el-table横向滚动后,通过is-scrolling-left获取滚动高度失效的问题
el-table横向滚动后,通过is-scrolling-left获取滚动高度失效的问题 需求 现在有一个需求,需要监听el-table的纵向滚动,当滚动高度达到特定值时进行一些操作。 代码如下: methods:{throttledHandleScroll() {// 如果已经有定时器…...
JAVA中的日期
获取当前的日期 LocalDate LocalDate today LocalDate.now();System.out.println("今天是:"today);//今天是:2024-05-06String format today.format(DateTimeFormatter.ofPattern("yyyy年MM月dd日"));System.out.println("今天是:"…...
一起了解开源自定义表单的优势表现
随着社会的进步和科技的发展,越来越多的中小企业希望采用更为先进的软件平台,助力企业实现高效率的流程化管理。低代码技术平台、开源自定义表单已经慢慢走入大众视野,成为一款灵活、高效的数字化转型工具。流辰信息专注于低代码技术平台的研…...
体育老师工资高吗,奖金有吗
教师的薪资水平与多种因素相关,包括教育经验、工作地点、学校类型以及个人的教学成果等。在讨论体育教师的工资问题时,不能仅仅关注数字,更应了解教育价值和个人发展。 初中体育教师的工资水平受多种因素影响。根据网络统计的数据,…...
Linux驱动开发——(十一)INPUT子系统
目录 一、input子系统简介 二、input驱动API 2.1 input字符设备 2.2 input_dev结构体 2.3 上报输入事件 2.4 input_event结构体 三、代码 3.1 驱动代码 3.2 测试代码 四、平台测试 一、input子系统简介 input子系统是管理输入的子系统,和pinctrl、gpio子…...
大数据毕业设计Python+Django旅游景点评论数据采集分析可视化系统 NLP情感分析 LDA主题分析 bayes分类 旅游爬虫 旅游景点评论爬虫 机器学习 深度学习 人工智能 计算机毕业设计
毕业论文(设计)开题报告 学生姓名 学 号 所在学院 信息工程学院 专 业 指导教师姓名 指导教师职称 工程师 助教 指导教师单位 论文(设计)题目 基于朴素贝叶斯算法旅游景点线上评价情感分析 开 题 报 告…...
FSNotes for Mac v6.7.1中文激活版:强大的笔记管理工具
FSNotes for Mac是一款功能强大的文本处理与笔记管理工具,为Mac用户提供了一个直观、高效的笔记记录和整理平台。 FSNotes for Mac v6.7.1中文激活版下载 FSNotes支持Markdown语法,使用户能够轻松设置笔记格式并添加链接、图像等元素,实现笔记…...
课程34:Windows Docker部署.Net Core项目
这里写目录标题 🚀前言一、安装Docker Desktop1.1 官网下载Docker1.2 安装Docker1.2.1 选择配置,默认都勾选1.2.2 安装中1.2.3 安装成功1.2.4 启动1.2.5 启动成功二、.Net Core 项目发布与部署2.1 修改Dockerfile文件2.2 Web项目发布2.3 修改配置2.3.1 修改dockerfile<...
分布式与一致性协议之ZAB协议(四)
ZAB协议 ZooKeeper是如何选举领导者的。 首先我们来看看ZooKeeper是如何实现成员身份的? 在ZooKeeper中,成员状态是在QuorumPeer.java中实现的,为枚举型变量 public enum ServerState { LOOKING, FOLLOWING, LEADING, OBSERVING }其实&…...
在M1芯片安装鸿蒙闪退解决方法
在M1芯片安装鸿蒙闪退解决方法 前言下载鸿蒙系统安装完成后,在M1 Macos14上打开闪退解决办法接下来就是按照提示一步一步安装。 前言 重新安装macos系统后,再次下载鸿蒙开发软件,竟然发现打不开。 下载鸿蒙系统 下载地址:http…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
