数据结构查找算法时间复杂度

Question

若要保证查找某序列中大部分值的时间复杂度均为O(1) ，则采用什么数据结构存放该序列最合适，为什么？

Answer 1

采用哈希表进行储存，这个查找大部分情况下就是o（1），哈希表构造上占用空间比较大，但是查找是非常快的，是典型的空间换取时间的做法，其他的基于比较的算法，最快的时间复杂度也只能达到o（log n），像快速排序，堆排序等等。