| |
|
开发:
C++知识库
Java知识库
JavaScript
Python
PHP知识库
人工智能
区块链
大数据
移动开发
嵌入式
开发工具
数据结构与算法
开发测试
游戏开发
网络协议
系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程 数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁 |
-> 数据结构与算法 -> ?数据结构入门?——哈希表 -> 正文阅读 |
|
[数据结构与算法]?数据结构入门?——哈希表 |
目录 哈希表概述
issue希望读者读完本文可以独立解决一下问题:
一、什么是哈希表文章开头就已经提到,哈希表是一种在链表上做一些特殊操作的数据结构。那么它与链表有什么样的联系呢,我下面举个简单的例子: 图书馆有十万万图书,把它们随意放在书架上,此时书架上的书是没有顺序的,小王想找一本《C primer puls》,他只能从第一本图书开始找,一本一本遍历,这样复杂度会很高; 哈希表就是给这些图书编号放置,便于查找。如何给图书编号那就得靠哈希函数了,通过哈希函数对其进行特殊处理下标,并将其储存在数组中。 二、哈希表的优缺点大家在刚才的描述中一定能看出哈希表的优缺点了,这里我总结一下 ,还是希望大家能独立思考 (1)优点
(2)缺点
冲突的解决方法前面提到的冲突,当两个或两个以上的下标相同时发生冲突,那么该如何处理这种情况呢,下面提到两种方法,拉链法和开放寻址法, 这里比较懒用y总的图来形象的概括下 (1)拉链法可以看出在重复下表的下面又开了一个数组,有点像邻接表。在这个数组将重复的全部装进去,这样在查找的时候只需要遍历这个数组就ok了; 这是第一种解决 冲突 的方法,但使用是还是需要考虑数组长度是否合适的 (2)开放地址法这种方法简单来说就是当元素下标值发生冲突时,寻找空白的位置插入数据。 其实当发生冲突时,寻找空白的位置也有三种方法,分别是 线性探测 、二次探测 、再哈希法 1.线性探测 线性的意思是 :当发生冲突时,索引+1,查看此时位置是否为空,是的话插入,否则重复以上操作; 但这个方法的有一个致命的缺点,当很长一段长度都不为空时候上述步骤要重复很多次,这种现象称为聚集 那么我们将如何处理这种问题呢,接下来讲的二次探测来缓解这种情况 2.二次探测 二次探测 在线性探测的基础上,将每次探测的步长改为了当前下标值 我们可以看到,二次探测 在一定程度上解决了 线性探测 造成的 聚集 问题,但是它却在另一种程度造成了一种聚集,就比如 3.再哈希法 再哈希法 就是再将我们传入的值进行一次 哈希化,获得一个新的探测步数 HASH表的基本操作
O(1)的复杂度 今天时间有点赶,可能写的不够全也不够好,还有代码实现以及一些配图没有完成例子也没有多么生动,以后有时间会做修改,最后,希望大家指出我的不足,大家共同学习进步,早日进大厂!!
|
|
|
上一篇文章 下一篇文章 查看所有文章 |
|
开发:
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- |
|
网站联系: qq:121756557 email:121756557@qq.com IT数码 |