数据映射--映射概述

简介:

上周是硬件,本周终于来到软件领域,明确的欠一个帐,文件系统这块因为东西比较多,我还没完全总结好,先欠着~

本周,让我们做一些准备,来谈谈映射。计算机就是个分型的系统,而映射这种数据结构,是计算机中非常基础和常见的一种数据结构, 从cpu到文件存储,再到分布式文件存储,其核心都是映射。

抄书: 映射就是: 使得对A中的每个元素a,按法则f,在B中有唯一确定的元素b与之对应,则称f为从A到B的映射,记作f:A→B。 哈哈,数学上的定义是最清晰和明确的。也可以写作y = f(x)

举个例子: 给定一个映射M,令 1 – > a , 2 –> c , 3 -> d 。 求3所对应的元素的时候,M应该返回的元素是 d 。

为什么在准备章节,需要先理解映射呢?自然是因为用的地方太多了 - -。。

当你希望从文件系统中找到标记为ADEADDAAD12AS的块所对应的数据的时候,你需要用到映射。

当你写的程序需要用到方法指针的时候,你需要用到映射。

当你从网络中获取了数据的时候,你需要用到映射。

当你需要从数据库内取出一条记录的时候,你需要用到映射。

甚至当你敲击键盘的时候,你也一样需要用到映射,键盘会将你的按键映射到计算机内的一种电信号。

自然而然的,在我们的海量数据处理中,映射也是整个体系中最为重要的核心组成部分,无论是RDBMS,图数据库,还是NoSQL引擎,他们底层的核心都是映射,而一个经过仔细优化的映射实现将能够直接的决定我们存储实现的所有技术特性。

怎样? 能够感受到映射的重要性了么? 既然这么重要还不赶紧往下看?!~

想实现这样的映射关系,在计算机程序里已经有了现成的方式了,那就是一个方法(method)

int get(int key){}

这就是一个最简单的方法了。 “get” 这就是方法的名字(可以对应函数下标),int key是入参(可以对应函数输入条件x),返回值是个int ,也就是y。

下面我们举一个例子,来实际的感受一下如何实现一套高效的映射。

假设我们需要找到一系列的函数实现,能够使得2 -> 4 , 1 -> 2 , 4 - > 8 ,3 -> 6 ,这样,当我给定key=1的时候,这个函数应该返回2,而给定key=2的是时候,函数应该返回4 。我们来看看,在计算机领域有哪些比较常用的方式和方法。

1.       使用集合类数据结构

这也应该是最容易想到的一种存放映射关系的方法了吧。在数据结构中,有很多种结构体可以支持这样的一个容器,比如使用数组,链表,二叉树,都可以使用类似的方式来存放这些数据。他们的特征各不相同,这也是我在这一章的后面要介绍的结构体中的重要主题。这里,为了帮助理解,我们以数组作为最简单的实现样例吧。

我们可以让数组里的每一个元素都是一个key->value pair。如下图所示

2->4

1->2

4->8

3->6

这样,当我要寻找key=2所对应的数据的时候,只需要遍历这个数组,找到key=2的元素,然后返回这个元素的value = 4就行了。

这种方式的适应性是最好的,因为不需要理解这些元素的内在联系。不过也有代价,就是需要付出很多的空间成本。

2.       定义一个函数

对于2 -> 4 , 1 -> 2 , 4 - > 8 ,3 -> 6这样的两组数据之间的对应关系,我们可以用一个算法 f(x) = 2x. x属于1~4

用上面的算法,就可以表示上面的这个映射的关系了。 使用这种方式的好处很多,比如空间节省,复杂度比较低,但是他有一个比较大的劣势,就是不是所有的数据都可以很容易的表示为上面的那种方式,因为需要理解元素之间内在的联系,并且这些元素本身必须有规律能够被认识才行。

3.       写一段穷举的算法

我们仍然使用1 -> 2 , 2 -> 4 , 3 -> 6 , 4 - > 8这样的两组数据之间的对应关系。

使用以下算法:

f(x) =

{

if(x == 1)

return 2;

else if(x == 2)

return 4;

else if(x == 3)

return 6;

else if (x == 4)

return 8;

else

throw exception;

}

使用这种算法,可以针对一些特殊情况进行特殊的处理,不过主要的代价是。。每次增加一个函数都需要咱去写代码儿。。 这事儿就有点儿二了。。。哈哈

在这三类中,后面这两类不大适合在我们的数据存储领域内使用,所以,我们将映射的概念进行一下收缩,后面的主要篇幅,就来介绍一下集合类。

