动态数组实现链地址法哈希表
通常情况下哈希函数的输入空间远大于输出空间,因此理论上哈希冲突是不可避免的。比如,输入空间为全体整数,输出空间为数组容量大小,则必然有多个整数映射至同一数组索引。
解决哈希冲突方法常见有:链地址法、开放寻址法。
注意:无论是开放寻址还是链地址法,它们只能保证哈希表可以在发生冲突时正常工作,但无法减少哈希冲突的发生。常见的哈希算法有:DM5、sha-1、sha-2和sha-3。
在原始哈希表中,每个桶仅能存储一个键值对。「链式地址 separate chaining」将单个元素转换为链表,将键值对作为链表节点,将所有发生冲突的键值对都存储在同一链表中。
package com.wei.mybatisflex.demo;import java.util.ArrayList;
import java.util.List;/*** 链式地址哈希表*/
public class HashMapChaining {int size; // 键值对数量int capacity; // 哈希表容量double loadThres; // 触发扩容的负载因子阈值=(键值对数量/哈希表容量) 标准为: 0.75int extendRatio; // 扩容倍数List<List<Pair>> buckets; // 桶数组,这里用动态数组List<Pair>代替链表,一个桶就是一个链表。/*** 键值对定义*/class Pair{private int key;private String val;public Pair(int key, String val) {this.key = key;this.val = val;}}/* 构造方法 */public HashMapChaining() {size = 0;capacity = 4;loadThres = 2 / 3.0;extendRatio = 2;buckets = new ArrayList<>(capacity);for (int i = 0; i < capacity; i++) {buckets.add(new ArrayList<>());}}/* 哈希函数 */int hashFunc(int key) {return key % capacity;}/* 负载因子 */double loadFactor() {return (double) size / capacity;}/* 查询操作 */String get(int key) {int index = hashFunc(key);List<Pair> bucket = buckets.get(index);// 遍历桶,若找到 key 则返回对应 valfor (Pair pair : bucket) {if (pair.key == key) {return pair.val;}}// 若未找到 key 则返回 nullreturn null;}/* 添加操作 */void put(int key, String val) {// 当负载因子超过阈值时,执行扩容if (loadFactor() > loadThres) {extend();}int index = hashFunc(key);List<Pair> bucket = buckets.get(index);// 遍历桶,若遇到指定 key ,则更新对应 val 并返回for (Pair pair : bucket) {if (pair.key == key) {pair.val = val;return;}}// 若无该 key ,则将键值对添加至尾部Pair pair = new Pair(key, val);bucket.add(pair);size++;}/* 删除操作 */void remove(int key) {int index = hashFunc(key);List<Pair> bucket = buckets.get(index);// 遍历桶,从中删除键值对for (Pair pair : bucket) {if (pair.key == key) {bucket.remove(pair);size--;break;}}}/* 扩容哈希表 */void extend() {// 暂存原哈希表List<List<Pair>> bucketsTmp = buckets;// 初始化扩容后的新哈希表capacity *= extendRatio;buckets = new ArrayList<>(capacity);for (int i = 0; i < capacity; i++) {buckets.add(new ArrayList<>());}size = 0;// 将键值对从原哈希表搬运至新哈希表for (List<Pair> bucket : bucketsTmp) {for (Pair pair : bucket) {put(pair.key, pair.val);}}}/* 打印哈希表 */void print() {for (List<Pair> bucket : buckets) {List<String> res = new ArrayList<>();for (Pair pair : bucket) {res.add(pair.key + " -> " + pair.val);}System.out.println(res);}}/*** 测试*/public static void main(String[] args) {HashMapChaining hashMapChaining = new HashMapChaining();hashMapChaining.put(123, "23");hashMapChaining.put(124, "24");hashMapChaining.put(125, "25");hashMapChaining.put(126, "26");System.out.println("哈希表展示如下:");hashMapChaining.print();System.out.println("==================");String s = hashMapChaining.get(123);System.out.println("k=123对应的val值是:"+s);System.out.println("==================");hashMapChaining.put(124, "99");System.out.println("把key=124的值换成99");hashMapChaining.print();System.out.println("==================");hashMapChaining.remove(124);System.out.println("删除key=124所对应的值:");hashMapChaining.print();}
}
相关文章:
动态数组实现链地址法哈希表
通常情况下哈希函数的输入空间远大于输出空间,因此理论上哈希冲突是不可避免的。比如,输入空间为全体整数,输出空间为数组容量大小,则必然有多个整数映射至同一数组索引。 解决哈希冲突方法常见有:链地址法、开放寻址…...
Eclipse(STS):pom.xml 报错:Multiple markers at this line
pom.xml 报错:Multiple markers at this line STS中,项目能够正常运行,但是 pom.xml 报错:Multiple markers at this line 项目本身没有任何修改,之前不报错的,突然报错了。 Multiple markers at this li…...
CSerialPort教程4.3.x (3) - CSerialPort在MFC中的使用
CSerialPort教程4.3.x (3) - CSerialPort在MFC中的使用 环境: 系统:windows 10 64位 编译器:Visual Studio 2008前言 CSerialPort项目是一个基于C/C的轻量级开源跨平台串口类库,可以轻松实现跨平台多操作系统的串口读写&#x…...
2022版 的IDEA创建一个maven项目(超详细)
一.设置idea中指定的maven的位置以及本地存储仓库 开发中一般我们使用自己下载的maven,不使用IDEA工具自带的,这就需要将我们下载的maven配置到IDEA工具中,配置如下图所示: 或者直接 快捷键 CtrlAltS 直接进入设置 maven home pa…...
lvs实现DR模型搭建
目录 一,实现DR模型搭建 1, 负载调度器配置 1.1调整ARP参数 1.2 配置虚拟IP地址重启网卡 1.3 安装ipvsadm 1.4 加载ip_vs模块 1.5 启动ipvsadm服务 1.6 配置负载分配策略 1.7 保存策略 2, web节点配置 1.1 调整ARP参数 1.2 配置虚拟I…...
设计模式之迭代器模式(Iterator)的C++实现
1、迭代器模式的提出 在软件开发过程中,操作的集合对象内部结构常常变化,在访问这些对象元素的同时,也要保证对象内部的封装性。迭代器模式提供了一种利用面向对象的遍历方法来遍历对象元素。迭代器模式通过抽象一个迭代器类,不同…...
【0基础入门Python Web笔记】二、python 之逻辑运算和制流程语句
二、python 之逻辑运算和制流程语句 逻辑运算控制流程语句条件语句(if语句)循环结构(for循环、while循环)continue、break和pass关键字控制流程语句的嵌套以及elif 更多实战项目可进入下方官网 逻辑运算 Python提供基本的逻辑运算…...
容器——Docker
1.安装docker服务,配置镜像加速器 2.下载系统镜像(Ubuntu、 centos) 3.基于下载的镜像创建两个容器 (容器名一个为自己名字全拼,一个为首名字字母) 4.容器的启动、 停止及重启操作 5.怎么查看正在运行的容器…...
SQL注入之宽字节注入
文章目录 宽字节注入是什么?注入练习让转义符失效联合查询 代码审计 宽字节注入是什么? 宽字节注入准确来说不是注入手法,而是另外一种比较特殊的情况。宽字节注入的目的是绕过单双引号转义。 宽字节注入是一种绕过单双引号转义的手段&#x…...
MyBatis动态sql
文章目录 一、MyBatis动态sql1.1 概述1.2 if元素1.3 foreach元素 二、模糊查询2.1 使用#{字段名}2.2 使用${字段名}2.3 使用concat{%,#{字段名},%}2.4 mybatis中#与$的区别 三、MyBatis结果映射3.1 区别3.2 应用场景 一、MyBatis动态sql 1.1 概述 MyBatis是一个Java持久化框架…...
L1-032 Left-pad 测试点全过
题目 根据新浪微博上的消息,有一位开发者不满NPM(Node Package Manager)的做法,收回了自己的开源代码,其中包括一个叫left-pad的模块,就是这个模块把javascript里面的React/Babel干瘫痪了。这是个什么样的…...
ssm+Vue.js在线购物系统源码和论文
ssmVue.js在线购物系统源码和论文049 开发工具:idea 数据库mysql5.7 数据库链接工具:navcat,小海豚等 技术:ssm 摘 要 随着科学技术的飞速发展,各行各业都在努力与现代先进技术接轨,通过科技手段提高自身的优势…...
港联证券|指数或进入磨底阶段 短期关注环保、煤炭等板块
磨底历来都不是一天能达到的,比方2018年的政策底到商场底,半途也阅历两个多月时间。当下政策底出现之后至今也有近一个月时间,并且下跌量能不断缩短,心情面也降至冰点,种种迹象阐明离真正商场底的构成已经不远了。此时…...
pytorch 实现VGG
VGG全称是Visual Geometry Group,因为是由Oxford的Visual Geometry Group提出的。AlexNet问世之后,很多学者通过改进AlexNet的网络结构来提高自己的准确率,主要有两个方向:小卷积核和多尺度。而VGG的作者们则选择了另外一个方向&a…...
科技项目验收检测报告获取有哪些注意事项,作用都有哪些?
验收测试报告 软件从研发到结束是一个很长的周期,对于软件想要完成上市或者是交付到用户手中之前我们还需要进行一次全面检测,也就是科技项目验收测试,此测试有着严格的要求,需要第三方软件测评机构来完成,并出具科技…...
OceanBase:谁动了我得参数?
作者:郑增权 爱可生南区数据库工程师,爱可生 DBA 团队成员,负责数据库相关技术支持。爱好:桌球、羽毛球、咖啡、电影。 本文来源:原创投稿 爱可生开源社区出品,原创内容未经授权不得随意使用,转…...
Python快速入门体验
Python快速入门体验 一、环境信息1.1 硬件信息1.2 软件信息 二、Conda安装2.1 Conda介绍2.1.1 Conda简介2.1.2 Conda、Anaconda及Miniconda及的关系 2.2 Conda安装包下载2.2.1 Miniconda下载2.2.2 Anconda下载 2.3 Conda安装2.3.1 Miniconda安装2.3.2 Anconda安装 2.4 Conda初始…...
【从零学习python 】68. Python正则表达式中的贪婪和非贪婪模式
文章目录 贪婪和非贪婪模式进阶案例 贪婪和非贪婪模式 Python里数量词默认是贪婪的(在少数语言里也可能是默认非贪婪),总是尝试匹配尽可能多的字符; 非贪婪则相反,总是尝试匹配尽可能少的字符。 在*、?、、{m,n}后面…...
MongoDB【CRUD练习-条件查询-文档关系】
练习1-CRUD // 进入test数据库 use test; // 查询文档内容 db.students.find(); // 显示当前数据库中所有集合 show collections; // 向数据库的user集合中插入一个文档 db.users.insertOne({username: "lyh"} ); // 查看当前数据库中所有的集合 发现users集合被创建…...
使用M2Mqtt 接受以及发布MQTT消息
在NuGet库里面直接查找M2Mqtt就可以安装库。 使用framework4.5.2 1.配置文件操作 public static class GModel{public static BassSetup MainSetup { get; set; }public static void GetThisAdd(){MainSetup new BassSetup();string IPAdd ConfigurationManager.AppSettings…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
