IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> ?数据结构入门?——哈希表 -> 正文阅读

[数据结构与算法]?数据结构入门?——哈希表

目录

哈希表

概述

issue

一、什么是哈希表

二、哈希表的优缺点

(1)优点

(2)缺点

冲突的解决方法

(1)拉链法

(2)开放地址法

HASH表的基本操作


哈希表

概述

  • 哈希表(散列表),可以理解为Hash函数(散列函数)与链表结合共同实现的一种数据结构。与离散化思想类似,离散化可以理解为一种特殊的哈希。

issue

希望读者读完本文可以独立解决一下问题:

  1. 为什么用哈希表?

  2. 哈希表的优缺点

  3. 关于冲突以及结果方法

  4. 处理冲突的两种方式分别是什么?它们个在自己的领域有着怎样的优势

一、什么是哈希表

文章开头就已经提到,哈希表是一种在链表上做一些特殊操作的数据结构。那么它与链表有什么样的联系呢,我下面举个简单的例子:

图书馆有十万万图书,把它们随意放在书架上,此时书架上的书是没有顺序的,小王想找一本《C primer puls》,他只能从第一本图书开始找,一本一本遍历,这样复杂度会很高;

哈希表就是给这些图书编号放置,便于查找。如何给图书编号那就得靠哈希函数了,通过哈希函数对其进行特殊处理下标,并将其储存在数组中。

二、哈希表的优缺点

大家在刚才的描述中一定能看出哈希表的优缺点了,这里我总结一下 ,还是希望大家能独立思考

(1)优点

  1. 对于一些大数据多数据,hash表处理起来比较轻松

  2. 能够快速的 查,改,插,删元素 等操作

  3. 代码简单(自己想好hash函数就完成啦)

(2)缺点

  1. 在hash函数处理某些元素的时候,不免出现下标重复相同的情况,这种情况可以称作为冲突

  2. 哈希表中的数据都是没有顺序的

冲突的解决方法

前面提到的冲突,当两个或两个以上的下标相同时发生冲突,那么该如何处理这种情况呢,下面提到两种方法,拉链法和开放寻址法

这里比较懒用y总的图来形象的概括下

(1)拉链法

可以看出在重复下表的下面又开了一个数组,有点像邻接表。在这个数组将重复的全部装进去,这样在查找的时候只需要遍历这个数组就ok了;

这是第一种解决 冲突 的方法,但使用是还是需要考虑数组长度是否合适的

(2)开放地址法

这种方法简单来说就是当元素下标值发生冲突时,寻找空白的位置插入数据。

其实当发生冲突时,寻找空白的位置也有三种方法,分别是 线性探测二次探测再哈希法

1.线性探测

线性的意思是 :当发生冲突时,索引+1,查看此时位置是否为空,是的话插入,否则重复以上操作;

但这个方法的有一个致命的缺点,当很长一段长度都不为空时候上述步骤要重复很多次,这种现象称为聚集

那么我们将如何处理这种问题呢,接下来讲的二次探测来缓解这种情况

2.二次探测

二次探测 在线性探测的基础上,将每次探测的步长改为了当前下标值 index + 12index + 22index + 32 …… 直到找到空白位置插入元素为止

我们可以看到,二次探测 在一定程度上解决了 线性探测 造成的 聚集 问题,但是它却在另一种程度造成了一种聚集,就比如 122232 …… n2 上的聚集。所以这种方式还是有点不太好。

3.再哈希法

再哈希法 就是再将我们传入的值进行一次 哈希化,获得一个新的探测步数 step,然后按照这个步数进行探测,找到第一个空着的位置插入数据。这在很大的程度上解决了 聚集 的问题。

HASH表的基本操作

  1. 计算hash函数的值

  2. 定位到对应链表

O(1)的复杂度

今天时间有点赶,可能写的不够全也不够好,还有代码实现以及一些配图没有完成例子也没有多么生动,以后有时间会做修改,最后,希望大家指出我的不足,大家共同学习进步,早日进大厂!!

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-10-01 17:08:43  更:2021-10-01 17:11:03 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 4:54:28-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码