我们还以刚才的例子来做分析。

假设我们需要找到一系列的函数实现,能够使得2 -> 4 , 1 -> 2 , 4 - > 8 ,3 -> 6 ,这样,当我给定key=1的时候,这个函数应该返回2,而给定key=2的是时候,函数应该返回4 。

在开始的时候,我们只采用了简单的数组结构,让数组里的每一个元素都是一个key->value pair。如下图所示

2->4

1->2

4->8

3->6

在查询的时候,我们选择的方式是遍历整个数组,找到要求的key后,返回这个key对应的value 。

这种方式虽然能够正确的返回数据,但是,效率明显是太低了。比如,如果这个数组的写入了100W的数据,那么如果要找到一个要求的数据,在最坏情况下,需要遍历整个数组才能取到所有数据。效率太低了这。。

于是,就自然而然的有个需求:能否找到更快的方式来查找数据呢?

在数据查找领域,核心的算法就俩,一个么叫二分查找,时间复杂度O(log2N),一个么就是hash..O(1)

二分查找的核心要求主要有仨:

1.       数据必须有序。

2. 可以快速的从数据中找到指定位置的数据。

3. 可以获知数据总个数

为了查找效率能够到达log2N,我们来看看,如果要查找到key = 3这个数据,具体如何操作。

我们先对数据排序

1->2

2->4

3->6

4->8

然后,就可以进行折半查找了。

另外一种方案就是hash

主要策略其实是利用hash函数对原始数据做一次预先的计算映射。

比如我可以选择一个hash函数 key % 3

每次插入数据的时候,都先算一下hash函数后,才插入到一个size是3的数组里面

3->6

1->2

2->4

这几个数字相对的比较好处理,但是4->8这个数据怎么办呢?

如果这个数据计算一下hash 函数 key % 3 = 4 % 3 = 1,这个数据应该也被写入到位置为1的这个的地方,但是,这个地方已经有一个数据1->2了,应该怎么办呢?

这在hash函数里面有个专业的名词,就叫碰撞。

碰撞有很多种不同的处理方式,不过这里我只介绍一种,在java中比较常见的模式:做一个链表放在后面

693f0847gx6BzyZWxrZ4b&690

 

这样,在查询的时候,如果需要4->8这个数据,那么 也先运算一下hash函数

key % 3 = 4 % 3 = 1 。所以在位置等于1的槽位上进行查找,因为第一个值是1->2不符合要求,所以指针下移,找到4->8,符合要求,返回即可。

上面,我们就介绍了能够提升查询速度的两套主要的思路。

看起来挺简单,其实不然,虽然核心思路简单,但是需要有很多其他的领域的不同选择,导致了完全不一样的算法结构。而面向的问题不同,解决的方案也就不同,我们来看看还有哪些主要的需求导致了我们实现上的不同呢?

1.       是否支持范围查找?

有些时候,一个数据结构需要进行范围查询,比如以时间作为key的数据,那么一般来说都会需要查询某个时间范围内的所有结果,对于这类的查询,支持范围查询是个必要的条件,不过有些数据结构则可能不能够支持范围查询。

2.       集合是否能够随着数据的增长而自动扩展?

大部分情况下,其实我们都很难在开始的时候预测到我们的这些数据结构中到底会有多少的数据,如果能够随着数据的增长而自动扩展,我们就不需要担心集合太小,数据太多,也不需要担心预先申请的空间太大,资源浪费了~ 可惜,数组不能自动扩展= =。。

3.       读写性能指标?

这应该是所有集合类都要努力追求和优化的东西~~~hoho

4.       是否面向磁盘结构?

这是个很重要的指标,什么叫面向磁盘的结构呢?为什么btree , LSM就适合在磁盘上存储呢? 本章后面章节会有详细介绍。

5.       并行指标?

当前数据结构是否能够支持并行写入和读取,在多核架构下是非常重要的一个指标。

6.       内存占用

以上的结构基本上能够涵盖一个集合的大部分技术特征了,而不同的集合类在以上这些特征上的不同选择也直接决定了性能的好坏,而无论是nosql还是RDBMS, 其性能最终的决定性因素都在于集合上的选择。在后面,我会选择几类常见的,比较典型的存储结构,以上面的这几个维度来进行一下分析,希望能够让大家在理解了这些存储的技术特性后,也能够对目前市面上常见的存储的性能进行更准确和更客观的估测 :)

