数组思想:数组之快

栏目:数据结构, 数组思想 作者:admin 日期:2018-10-26 评论:1 点击: 55 次

论访问快的数据结构,肯定会想到哈希表,那哈希表与数组有什么关系呢?我认为:哈希表的本质就是数组,它是数组的升华。查找元素的过程分为两大步骤:
第一:定位key的哈希值
第二:根据哈希值定位元素的位置,这个过程就是上面3提到的过程。
哈希表的查找过程,耗时在计算哈希上面,然后得出哈希值之后定位元素的过程是非常快的。
哈希表的本质就是数组,所以它也是连续的,就完全把它当做普通数组对待就行了。不要被哈希表这个名词所干扰,误认为是高大上的东西。
除了哈希表,数组与其他数据结构又有什么关系呢?我们知道,数据的存储分为:顺序存储和随机存储,顺序存储的代表是数组,随机存储的代表是链表,为什么数组比链表随机访问速度会快很多呢?
1 数组是顺序存储,在内存中是一个整块;
2 数组元素的定位分为两步:第一步,计算下标i*数组元素大小求出偏移地址;第二步:数组首地址+偏移地址就是元素i的地址。因为仅仅需要两步就能定位到数据,所以数组的访问速度非常快。
哈希是数组的升华,而数组是顺序存储,在速度上吊打随机存储的数据结构,这就数组思想:知道数组很快,而且知道它快的原因,还知道它的升华。

网站公告
欢迎加入金燕知识社群,更多介绍请查阅:知识社群

数组思想:数组之快:目前有1 条留言

  1. 沙发
    简简单单:

    解释的真通俗,受教了

    2018-10-26 下午1:22 [回复]

发表评论


------====== 本站公告 ======------
金丝燕网,即将迎来四周年!