开放寻址法、链式哈希数据结构详细解读

一、开放寻址法(Open Addressing)

1. 定义

开放寻址法是一种哈希冲突解决策略,所有元素都存储在哈希表中。当发生冲突时,即两个键计算出的哈希值相同时,会按照一定的探查序列查找下一个可用的位置来存储新元素。

2. 工作原理

开放寻址法中,每个元素都在表内的一个固定位置。探查序列用于寻找下一个可用插入位置,常见的方法包括:

  • 线性探查(Linear Probing):依次检查下一个位置,如 ,其中 i 是步数。
  • 二次探查(Quadratic Probing):检查位置按二次函数递增,如 
  • 双重散列(Double Hashing):使用第二个哈希函数来确定步数,如 ((h(k)+i⋅h′(k))mod  m。
3. 特点
  • 单一存储:所有元素都存储在哈希表内,不需要额外的空间来存储链表或链节点。
  • 探查序列:用于在发生冲突时寻找新的存储位置。
  • 删除标记:删除元素时,通常标记为“已删除”,以避免破坏探查序列。
4. 优缺点
  • 优点

    • 节省空间:不需要额外的结构来存储冲突元素。
    • 简单实现:易于理解和实现。
  • 缺点

    • 负载因子:性能受负载因子的影响,负载因子越大,探查越长,效率越低。
    • 探查冲突:线性探查容易出现聚集问题(大量元素集中在一起)。
    • 删除复杂:删除操作需要特殊标记,处理不当会影响查找效率。
5. 应用场景
  • 内存有限:适合内存有限的场景,不需要额外的存储空间。
  • 中等负载:适用于负载因子较低的情况,以保持性能。
6. 示例代码(Java 实现线性探查)
public class OpenAddressingHashTable {private String[] table;private int size;public OpenAddressingHashTable(int capacity) {this.table = new String[capacity];this.size = 0;}private int hash(String key) {return key.hashCode() % table.length;}public void insert(String key) {int hash = hash(key);int i = 0;while (table[(hash + i) % table.length] != null) {i++;}table[(hash + i) % table.length] = key;size++;}public boolean search(String key) {int hash = hash(key);int i = 0;while (table[(hash + i) % table.length] != null) {if (table[(hash + i) % table.length].equals(key)) {return true;}i++;}return false;}
}

二、链式哈希(Chaining)

1. 定义

链式哈希是一种使用链表来解决哈希冲突的方法。在链式哈希中,每个哈希表的桶(bucket)中存储一个链表。当两个或多个键映射到同一哈希值时,这些键被存储在对应桶的链表中。

2. 工作原理

当元素被插入时,哈希函数计算出其哈希值,并将元素插入到对应桶的链表中。如果桶为空,创建新的链表并将元素加入其中。查找时,哈希值定位桶,然后遍历链表寻找元素。

3. 特点
  • 桶与链表结合:哈希表的每个桶可以存储多个元素,冲突的元素以链表的形式链接。
  • 动态增长:链表的长度不限,可以动态增长以存储任意数量的冲突元素。
  • 负载因子:哈希表性能受负载因子影响,合理的哈希函数和扩展策略有助于保持效率。
4. 优缺点
  • 优点

    • 简单删除:删除操作相对简单,只需从链表中删除节点,不影响整体结构。
    • 负载平衡:对于高负载因子,链表能有效处理大量冲突。
  • 缺点

    • 内存开销:每个链表节点需要额外存储指针,会增加内存消耗。
    • 查找时间:最坏情况下(所有元素哈希到同一个桶),查找时间为 O(n)。
5. 应用场景
  • 动态数据存储:适用于插入和删除频繁的场景。
  • 高负载因子:在负载较高时,链式哈希能更好地维持性能。
6. 示例代码(Java 实现链式哈希)
import java.util.LinkedList;public class ChainingHashTable {private LinkedList<String>[] table;public ChainingHashTable(int capacity) {table = new LinkedList[capacity];for (int i = 0; i < capacity; i++) {table[i] = new LinkedList<>();}}private int hash(String key) {return key.hashCode() % table.length;}public void insert(String key) {int index = hash(key);table[index].add(key);}public boolean search(String key) {int index = hash(key);return table[index].contains(key);}public void delete(String key) {int index = hash(key);table[index].remove(key);}
}

总结比较

方法冲突解决机制操作复杂度优点缺点
开放寻址法探查序列查找空位查找、插入:O(1),最坏:O(n空间效率高,不需要额外结构高负载时性能下降,删除复杂
链式哈希链表存储冲突元素平均:O(1),最坏:O(n)删除简单,负载高时仍保持性能内存开销大,链表操作较慢

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/466309.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

并查集(基础学习与应用)

并查集 基本原理&#xff1a; 对于多个集合&#xff0c;每个集合中的多个元素用一颗树的形式表示&#xff0c;根节点的编号即为整个集合的编号&#xff0c;每个树上节点存储其父节点&#xff0c;使得当前集合的每个子节点都可以通过对父节点的询问来找到根节点&#xff0c;根…

基于 Encoder-only 架构的大语言模型

基于 Encoder-only 架构的大语言模型 Encoder-only 架构 Encoder-only 架构凭借着其独特的双向编码模型在自然语言处理任务中表现出色&#xff0c;尤其是在各类需要深入理解输入文本的任务中。 核心特点&#xff1a;双向编码模型&#xff0c;能够捕捉全面的上下文信息。 En…

sql数据库-DQL-条件查询

条件查询 SELECT 字段列表 FROM 表名 WHERE 条件列表; 条件列表 比较运算符功能> 大于>大于等于 < 小于<小于等于等于!不等于between...and...某个范围之间&#xff08;闭区间&#xff09;IN(...)在in之后的列表中的值&#xff0c;多选一LIKE 通…

Android CCodec Codec2 (二十)C2Buffer与Codec2Buffer

在阅读Codec2框架代码时&#xff0c;我们可能会发现好几个名称中都带有“buffer”的类&#xff0c;如MediaCodecBuffer、ABuffer、CCodecBuffers、Codec2Buffer以及C2Buffer。它们分别是什么&#xff1f;各自承担着什么功能&#xff1f;它们之间有何联系&#xff1f;本文将围绕…

WPF怎么通过RestSharp向后端发请求

1.下载RestSharpNuGet包 2.请求类和响应类 public class ApiRequest {/// <summary>/// 请求地址/// </summary>public string Route { get; set; }/// <summary>/// 请求方式/// </summary>public Method Method { get; set; }/// <summary>//…

SQL Server 日志记录

SQL Server是一个关系数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;旨在有效地存储、组织、检索和操作大量结构化数据。SQL Server日志是监控数据库活动、排查问题和确保数据一致性的基础&#xff0c;这些日志记录了SQL Server实例中发生的事件的时间顺序。它们充当…

书生实战营第四期-基础岛第三关-浦语提示词工程实践

一、基础任务 任务要求&#xff1a;利用对提示词的精确设计&#xff0c;引导语言模型正确回答出“strawberry”中有几个字母“r”。 1.提示词设计 你是字符计数专家&#xff0c;能够准确回答关于文本中特定字符数量的问题。 - 技能&#xff1a; - &#x1f4ca; 分析文本&…

默认 iOS 设置使已锁定的 iPhone 容易受到攻击

苹果威胁研究的八个要点 苹果手机间谍软件问题日益严重 了解 Apple 苹果的设备和服务器基础模型发布 尽管人们普遍认为锁定的 iPhone 是安全的&#xff0c;但 iOS 中的默认设置可能会让用户面临严重的隐私和安全风险。 安全研究员 Lambros 通过Pen Test Partners透露&#…

双指针算法篇——一快一慢须臾之间解决问题的飘逸与灵动(3)

前言&#xff1a;本篇来到双指针算法介绍的最终篇&#xff0c;该文将通过三个同类型但难度逐渐累增的题目&#xff0c;再次强化对双指针算法的理解和运用。 相关题目及讲解 一. 两数之和 题目链接&#xff1a;LCR 179. 查找总价格为目标值的两个商品 - 力扣&#xff08;LeetC…

sparkSQL的UDF,最常用的regeister方式自定义函数和udf注册方式定义UDF函数 (详细讲解)

- UDF&#xff1a;一对一的函数【User Defined Functions】 - substr、split、concat、instr、length、from_unixtime - UDAF&#xff1a;多对一的函数【User Defined Aggregation Functions】 聚合函数 - count、sum、max、min、avg、collect_set/list - UDTF&#xff1a;…

Springcloud高校选课管理系统-计算机毕业设计源码27115

摘 要 随着信息技术的快速发展和高校信息化建设的深入推进&#xff0c;选课管理系统作为高校教育信息化建设的重要组成部分&#xff0c;其重要性和紧迫性日益凸显。传统的选课管理系统往往采用单体架构&#xff0c;存在系统耦合度高、可维护性差、扩展性不强等问题&#xff0c;…

ChatGPT 新体验:AI 搜索功能与订阅支付指南

就在凌晨&#xff0c;在 ChatGPT 迎来两周岁生日之际&#xff0c;OpenAI 重磅发布了 ChatGPT 的全新人工智能搜索体验。 期待已久的时刻终于到来&#xff0c; ChatGPT 正式转型成为一款革命性的 AI 搜索引擎&#xff01; 先来看看 ChatGPT 搜索&#xff1a;这次不是简单的加个…

奇瑞汽车:降阶模型在新能源汽车热管理仿真上的应用

随着新能源汽车的发展&#xff0c;对仿真技术的要求也越来越高。那么奇瑞汽车利用降阶模型在新能源汽车热管理仿真上做了哪些应用呢&#xff1f;本次内容主要从四个方面展开介绍&#xff1a; 1、 奇瑞汽车简介&#xff1b; 2、 热管理降阶模型开发的背景&#xff1b; 3、 高低…

RPC核心实现原理

目录 一、基本原理 二、详细步骤 三、额外考虑因素 RPC&#xff08;Remote Procedure Call&#xff0c;远程过程调用&#xff09;是一种计算机通信协议&#xff0c;也是一种用于实现分布式系统中不同节点之间进行通信和调用的技术。其实现原理主要可以分为以下几个步骤&…

HTML前端页面设计静态网站-仿百度

浅浅分享一下前端作业&#xff0c;大佬轻喷~ <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><title>百度&#xff08;伪&#xff09;</title><style>body {margin: 0;padding: 0;}.top-bar {dis…

Linux多线程(个人笔记)

Linux多线程 1.Linux线程概念1.1线程的优点1.2线程的缺点 2.Linux线程VS进程3.Linux线程控制3.1创建线程3.2线程tid及进程地址空间布局3.3线程终止3.4线程等待 4.分离线程5.线程互斥5.1互斥锁mutex5.2互斥锁接口5.3互斥锁实现原理5.4可重入VS线程安全 6.线程同步6.1条件变量6.2…

【MacOS实操】如何基于SSH连接远程linux服务器

MacOS上远程连接linux服务器&#xff0c;可以使用ssh命令pem秘钥文件连接。 一、准备pem秘钥文件 如果已经有pem文件&#xff0c;则跳过这一步。如果手上有ppk文件&#xff0c;那么需要先转换为pem文件。 macOS 的默认 SSH 客户端不支持 PPK 格式&#xff0c;你需要将 PPK 文…

基于CNN-LSTM的时间序列数据预测,15个输入1个输出,可以更改数据集,MATLAB代码

1. 数据收集与预处理 数据清洗&#xff1a;处理缺失值、异常值等。特征工程&#xff1a;提取有助于预测的特征。数据标准化&#xff1a;将时间序列数据标准化&#xff0c;使其具有零均值和单位方差&#xff0c;有助于模型训练。滑动窗口划分&#xff1a;将时间序列数据划分为多…

win 查看显卡支持 CUDA版本

在cmd 中执行 nvidia-smi 二、nvcc -V

Java算法OJ(6)归并分治

目录 1.前言 2.正文 2.1归并分治的概念 2.2计算数组的小和 2.2.1题目 2.2.2示例 2.2.3代码 2.3翻转对 2.3.1题目 2.3.2示例 2.3.3代码 3.小结 1.前言 哈喽大家好吖&#xff0c;今天继续来给大家带来Java算法——归并分治的讲解&#xff0c;学习这篇的前提可以先把…