求解关于hashmap时间复杂度

才刚开始刷题 比较小白 求不喷＝ ＝
求解hashmap的操作的时间复杂度以及空间复杂度
先谢过啦~~~~~~~~~

Hashmap 是avg O(1), worst O(n) time 和O(n) space的. 每一次存或者取,通过计算一个hash function获得这个key的unique hash值, 这部分是O(1)的. 正常情况就只需要这么多,如果有collision的话,就是两个key 算出来的hash值是一样的,那就是linear 的complexity, 因为一个key里面有两个值, 所以worst的情况O(n), 然而这个几率非常小, 多次都collide的几率更小. space的话就是每多一个key-value pair,就要allocate一个space,所以是O(n).

花花你也要转程序媛了吗

zhahaoyu 发表于 2017-1-29 05:47
Hashmap 是avg O(1), worst O(n) time 和O(n) space的. 每一次存或者取,通过计算一个hash function获得这个 ...

谢谢 讲的很好！！

读写O(1)。
分为Open Hashing closed hashing.Open Hashing 就是如果存在重复值的话，就在重复的节点后面建立链表。
Closed Hashing 就是对那个储存数据的数组进行扩容。
hashing函数是 Key值 % array size。不少题中要求设计数据结构，用Hashmap HashSet非常好用。复杂度O(1)第一个就想到哈希表。
正好看到这里。