程序员经验分享-hwhale

数据结构--哈希表，哈希函数（或者散列表、散列函数）

2023-11-02

 目录

哈希表的定义

处理冲突的方法--拉链法 

散列查找

常见的散列函数（构造哈希函数）

除留余数法

直接定址法

 数字分析法

平方取中法

处理冲突的方法--开放定址法

（1）线性探测法： 

（2）平方探测法

（3）伪随机序列发 

处理冲突的方法--再散列法 

总结 

 哈希表的定义

处理冲突的方法--拉链法 

散列查找

圈出来部分，分别是除了第一层查找1次，其他每个元素查找次数 

 

装填因子a=表中记录数/散列表长度

 

常见的散列函数（构造哈希函数）

除留余数法

直接定址法

 数字分析法

平方取中法

 

处理冲突的方法--开放定址法

 

（1）线性探测法： 

 把元素1放到数组2位置，然后接着算68，20....

  

 68和20按照哈希函数取余，分别是3，7，而数组下标3，7还没有存放与元素，所以没有冲突，可以直接放进数组对应的下标里面，如图：

接着放84时，按照哈希函数取余时6，6已经有元素放了，所以按照线性推测法 公式算，依次往后找，找到8下标没有元素，所以84放到下标8那里

存放84的结果如下：

 

然后是27： 

 

存放27的结果

 

删除操作 

 

 

（2）平方探测法

 

 

（3）伪随机序列发 

 

 存放结果：

处理冲突的方法--再散列法 

总结 

装填因子，线性探测法很重要

 

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

散列表

哈希算法

考研

学习

数据结构--哈希表，哈希函数（或者散列表、散列函数） 的相关文章

  • 断言简介说明

    转自 断言简介说明 下文笔者讲述断言简介说明 如下所示 断言简介 在Java中 assert关键字是从Java 4开始引入的 为了避免和老版本的Java代码中使用了assert关键字导致错误 Java在执行的时候默认是不启动断言检查的 这个

  • 后端代码审计——PHP数组

    文章目录 PHP数组 1 索引数组 2 关联数组 3 数组创建 3 1 直接赋值 3 2 array 语言结构 4 多维数组 4 1 创建多维数组 5 数组元素访问 5 1 组元素操作 5 2 元素操作 5 3 数组的遍历 5 4 for

  • win11 安装 Anaconda（2022.10）+pycharm（2022.3/2023.1.4）+配置虚拟环境

    目录 一 安装Anaconda 二 Anaconda配置环境变量 三 Anaconda更改虚拟环境安装路径 创建虚拟环境 四 安装pycharm 五 pycharm配置Anaconda环境 一 安装Anaconda 1 下载 官网慢 可以选

  • app渗透-外在信息收集

    app渗透 外在信息收集 5 外在信息收集 5 1外在抓包 frida r0capture 5 1 1 frida的安装和使用 1 安装 2 使用测试 5 2 1 r0capture使用 5 外在信息收集 5 1外在抓包 frida r0c

