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

一、开放寻址法(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)删除简单,负载高时仍保持性能内存开销大,链表操作较慢

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

算法通关(4)-- 前缀树

前缀数原理和代码 原理 前缀树&#xff08;Trie树&#xff09;&#xff0c;也称为字典树&#xff0c;是一种用于高效存储和检索字符串的数据结构。它是一种树形结构&#xff0c;能够利用字符串的公共前缀来减少存储空间和查询时间。 现在有“acb”,"cba","ac…

CSS3新增渐变(线性渐变、径向渐变、重复渐变)

1.线性渐变 代码&#xff1a; 效果图&#xff1a; 使文字填充背景颜色&#xff1a; 效果图&#xff1a; 2.径向渐变 代码&#xff1a; 效果图&#xff1a; 代码图&#xff1a; 效果图&#xff1a; 3.重复渐变 代码&#xff1a; 效果图&#xff1a;

Python 学习完基础语法知识后,如何进一步提高?

入门Python后&#xff0c;就可以拿些小案例练手了&#xff0c;这时候千万不要傻乎乎地成天啃语法书。 编程是一门实践的手艺&#xff0c;讲究孰能生巧。不管是去手撸算法、或者照葫芦画瓢写几个小游戏都可以让你的Python突飞猛进。 之前看github比较多&#xff0c;推荐给大家…

blender导入的图片渲染看不见,图片预览正常,但渲染不出

在使用Blender时&#xff0c;我们经常会遇到导入图片后在预览渲染中显示&#xff0c;但在实际渲染时图片消失的问题。本文将提供详细的解决方法&#xff0c;帮助大家解决“Blender导入的图片渲染图像不显示”的问题。 问题原因 导入的图片在Blender中只是一张图&#xff0c;并…

【数据结构】选择排序——选择排序 和 堆排序

选择排序 和 堆排序 一、选择排序选择排序的思路及其代码选择排序的弊端 二、堆排序三、速度对比同时排10000个数同时排100000个数同时拍500000个数堆排 1 亿个数 一、选择排序 选择排序的思路及其代码 选择排序思路很简单 就是经过将数组遍历选择最小值 将最小值位置的数与数…

Docker在CentOS上的安装与配置

前言 随着云计算和微服务架构的兴起&#xff0c;Docker作为一种轻量级的容器技术&#xff0c;已经成为现代软件开发和运维中的重要工具。本文旨在为初学者提供一份详尽的指南&#xff0c;帮助他们在CentOS系统上安装和配置Docker及相关组件&#xff0c;如Docker Compose和私有…

大数据新视界 -- 大数据大厂之 Impala 性能优化:数据存储分区的艺术与实践(下)(2/30)

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…

CLIP论文CLIP 改进工作串讲

文章目录 CLIPViLTCLIP 改进工作串讲Lseg&#xff08;Language -driven semantic segmentation)Group ViT&#xff08;Semantic Segmentation Emerges from Text Supervision&#xff09;ViLDGLIP_V1/V2&#xff08;Ground Language-Image Pre-train&#xff09;CLIP PassoCLIP…

C++:set详解

文章目录 前言一、set概念介绍二、set的使用1. 插入删除相关2. 查找相关1&#xff09;find2&#xff09;count3&#xff09;lower_bound与upper_bound4&#xff09;equal_range 三、set的值是不能修改的原理四、基于哈希表的set总结 前言 根据应用场景的不同&#xff0c;STL总…

【静态页面】尚品汇 1、设计稿分析及资源准备

目录 1. 准备工作2. 理解设计3. 规划项目结构 1. 准备工作 安装必要的工具&#xff1a;确保你的开发环境已经准备好&#xff0c;包括文本编辑器&#xff08;如 VSCode&#xff09;、浏览器等。获取设计文件&#xff1a;获取UI设计稿或者设计文件链接&#xff0c;并确保可以访问…

小时收入:衡量工作效率与个人自由的标准

小时收入&#xff0c;就是按照小时来计算一个人的收入。比如&#xff0c;一个月一共工作200小时&#xff0c;获得的总收入是20000元&#xff0c;那么小时收入就是100元/小时。 小时收入可以反应一个人的赚钱效率。 可能两个人的月收入一样&#xff0c;但是付出的总工作时间不…

RFID文件柜在文件管理中的作用

一、RFID文件柜系统概述 1.1 RFID技术简介 RFID&#xff08;Radio Frequency Identification&#xff0c;无线射频识别&#xff09;技术是一种非接触式的自动识别技术&#xff0c;它通过无线电讯号识别特定目标并读写相关数据&#xff0c;无需识别系统与特定目标之间建立机械…

mysql代码生成器

项目 pom 文件内容 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.org/…

域控操作二十四:主域故障辅域接替

模拟环境&#xff1a;上海DC1故障无法开机&#xff0c;导致只有一个DNS的电脑无法上网&#xff08;实际可以添加DC2但是为了实验就不说了&#xff09; FSMO还在DC1上 使用powershell把角色迁移到DC2 ntdsutil roles connections connect to server DC2SHA.whbk.cn quitSeize …

Redis(2):内存模型

一、Redis内存统计 工欲善其事必先利其器&#xff0c;在说明Redis内存之前首先说明如何统计Redis使用内存的情况。 在客户端通过redis-cli连接服务器后&#xff08;后面如无特殊说明&#xff0c;客户端一律使用redis-cli&#xff09;&#xff0c;通过info命令可以查看内存使用情…

数据分析:宏基因组DESeq2差异分析筛选差异物种

禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍原理:计算步骤:结果:加载R包准备画图主题数据链接导入数据Differential abundance (No BP vs 2BP TA)构建`countData`矩阵过滤低丰度物种构建DESeq数据对象DESeq2差异分析画图Di…

泷羽sec学习打卡-shodan扫描4

声明 学习视频来自B站UP主 泷羽sec,如涉及侵权马上删除文章 笔记的只是方便各位师傅学习知识,以下网站只涉及学习内容,其他的都与本人无关,切莫逾越法律红线,否则后果自负 关于shodan的那些事儿-4 一、shodan4如何查看公网ip&#xff1f;如何查看自己的ip&#xff1f;如何查看出…

abap 可配置通用报表字段级日志监控

文章目录 1.功能需求描述1.1 功能1.2 效果展示2.数据库表解释2.1 表介绍3.数据库表及字段3.1.应用日志数据库抬头表:ZLOG_TAB_H3.2.应用日志数据库明细表:ZLOG_TAB_P3.3.应用日志维护字段配置表:ZLOG_TAB_F4.日志封装类5.代码6.调用方式代码7.调用案例程序demo1.功能需求描述 …

Spark中的shuffle

Shuffle的本质基于磁盘划分来解决分布式大数据量的全局分组、全局排序、重新分区【增大】的问题。 1、Spark的Shuffle设计 Spark Shuffle过程也叫作宽依赖过程&#xff0c;Spark不完全依赖于内存计算&#xff0c;面临以上问题时&#xff0c;也需要Shuffle过程。 2、Spark中哪…