相关文章
|
C#
C#—Collection was modified;enumeration operation may not execute
错误 Collection was modified; enumeration operation may not execute翻译是 集合已修改;枚举操作可能无法执行。也就是说我们在遍历集合等可迭代元素时,进行了集合的修改导致的错误。本质上因为Collection返回的IEnumerator把当前的属性暴露为只读属性,所以对其的修改会导致运行时错误,只需要把foreach改为for来遍...
784 0
|
Oracle 安全 算法
重磅!JDK 17 发布,Oracle 宣布从 JDK 17 开始正式免费。。
JDK 16 刚发布半年(2021/03/16),JDK 17 又如期而至(2021/09/14),这个时间点牛逼啊,蹭苹果发布会的热度?记得当年 JDK 15 的发布也是同天,巧了。。
重磅!JDK 17 发布,Oracle 宣布从 JDK 17 开始正式免费。。
|
Oracle 关系型数据库
集成平台即服务(iPaaS)软件
本文研究全球及中国市场集成平台即服务(iPaaS)软件现状及未来发展趋势,侧重分析全球及中国市场的主要企业,同时对比北美、欧洲、中国、日本、东南亚和印度等地区的现状及未来发展趋势
|
存储 Web App开发 运维
发布、部署,傻傻分不清楚?从概念到实际场景,再到工具应用,一篇文章让你彻底搞清楚
部署和发布是软件工程中经常互换使用的两个术语,甚至感觉是等价的。然而,它们是不同的! • 部署是将软件从一个受控环境转移到另一个受控环境,它的目的是将软件从开发状态转化为生产状态,使得软件可以为用户提供服务。 • 发布是将软件推向用户的过程,应用程序需要多次更新、安全补丁和代码更改,跨平台和环境部署需要对版本进行适当的管理,有一定的计划性和管控因素。
3589 1
|
SQL 存储
数据权限就该这么实现(实践篇),yyds!
数据权限就该这么实现(实践篇),yyds!
988 0
|
安全 网络安全 数据库
常用网络安全数据集来源
常用网络安全数据集来源
633 1
|
Web App开发 监控 UED
如何解决Angular中的Error: HTTP request failed, call timeout问题
在Angular应用中,遇到HTTP请求超时错误`Error: HTTP request failed, call timeout`时,可通过多种途径解决。首先,可增加请求超时时间,Angular默认无超时限制,设置合理的超时时间如5秒有助于避免长时间等待无响应。其次,检查服务器响应时间,利用开发者工具监控网络请求,优化服务器端代码或调整超时值。最后,确认网络连接稳定性,使用`navigator.onLine`检测网络状态,并在不同网络环境中测试。这些策略共同作用,能够有效提升应用的稳定性和用户体验。
683 1
|
存储 安全 算法
代码混淆和加固,保障应用程序的安全性
代码混淆是将源代码进行加密和优化,使得反编译者难以理解和还原源代码的过程。通过替换变量名、类名等信息为无意义的字符,代码混淆使得反编译后的代码难以理解和维护,从而提高了应用程序的安全性。 代码加固是对已经混淆的代码进行二次保护,防止破解者通过静态或动态分析手段获取到关键算法和逻辑。代码加固可以添加额外的安全层,包括加密、反调试、反动态调试、反内存dump等,从而增强应用程序的抗攻击能力,以IPA Guard为例,。
|
人工智能 自然语言处理 区块链
什么是token?3分钟带你看懂
`Token`在人工智能领域指的是文本处理的最小单元,用于大语言模型如LLM,它可以是单词、字母等。在模型运作中,输入的文本被转化为tokens,模型通过分析上下文tokens预测并生成输出。模型的上下文(窗口)长度限制了处理的token数量,影响性能和用户体验。此外,`token`也与收费计量单位相关,大模型服务商常按token量计费。同时,`AI token`在某些场景下代表代币,用于应用程序交易、服务和投资,有时扮演加密货币角色。Token在人机交流中起到桥梁作用,促进了通用人工智能的普及和发展。
|
开发框架 .NET C#
探索VB.NET:了解.NET Framework下的Visual Basic
【4月更文挑战第27天】Visual Basic进化为VB.NET,融入.NET Framework,提供面向对象编程、泛型、LINQ等特性。VB.NET是强类型语言,支持类型推断,通过Windows Forms和WPF构建桌面应用。广泛应用于企业级、Web和数据处理开发,是易学且功能强大的编程工具。随着.NET版本更新,VB.NET的应用仍具价值,适合初学者和资深开发者。
394 1