数组查询为何比链表快

关于基础的进一步探索

  • 寻址操作上面,链表远比数组多

当CPU进行寻址时,数组只需要知道【基地址+(元素大小)*k】,就可以找到第k个元素的地址,取地址即可知道元素的值,但是在链表中,找到第k个元素一定要先找到第(k-1)元素,查看其next域,知道第k个元素的地址,然后再一次从头开始进行寻址操作,当数据量比较大,或者是查询操作比较多的时候,数组和链表之间在查询方面的差距会很大。

  • CPU缓存的局部性原理

根据空间局部性,CPU缓存会把一部分的内存空间读入,因为数组是地址连续的数据结构,所以数组的全部或者一部分元素会被读入缓存中,这样就发挥了缓存的优势,而链表几乎每一次都需要CPU直接访问内存进行查找

但是链表在进行增删上面还是存在优势,当然这不是这篇博客讨论的问题。

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/数组查询为何比链表快mdmd