一亩三分地论坛

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

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

[算法题] 一道面经题目,不懂出题点

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

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

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

x
经典的2sum。。follow up问如果是浮点数,hash的时候会有什么问题.问怎么hash浮点数。  我实在没看懂这个出题点是啥?难道hash float number 不同??
jiebour 发表于 2015-10-2 04:46:42 | 显示全部楼层
哪家公司的?
回复 支持 反对

使用道具 举报

peach=。= 发表于 2015-10-2 04:50:44 | 显示全部楼层
我查了下,hash一个double的时候,会把double转换成long bits,再用这个long bits去算hash code
会不会是因为当double后面的小数位特别长时,返回的hashcode就会是一样的,所以才有这个follow up?
我试了一下,比如42.500000000000001 和 42.500000000000002的hashcode是一样的
><有木有路过的大神来解答一下!
回复 支持 反对

使用道具 举报

stellari 发表于 2015-10-2 10:44:33 | 显示全部楼层
因为HashTable的下标是个整数,所以我们最后要实现的其实是把key的类型映射到一个整型数上去。如果key的类型也是整型,这个映射就比较简单,比如最简单的实现可以用key % (a prime number)。但是浮点数的话就不能用这种方法了。所以才问你有没有比较通用的方法,能扩展到浮点数上。
回复 支持 反对

使用道具 举报

stellari 发表于 2015-10-2 10:53:13 | 显示全部楼层
peach=。= 发表于 2015-10-2 04:50
我查了下,hash一个double的时候,会把double转换成long bits,再用这个long bits去算hash code
会不会是 ...

double型最多表示16位10进制有效数字,你给的42.500000000000001和42.5...02恰好超出了double型能表示的范围,所以这两个数在计算机中都是用42.5来表示的。对两个同样的42.5做hash当然会得出相同的hashCode。这个问题如果不增加double型的位数的话,是不可能得到解决的,所以这应该不是出题点。面试官想问的估计就是你知不知道double转raw bits这个思路。
回复 支持 反对

使用道具 举报

peach=。= 发表于 2015-10-2 15:32:51 | 显示全部楼层
stellari 发表于 2015-10-2 10:53
double型最多表示16位10进制有效数字,你给的42.500000000000001和42.5...02恰好超出了double型能表示的 ...

原来如此,谢谢大神解答!
还有两个疑问,
1. 整型数映射成hashcode,我看到有些解释的是说 int 就直接用int值本身,long的话就用 (int) num^(num>>>32),不知道和你说的key % (a prime number)是什么区别?为何要% prime number?
2. 你猜测的面试官想问知不知道double 转raw bits这个思路是不是java 算double的hashcode时候用的Double.doubleToLongBits()这个方法?
><希望大神能再解答一下!
回复 支持 反对

使用道具 举报

stellari 发表于 2015-10-2 20:31:14 | 显示全部楼层
peach=。= 发表于 2015-10-2 15:32
原来如此,谢谢大神解答!
还有两个疑问,
1. 整型数映射成hashcode,我看到有些解释的是说 int 就直接 ...

1. 取模是为了把一个范围非常大的数字[INT_MIN, INT_MAX]均匀地映射到一个比较小的范围内(即hashtable数组的长度)。你看到的那些解释是意思是说“我们在取模这一步之前应该做什么”。最后一步的取模操作他们都默认大家知道,所以略去不说了。
2. 是的。当然你也未必一定要用这个方法,自己提出一个方案也可以。只要你能证明这个方案能够均匀地把double映射到hash数组中就可以。
回复 支持 反对

使用道具 举报

peach=。= 发表于 2015-10-3 01:29:42 | 显示全部楼层
stellari 发表于 2015-10-2 20:31
1. 取模是为了把一个范围非常大的数字均匀地映射到一个比较小的范围内(即hashtable数组的长度)。你看到 ...

谢谢耐心解答!
第二点明白了,第一点还有一个疑问:
如果要映射到hashtable数组的长度内,为什么不是模上这个长度,而是一个prime number呢? (T^T默认大家都知道…我一直以为模的是array size啊!不是吗?没有这种做法吗?
回复 支持 反对

使用道具 举报

plich 发表于 2015-10-3 06:38:43 | 显示全部楼层
路过问一下,我如果直接使用c++里面的unordered_map<double, int>的话,是会解决这个问题还是带来同样/更多的隐患呢?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-10-3 09:44:13 | 显示全部楼层
peach=。= 发表于 2015-10-3 01:29
谢谢耐心解答!
第二点明白了,第一点还有一个疑问:
如果要映射到hashtable数组的长度内,为什么不是 ...

是数组长度,但是数组长度一般都是一个质数。抱歉这点我忘说了。
回复 支持 反对

使用道具 举报

peach=。= 发表于 2015-10-3 11:11:17 | 显示全部楼层
stellari 发表于 2015-10-3 09:44
是数组长度,但是数组长度一般都是一个质数。抱歉这点我忘说了。

soga!懂了!谢谢解答!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 04:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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