数据结构和算法-哈希表(散列)1|学习笔记

简介: 快速学习数据结构和算法-哈希表(散列)1

开发者学堂课程【Go 语言核心编程 - 数据结构和算法: 数据结构和算法-哈希表(散列)1】学习笔记,与课程紧密联系,让用户快速学习知识。

课程地址:https://developer.aliyun.com/learning/course/627/detail/9865


数据结构和算法-哈希表(散列)1


 一、哈希表(散列)

1、实际的需求:

Google 公司的一个上机题:

有一个公司,当有新的员工来报道时,要求该员工的信息加入(id,性别,年龄,住址..),当输入该员工的 id 时,要求查找到该员工的所有信息。

要求:不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)

前提是自己设计

2、哈希表的基本介绍:

散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

如果把哈希表存放起来,就能自己做一个内存数据库,而且根据需求可以自己定制,如果不会这个,就只能用原始的一些方法去做。

哈希表的一个简单构造示意图:

image.png

一共十六根链表,不同的 id 分散到不同的链表去,在添加的过程中,按照从小到大的顺序。像0号链表,其中的 id 就是从小到大排列的。

3、使用 hashtable 来实现一个雇员的管理系统[增删改查]

>应用实例 google 公司的一个上机题

有一个公司当有新的员工来报道时要求将该员工的信息加入(id,性别,年龄,住址..)当输入该员工的 id 时要求查找到该员工的所有信息

要求

(1)不使用数据库尽量节省内存速度越快越好=>哈希表(列)

(2)添加时,保证按照id从低到高插入

>思路分析:

(1)使用链表来实现哈希表,该链表不带表头

即:链表的第一个结点就存放员信息

(2)思路分析画出示意图

(3)代码实现[增改查(显示所有员工,按id查询)]

主要完成增加和查询

>基于 hashtable 的雇员关系系统的思路分析:

(1)首先先建一个结构体,会出现一个含有七个链表的数组。

(2)七个元素分别是:LinkArr[0]、LinkArr[1]等等。

(3)hashtable 是一个结构体:

 struct{LinkArr[7]EmpLink}

(4)、EmpLink 是一个雇员链表结构体:

  struct{Head * Emp}

(5)、雇员与雇员之间会形成链表,其 id 会从小到大进行设计。  

(6)、id 的结构体:

 struct Emp{Id int Name string Next * Emp},它实际上指的是雇员图层。

(7)、每一个链表里面含有一个指向雇员的指针。

image.png

蓝色代表的是链表数组(一共有七个),里面的框是元素。元素里面具体放的是雇员链表。后面橙色框是代表的雇员他们会形成一共链表,而且他们的id 会从小到大进行排列。查询时也是在七个链表中找,而不是一整个数据库去找。橙色也是一个个结构体,一个个雇员信息,也是指向下一个节点的指针。

要完成这样的思路:首先要有一个哈希表,里面存了七个链表,他是一个链表数组,而且每一个链表里面指向一个雇员链表,这个链表里面有一个指向雇员的指针,通过这些来完成增删改查。

打个比方:比如现在有一根链表,这个链表里面有1000个雇员,这个里面没有散例,且只有一根链表,其中要查询id 为998的,如果是单链表的话就要一个个查,需要查998次才能查到,但是如果是用这个方法,就可以在存的时候输入998%7=?,那么在插入的时候就知道这个998是在某一个链表中,再查的时候就能找到998的位置,在指定的链表中查,这样时间就减少了很多,查询速度变快了。他的价值在于可以提高速度,在开发的时候用这样的方法,速度就大大提升了。

例如:

假设同时在线人数1000万,传统的方法就是操作数据库。如果按传统方法操作数据库,后果就是有一个人的状态发生了变化,或者有一个人要来读取一个ID的状态,那用户只能操作输入,这个量是很大的,对数据库的冲击很大。但是如果做一个优化维护用户的状态假设每个人都去操作数据库,这个数据库压力太大了,换一个思路因为知道用户的状态不是一个特别重要的数据。因为用户状态可能会是离线在线或者版本,不是特别重要必须入库的数据。我们就可以采取做一个结构体。比如

struct userState{id int state byte}

用2000个这个列表把它串起来。那这样的效果的好处,虽然可能会浪费一点内存但是在操作一个用户的状态的时候,不管是修改还是查询速度都会变快。

相关文章
|
机器学习/深度学习 算法 算法框架/工具
深度学习小白学习路线规划
深度学习小白学习路线规划
|
XML Web App开发 人工智能
SVG图像——为 PPT 增添视觉趣味/03/O365智能系列(二)
SVG图像——为 PPT 增添视觉趣味/03/O365智能系列(二)
1850 0
SVG图像——为 PPT 增添视觉趣味/03/O365智能系列(二)
|
12月前
|
Java 编译器 Android开发
Kotlin语法笔记(28) -Kotlin 与 Java 混编
Kotlin语法笔记(28) -Kotlin 与 Java 混编
181 2
|
Java 开发工具
通过Java SDK调用阿里云模型服务
在阿里云平台上,可以通过创建应用并使用模型服务完成特定任务,如生成文章内容。本示例展示了一段简化的Java代码,演示了如何调用阿里云模型服务生成关于“春秋战国经济与文化”的简短文章。示例代码通过设置系统角色为历史学家,并提出文章生成需求,最终处理并输出生成的文章内容。在实际部署前,请确保正确配置环境变量中的密钥和ID,并根据需要调整SDK导入语句及类名。更多详情和示例,请参考相关链接。
|
域名解析 网络协议 物联网
深度解析:UDP协议及其工作机制与优点
【8月更文挑战第20天】
705 0
|
12月前
|
Java 调度
HashMap为什么会死循环?
本文分析了在Java中HashMap导致死循环的原因,主要由于在JDK 1.7及之前版本中,多线程环境下进行扩容操作时,头插法导致的链表反转,以及线程调度问题,从而形成循环链表。
448 0
HashMap为什么会死循环?
|
Rust Cloud Native 安全
哇塞!Rust 在云原生环境中搞大事啦!构建微服务竟如此酷炫,你还不来看看?
【8月更文挑战第31天】《构建微服务:Rust 在云原生环境中的实践》探讨了 Rust 语言凭借其内存安全、高性能及可靠性等特性,在快速发展的云计算领域构建微服务的优势。书中介绍了选择合适框架(如 Axum 和 Tide)、容器化部署、服务间通信及确保服务可靠性等方面的内容,并展示了 Rust 在云原生环境中的广泛应用前景。
608 1
|
10月前
|
IDE iOS开发 Python
小白如何开始使用通义灵码(含安装IDE、安装灵码插件)
PyCharm 和 IntelliJ IDEA 下载安装及通义灵码插件下载安装说明
8460 9
|
测试技术
loadrunner 场景设计-集合点设置
loadrunner 场景设计-集合点设置
558 0
|
Java 程序员 API
Hutool工具使用(验证码生成、Excel文件的导入、导出)
🍅程序员小王的博客:程序员小王的博客 🍅 欢迎点赞 👍 收藏 ⭐留言 📝 🍅 如有编辑错误联系作者,如果有比较好的文章欢迎分享给我,我会取其精华去其糟粕 🍅java自学的学习路线:java自学的学习路线
1281 0
Hutool工具使用(验证码生成、Excel文件的导入、导出)