Hash索引为什么时间复杂度是O(1)?存在的意义是什么?

qing
  • 47
上海

正在学索引。据我所知,Hash索引就是把索引字段的Hash值作为Hash表的key,对应的数据作为value。那问题来了,查询时,计算完关键字的Hash值后,不也要再Hash表里面找吗?如果数据很多,比如100w笔数据,平均也要和key对比50w次吧。这样的话时间复杂度怎么会是O(1)呢?而且按照这个逻辑,因为Hash值是无序的,所以索引的效率应该比B树差很多吧。既然如此,Hash索引存在的意义是什么?以上,我不是很明白,望指教。

回复
阅读 753
2 个回答
✓ 已被采纳

hash 一般直接被当作(或者简单映射到)一个偏移,不需要与每一个 key 比较。

这个偏移上存的是一个桶,里面只有有限个元素。hash 建立的时候会保证桶里元素不会太多,多了通常会 rehash (重建更多的桶),保证桶里的元素个数可控。

这样,hash 到偏移跟再桶里查找大概都是 O(1) 时间,总的时间也是 O(1) 。

风兮清扬
  • 5.6k
北京

把哈希的值当成数组下标理解就好了. 如果有多个哈希值相同, 在相同的下标处会使用一个更高维的数组或者是链表保存数据.

用数组下标访问, 可不就是O(1)么.

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