hashmap的时间复杂度问题

Pack 发布于 2019-12-25 15:36

阅读 756

答案 1

分类：Java开发

hashMap.containsKey(value) 的时间复杂度是多少？

今天跟朋友关于这个时间复杂度问题，吵起来了，我说hashMap.containsKey(value)的时间复杂度只有在最好的情况下才是O(1)，他非得说map里面的所有操作时间复杂度都是O(1)，在碰到hash碰撞的时候时间复杂度为O(n),由于才疏学浅，没办法说服对方，
哪位大神，帮我解释一下，
hashMap.containsKey(value)的时间复杂度到底是多少

Pack 2019-12-25 15:36

hashmap在最坏的情况下实际上是一个红黑树，时间复杂度是logn,但是我们说的时间复杂度一般不是指最好的，也不是指最差的，一般是指平均的，即大多数情况下的情况，hashmap时间上最耗时的操作是在计算hash值（这是在有限的时间内一定能算出来的，时间复杂度为1），然后通过数组下标取值，一般情况下，在hash冲突比较多的时候会扩容来降低hash冲突，这个扩容操作时间复杂度是很高的，但是这个时间均摊到每一次操作，又可以忽略了，总的还说hashmao的时间复杂度为1

hashmap的时间复杂度问题

hashMap.containsKey(value) 的时间复杂度是多少？

Pack 的其他提问

类似问题