Hash索引为什么时间复杂度是O(1)?存在的意义是什么？
正在学索引。据我所知，Hash索引就是把索引字段的Hash值作为Hash表的key，对应的数据作为value。那问题来了，查询时，计算完关键字的Hash值后，不也要再Hash表里面找吗？如果数据很多，比如100w笔数据，平均也要和key对比50w次吧。这样的话时间复杂度怎么会是O(1)呢？而且按照这个逻辑，因为Hash值是无序的，所以索引的效率应该比B树差很多吧。既然如此，Hash索引存在的意义是什么？以上，我不是很明白，望指教。
回答：
hash 一般直接被当作（或者简单映射到）一个偏移，不需要与每一个 key 比较。
这个偏移上存的是一个桶，里面只有有限个元素。hash 建立的时候会保证桶里元素不会太多，多了通常会 rehash （重建更多的桶），保证桶里的元素个数可控。
这样，hash 到偏移跟再桶里查找大概都是 O(1) 时间，总的时间也是 O(1) 。
回答：
把哈希的值当成数组下标理解就好了. 如果有多个哈希值相同, 在相同的下标处会使用一个更高维的数组或者是链表保存数据.
用数组下标访问, 可不就是O(1)么.
以上是 Hash索引为什么时间复杂度是O(1)?存在的意义是什么？ 的全部内容， 来源链接： utcz.com/p/944665.html
