为什么说哈希表和跳表是高效的数据结构

问题描述

精选答案

优势： 从时间和空间的角度分析： 时间高效：利用哈希可使插入、查找、删除、修改、替换操作的时间复杂度达到O(1)，这是其他查找方式无法达到的（比如树形查找O(logn)、二分查找O(logn)、顺序查找O(n)等）。即使出现碰撞，整体理论值也可以接近O(1)。

空间可接受：哈希的比较合适的空间消耗以O(2n)最佳，对于其他同类算法（主要是树形查找方式），要分为两类。

第一种是以叶子存放有效值的树(如b+树、线段树)，其空间消耗可认为是O(4n)；

第二种是所有节点均存放有效值，空间消耗可认为O(n)。