为什么hash作为内存使用的经典数据结构

2022-08-21 科技 98阅读
因为我想知其所以然,如何理解背后的原因,我花费点时间来学习一番。

我之前学过搜索引擎中的倒排索引,其中的单词词典就是使用hash方式实现:对关键词做hash值,同样hash值的关键词都归到一起。这是我通俗化接触hash应用开始。

我们使用hash寻找数据的时候,数据随机分散到各个物理位置。不是有序的数据。而内存设备也是随机访问设备。内存很适合用hash方式来读取数据。比如memcached、redis等这些内存缓存,都是使用key-value形式来读取数据的

内存是一个随机存储设备,随机存储设备,我觉得是相对顺序存储设备而言的。机械硬盘存储,读取速度会影响整体速度,比如就近读取就会快。主存的数据读取与先后顺序无关。是典型的随机访问设备。很适合hash数据结构查找。

如何理解内存中数据的读取与先后顺序无关? 熟悉了内存存储原理,才知道,为什么内存是随机存储设备。

借用网上别人的一张内存存储图:

这张图很好的帮我理解了内存的数据读取方式。感谢作者。

把内存里面的存储空间,看成是一个一个的单元格组成的矩阵,每个单元格就是存储数据的。

数据d1,d2,d3分别分散存储在内存中的各个单元格子里面。

要读取数据d1。通过一个行地址和一个列地址可以唯一定位到一个存储单元。

随便数据存储在哪个单元个子里面,都能通过行地址与列地址快速定位找到数据所在的单元格。

假设要读取数据d1、d2、d3。先读取d1,还是先读取d3,对于整体速度是没有影响的。因为定位每个单元格子所需要的操作是一样的(行地址与列地址)

所以,读取的速度是与读取顺序无关的。

而在硬盘中则不同,硬盘的磁头要进行定位,如何数据在磁头附近,则直接移过去即可。如果接下来要读取的数据不在磁头附近,又需要让磁盘片重新转一圈才行(磁头不转动,盘片转动,所以需要让数据所在区域转动到到磁头位置下,以便磁头读取数据),这就需要耗费磁盘i/o。在磁盘扇区,相临近的数据,能减少盘片转动,所以安排数据的先后读取顺序其实就是减少了盘片转动。比如把需要一起访问的数据放到同一个柱面上,就是一种方式。

这时候,理解了为什么内存很适合用hash方式存取数据。是与随机存储设备有关。

磁盘靠物理旋转来定位读取数据,于是存在寻道时间和旋转延迟。内存查找数据不存在这种问题。

有的对比,就更加了解硬盘为什么很适合用b树方式作为数据结构。不适合使用hash方式来组织数据。

可以这样理解:内存与磁盘存储的原理的不同,使得内存很适合hash方式访问数据,磁盘则很适合使用b树形式组织数据。
声明:你问我答网所有作品(图文、音视频)均由用户自行上传分享,仅供网友学习交流。若您的权利被侵害,请联系fangmu6661024@163.com