一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 598|回复: 13
收起左侧

[算法题] 如果hashcode不是O(1),那么hashmap能保证O(1)look up吗?

[复制链接] |试试Instant~ |关注本帖
allen6432 发表于 2015-8-15 03:13:58 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
最近在准备goolge面试复习hashmap时候发现有一个东西没想明白。
如果hashmap中hashfuntion比较好的话,那么get(key)一般是O(1);
但是问题是如果hashfunction不是O(1)怎么办?
比如,java 中string.hashcode()=s[0]31^n-1+s[1]*31^n-2+.......+s[n-1]; 这是O(N)
有点想不通,求好心人解答


victor2100 发表于 2015-8-15 14:15:27 | 显示全部楼层
回复 支持 1 反对 0

使用道具 举报

stellari 发表于 2015-8-15 13:52:10 | 显示全部楼层
georgmaster 发表于 2015-8-15 05:24
如果考虑这么仔细的话,不如更进一步.
c*x ^ y 相当于做了n次乘法
那么计算总共乘了(1+n)*n/2

如果每一项的x和y都不同的话,确实如此。但是hashCode()的计算公式中每一项的底都是31,而指数则是按照0, 1, 2, ..., n-1这样逐次递增。所以,只需要线性次计算就能够将这n项的值全部算出。复杂度依然是O(n),不需要使用O(n^2)的naive方法。

面试时如果被要求分析复杂度的话,我认为有必要将这点指出。因为这在字符串较长时会引起一定的性能差别,不能简单忽略。
回复 支持 1 反对 0

使用道具 举报

 楼主| allen6432 发表于 2015-8-15 03:22:25 | 显示全部楼层

哦。 感谢!!!
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-8-15 04:16:55 | 显示全部楼层

楼主你明白咋回事了吗?如果字符串的长度就是n的话怎么办呢?
回复 支持 反对

使用道具 举报

 楼主| allen6432 发表于 2015-8-15 04:27:04 | 显示全部楼层
水逼一枚 发表于 2015-8-15 04:16
楼主你明白咋回事了吗?如果字符串的长度就是n的话怎么办呢?

如果我没理解错的话,我们一般所说hashmap.get(key)是考虑与hashmap里面有多少pair(key,value)相关。这就是N.但是算hashcode(key)的复杂度是与字符长度有关的n. 所以楼上解释是此n非彼N.
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-8-15 04:47:12 | 显示全部楼层
allen6432 发表于 2015-8-15 04:27
如果我没理解错的话,我们一般所说hashmap.get(key)是考虑与hashmap里面有多少pair(key,value)相关。这就 ...

好的明白了,之前还真没注意到这一点。赞一个仔细。另外HashMap我们常说O(1)的查找这个也是平均时间复杂度没错吧,最坏的情况下还是有可能O(n)的没错吧,只是我们一般就用平均再说。
回复 支持 反对

使用道具 举报

 楼主| allen6432 发表于 2015-8-15 05:01:23 | 显示全部楼层
水逼一枚 发表于 2015-8-15 04:47
好的明白了,之前还真没注意到这一点。赞一个仔细。另外HashMap我们常说O(1)的查找这个也是平均时间复杂 ...

是的,没错
回复 支持 反对

使用道具 举报

readman 发表于 2015-8-15 05:03:25 | 显示全部楼层
这个就是为什么prime in p 不是消除法一个道理.
回复 支持 反对

使用道具 举报

 楼主| allen6432 发表于 2015-8-15 05:15:39 | 显示全部楼层
readman 发表于 2015-8-15 05:03
这个就是为什么prime in p 不是消除法一个道理.

这个问题具体是?
回复 支持 反对

使用道具 举报

georgmaster 发表于 2015-8-15 05:24:50 | 显示全部楼层
本帖最后由 georgmaster 于 2015-8-15 05:32 编辑

如果考虑这么仔细的话,不如更进一步.
c*x ^ y 相当于做了n次乘法
那么计算总共乘了(1+n)*n/2

你看现在不是O(n)了,是O(n^2)

两个两位数相乘相当于两次一位数乘以两位数和一次两位数加三位数
一位数乘以两位数是两次一位数乘以一位数和两次加法,就是四次操作
两位数加三位数就是四次加法,就是四次操作
那么总共就是12次操作
那么就变成了O(12n^2)


那我们再把对内存的操作考虑进来
好吧我编不下去了


回复 支持 反对

使用道具 举报

 楼主| allen6432 发表于 2015-8-15 06:10:41 | 显示全部楼层
georgmaster 发表于 2015-8-15 05:24
如果考虑这么仔细的话,不如更进一步.
c*x ^ y 相当于做了n次乘法
那么计算总共乘了(1+n)*n/2

非常对。感觉自己蠢哭了
回复 支持 反对

使用道具 举报

stellari 发表于 2015-8-15 13:58:05 | 显示全部楼层
你可以理解为O(1) look up是仅适用于“长度为常数”的数据类型的。对于值可能会很长的数据,比如字符串,这一说法不再适用。这种情况下,查询的平均复杂度应是O(L),其中L为字符串的平均长度。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 18:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表