📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2120| 回复: 11
跳转到指定楼层
上一主题 下一主题
收起左侧

一道面经题目,不懂出题点

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
经典的2sum。。follow up问如果是浮点数,hash的时候会有什么问题.问怎么hash浮点数。  我实在没看懂这个出题点是啥?难道hash float number 不同??

上一篇:求教啊刚刚收到BAIDU AIlab的technical 电面,求题目啊
下一篇:Career ride里的一个OS的题目,关于deadlock的
推荐
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数组中就可以。
回复

使用道具 举报

推荐
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这个思路。
回复

使用道具 举报

🔗
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)。但是浮点数的话就不能用这种方法了。所以才问你有没有比较通用的方法,能扩展到浮点数上。
回复

使用道具 举报

🔗
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数组的长度内,为什么不是 ...

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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