成语大全网 - 成语词典 - 哈希表查找的时间性能在什么情况下可以达到o1?

哈希表查找的时间性能在什么情况下可以达到o1?

哈希表查找的时间性能在没有哈希冲突的情况下可以达到o(1)。

也就是说复杂度是和哈希函数的M以及你要存的数据总数N有关的。

一般情况下N/M是一个常数,也就是说复杂度是O(1)。

但是如果M过小,N过大,就有可能出现复杂度比O(1)大的情况。

扩展资料:

step1 取数据元素的关键字key,计算其哈希函数值。若该地址对应的存储空间还没有被占用,则将该元素存入;否则执行step2解决冲突。

step2 根据选择的冲突处理方法,计算关键字

key的下一个存储地址。若下一个存储地址仍被占用,则继续执行step2,直到找到能用的存储地址为止。

百度百科-哈希查找