美文网首页
算法和数据结构1.6哈希表

算法和数据结构1.6哈希表

作者: 数字d | 来源:发表于2019-07-25 23:38 被阅读0次

哈希表的存储是由键(key)和值(value)组成的数据。

例如我们对多个人的性别进行存储,key值是人的姓名,value值是人的性别。

let arr = [
"Joe":"M",
"Sue":"F",
"Dan":"M",
"Nell":"F",
"Ally":"F",
"Bob":"M",
]

上面代码,为了和哈希表进行对比,先将数据存储到数组中去。

假设一种场景,我们要找到Ally的性别,按照数组的操作,我们从下标为0的位置开始找姓名为Ally的,依次往下,下标为0123时候都不是Ally,直到下标为4的时候,我们把键对应的值取出就知道Ally的性别为F(女)了。

数据量越多,线性查找耗费的时间就越长。由此可知道:由于数据查询比较耗时,所以此处并不适合使用数组来存储数据。

但是使用哈希表便可以解决这个问题。首先准备好数组,我们用一个长度为5的数组来存储数据。

哈希表存储数据流程:

先存第一个人的姓名Joe和性别M,
步骤:1.使用哈希函数(Hash)计算Joe的键,也就是字符串“Joe”的哈希值。得到的结果是4928.
2.将得到的值4928除以数组长度5,记作4928 mod 5 = 3. 所得的余数是3。
3.所以最终Joe的运算结果是3,因此我们将Joe的数据存入下标数组下标是3的位置。

对于arr中的所有信息都操作以上步骤。

但是这样事情还没结束

冲突

Nell的哈希值是6276 ,mod 5 的结果是1.Sue的哈希值是7291,mod 5的结果也是1.这种存储位置重复了的情况叫做“冲突”。遇到这种情况,可以使用链表在已有的数据后面继续存储新的数据。

//个人思考:在这里来看,原有设定的数组类型就不属于真正意义上的数组,因为传统意义上的数组中的每个元素的类型是一样的。
//而这种结构既存储字典,又存储链表的类型属于哈希表。
//swift中的元组也是能存储多种类型的数据结构,只是不知道有没有区别
//传统意义上的数组中第3个位置不存数据,第四个位置存数据不知道会发生异常情况吗

当数据存储完毕之后,用来存储数据的这个特殊的数组叫做哈希表。

哈希表的数据查询方法:

如果我们想要查询Dan的性别,先计算Dan的哈希值,然后对其进行mod运算。最后得到的结果是4.
于是我们直到它存储在下标为4的位置。直接就得出Dan的性别为M。

如果我们想要查询Ally的性别,同样的方法计算出来位置,最终发现3号下标的位置存储的不是Ally而是Joe,此时我们就需要队Joe所在的链表进行线性查找。

由此才能查找到键值为Ally的数据。便知道Ally的性别为女性(F)。

总结:

在哈希表中,我们可以利用哈希函数快速访问到数组中的目标数据。如果发生哈希冲突,就用链表进行存储。这样一来,不管数据量多大,我们都能灵活应对。

如果数组空间太小,使用哈希表容易发生冲突,线性查找的频率会更高。

如果数组空间太大,就会出现很多的空的下标,造成内存的浪费。

因此,给数组设定合适的空间非常重要。

其他应用场景

因为哈希表在数据存储上的灵活性和数据查询的高效性,编程语言的关联数组等也常常会使用到它。

相关文章

  • 「Redis源码解读」—数据结构(二)哈希表

    Redis的字典使用哈希表作为底层实现 知识点 1.数据结构 哈希节点 哈希表 类型处理函数 2.哈希 哈希算法 ...

  • 算法和数据结构1.6哈希表

    哈希表的存储是由键(key)和值(value)组成的数据。 例如我们对多个人的性别进行存储,key值是人的姓名,v...

  • MySQL索引简述--哈希索引

    哈希算法 哈希算法时间复杂度为O(1),且不只存在于索引中,每个数据库应用中都存在该数据结构。 哈希表 哈希表也为...

  • 数据结构和算法

    1.哈希表哈希算法详解(附带 iOS 开发中实际应用) 2.链表iOS 数据结构之链表

  • hash-table基础以及一些运用例子

    最近在复习算法和数据结构 ,这章把hash表的概念和相关题目进行汇总。 一、前言 1.1、哈希表和数组...

  • 安卓开发者的知识清单

    临近学校课程结束,回顾和梳理了下几门主要课程的脉络: 1.数据结构和算法基础数据结构:数组、链表、栈、队列、哈希表...

  • leetcode和牛客网刷题

    在上学时学过《数据结构和算法》这门课,当时学习了数组、链表、哈希表、二叉树、图等数据结构,还有排序算法、二分查找、...

  • 刷穿剑指offer-Day14-哈希表I 基础知识整理

    刷穿剑指offer-Day14-哈希表I 基础知识整理 引子 哈希表作为算法解题中的top数据结构,因为其查找、插...

  • iOS标准库中常用数据结构和算法之哈希表

    上一篇: iOS标准库中常用数据结构和算法之二叉排序树 ?哈希表 系统提供一个全局的key为字符串的哈希表。并提供...

  • MySQL索引和锁

    Mysql索引使用的数据结构主要有BTree索引 和 哈希索引 。对于哈希索引来说,底层的数据结构就是哈希表,因此...

网友评论

      本文标题:算法和数据结构1.6哈希表

      本文链接:https://www.haomeiwen.com/subject/qdqlrctx.html