随机推荐

  • 问题 D: 数据结构练习 -- 栈的操作

    题目描述 对输入整数序列1 2 3 执行一组栈操作 输出操作的出栈序列 输入 每行是一个测试用例 表示一个操作序列 操作序列由P和Q两个符号组成 P表示入栈 Q表示出栈 每个操作序列长度不超过1000 输出 对每个操作序列 输出出栈序列 若

  • MySQL——数据的增删改

    2023 9 12 本章开始学习DML 数据操纵语言 语言 相关学习笔记如下 DML语言 数据操作语言 插入 insert 修改 update 删除 delete 一 插入语句 方式一 经典的插入 语法 insert into 表名 列名

  • 详解JavaNIO Buffer类的属性和方法

    前言 我们知道 Java中的NIO实际上使用的是多种IO模型中的IO多路复用策略 在NIO中 引入了Buffer缓冲区 Channel通道 Selector选择器三个概念 现在先看一下Buffer缓冲区的一些基本知识 介绍 NIO的Buff

  • mac os如何使用rz、sz

    1 什么是rz sz 在线上真实生产环境中总会有上传文件到服务器 以及从服务器下载文件的需求 rz sz应用广泛 由于发送和接收都是在服务器上进行的 所以 rz received 接收 意味着向服务器上传 sz send 发送 意味着从服务

  • 深度学习实战5-卷积神经网络（CNN）中文OCR识别项目

    文章目录 一 前期工作 导入库 图片生成函数 导入数据 生成数据集函数 二 CNN模型建立 三 训练模型函数 四 训练模型与结果 五 验证 大家好 我是微学AI 今天给大家带来一个利用卷积神经网络 CNN 进行中文OCR识别 实现自己的一个

  • 关于微软研究院（谢幸、郑宇研究员主导的）“智能城市”“智能生活”研究的一个归纳

    微软亚洲研究院基于GPS数据展开的研究工作 取得了另学术界瞩目的成就 从2008年开始每年都在顶级的计算机类会议上有文章发出 掀起了研究GPS数据智能化处理的热潮 他们的工作由谢幸研究员和郑宇研究员主导 实验数据采集主要有两个工程 1 Ge

  • 多线程（二）内存模型-线程安全

    转载地址 https github com CyC2018 Interview Notebook 七 内存模型 主内存与工作内存 对处理器上的寄存器进行读写的速度比内存快几个数量级 为了解决这种速度矛盾 在它们之间加入了高速缓存 所有的变量

  • python可视化-股票价格（自学实操）

    前言 数据来源 知乎数据分析课程 python数据分析和可视化实操 一 明确问题 对给定的五个公司股票数据进行对比分析 二 数据理解 部分数据展示 各字段含义 Date 日期 Open 开盘价 High 最高价 Low 最低价 Close

  • case when 作为条件_【SQL】区间（条件）分组统计

    简介 很多时候 我们都使用group by 进行分组 count 进行统计 两者结合可以进行聚合统计 假设我们有这样一张煤矿数据库表 table name coalmine columns id 煤矿ID bigint prod statu

  • 学习笔记 - git(项目所有权转移)

    git转移过程 git remote v 查看现在的远程链接是否是已转移的远程链接 是则不需要往下进行 否则进行下面的操作 git remote remove origin 删除远程连接 git remote v 查看远程仓库 这个时候没有

  • 程序员转行适合做什么?

    程序员可以转行做很多事情 这取决于他们的技能和兴趣 常见的转行方向包括 数据科学家 人工智能工程师 软件项目经理 网络架构师 系统管理员 数据分析师 云计算专家等 程序员的技能在很多领域都是有用的 所以他们可以考虑转行到相关的领域 重要的是

  • 微信小程序设置为体验版需要打开调试模式

    微信小程序在开发过程中可以发布体验版本进行调试 微信扫码后 需要手动打开开发调试 步骤如下图 1 前往体验版 2 点击右上角设置 3 点击开发调试 4 打开调试 注意点 清除微信后台 开发调试是否会自动关闭 安卓手机不会 ios的会

  • Weblogic漏洞 CVE-2021-2109 处理

    好记忆不如烂笔头 能记下点东西 就记下点 有时间拿出来看看 也会发觉不一样的感受 目录 一 前言 二 影响版本 三 漏洞查阅 四 漏洞修复 4 1 补丁包下载 4 2 安装补丁包 4 3 具体操作 一 前言 oracl 早就发布了weblo

  • npm install过程失败的几种处理方法

    npm install安装包过程失败的几种处理方法 npm install过程失败 第一种情况 首先经过npm install后 会生成node modules 先清除它 rm rf node modules 如果项目中有package l

  • 7.5.3 推断

    7 5 3 推断 贝叶斯网训练好之后就能用来回答 查询 query 即通过一些属性变量的观测值来预测其他属性变量的取值 例如 在西瓜问题中 若我们观测到西瓜色泽青绿 敲声浊响 根蒂蜷缩 想知道它是否为成熟 甜度如何 这样通过已知变量观测值来

  • 【Keil】warning: #550-D: variable "activeTaskID" was set but never used

    现象 warning 550 D variable activeTaskID was set but never used 描述 变量activeTaskID定义但从未使用 或者是 虽然这个变量你使用了 但编译器认为变量activeTask

  • JetBrains开发工具汉化

    文章目录 前言 一 打开扩展 二 搜索Chinese 并下载中文语言包 三 重启开发工具 总结 前言 相信很多人目前都在使用JetBrains的开发工具 IDEA PyCHarm PhpStorm CLion等 对于新手而言 英文界面可能使

  • C#winform——添加不同语言环境下的resx，使得显示文本能随语言环境变化

    添加不同语言环境下的resx 添加不同语言resx文件的两种情形 窗体控件 非窗体控件 为窗体控件添加不同语言resx文件 为非窗体控件添加不同语言resx文件 添加不同语言resx文件的两种情形 窗体控件 1 如下所示 需要在不同语言环境

  • 入门级测试Kotlin实现PopWindow弹窗代码

    入门级测试Kotlin PopWindow弹窗代码 文件名称 MainActivity Kt package com example alert import android app Dialog import android conten

  • 数据结构--哈希表，哈希函数（或者散列表、散列函数）

    目录 哈希表的定义 处理冲突的方法 拉链法 散列查找 常见的散列函数 构造哈希函数 除留余数法 直接定址法 数字分析法 平方取中法 处理冲突的方法 开放定址法 1 线性探测法 2 平方探测法 3 伪随机序列发 处理冲突的方法 再散列法 总结

热门标签