一亩三分地

 找回密码 注册账号

扫描二维码登录本站

最近看过此主题的会员


码农求职神器Triplebyte
不用海投
内推多家公司面试

Total Comp Calculator
输入offer信息
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250

深入浅出AB Test
从入门到精通
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
楼主: gougou9901
收起左侧

Berkeley CS 61B Data Structures(in Java) Homework6 加分+讨论帖

  [复制链接] |试试Instant~
我的人缘0
renyi 发表于 2018-8-8 22:17:42 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   97% (37)
 
 
2% (1)    👎
交作业,本来觉得不是很难,但是在一个小问题上卡了一晚上TAT。。。当定义一个list类型的数组的时候,数组里存放的并不是list,而是指向list的指针!要对数组里的元素赋过值,即新建list并使数组元素指向该list以后才能通过数组下标找到list,否则就会出现nullpointerexception
更多图片 小图 大图
组图打开中,请稍候......
回复 微信

使用道具 举报

我的人缘0
copyrightly 发表于 2018-8-14 16:05:11 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
SaltSprayAir 发表于 2017-6-23 18:44
还算简单,list中把之前作业里的nth用在了HW5的list包了,就很方便。SimpleBoard的hashcode直接sum = sum*2 ...

是不是应该是sum*3 ?
回复

使用道具 举报

我的人缘0
copyrightly 发表于 2018-8-14 16:16:00 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
a9x26j8i 发表于 2018-6-22 03:18
我一直不太明白readme.pdf中的a tutorial on collision probability 中:
So when you have i keys in the ...

那你是假定了前面i个item的分布情况,实际上它们的分布情况不知道,可能在一个bucket里,也可能不在。因为新加入的item与任何一个已有的item 不重叠的概率都是 1 - 1/N,那么与前i个都不重叠的概率就是它的i次方。
回复

使用道具 举报

我的人缘0
copyrightly 发表于 2018-8-14 16:20:08 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
问一个问题,remove 的时候如果有相同的key随机删除一个是怎么做到的?
回复

使用道具 举报

我的人缘0
shendezhuti 发表于 2019-5-18 11:30:32 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (29)
 
 
3% (1)    👎
WX20190518-112214@2x.png WX20190518-112153@2x.png
本次作业是关于hash table,总体来说难度不是很大,但是自己实现的时候还是磕磕绊绊的,参考了别人的代码。
1.对于N的选取,我是用了sieve of eratosthenes找素数的方法,然后检查 sizeEsitimate~2*sizeEsitimate中,取一个素数p,使得 sizeEsitimate/p的值最接近0.75
2.写SimpleBoard类中的hashcode()我们可以将每个格子对应的(i,j)对应不同的幂(从0~63),但是我不理解的是为什么要舍掉高位?虽然我理解舍掉高位之后会造成冲突..
3.本次好多测试代码都要自己写,一脸懵逼,最后的Homework6Test中的 histograph输出方法还是从别人那找来的...心累
回复

使用道具 举报

我的人缘0
satiji 发表于 2019-6-16 02:38:37 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (75)
 
 
5% (4)    👎
打卡hw6,感觉难度不是很大,遇到的唯一bug就是一开始总是提示insert函数数组索引越界,发现java自带的hashcode函数可能会求出负数,于是加上绝对值即可:Math.abs(((a*code+b)%p)%N),另外就是对于hashcode的原理还是不太了解,数论基础太差,,,,继续,,,,hw7走起!!!!!
hw6.png
回复

使用道具 举报

我的人缘0
lesliere 发表于 2019-6-19 00:45:00 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (12)
 
 
7% (1)    👎
1. 不知道为啥得到的bucket index有负数,有一个同学说"hashcode在乘以一个常数a后溢出导致变为了负数"。但依照lecture notes的意思,是因为hashcode本身很可能是负数(为啥会这样?),所以要用mod这个运算符,这样就会得到正数,可我好像是用不了这个运算符,不知道大家能不能。。。。总之我后来用的运算符是%并且对负值的index加了一个N2. buckets我考虑到loadfactor控制在0.5-1,我想接近0.5就用了小于2倍entry数的最小质数,但出来的结果有时候会比expected collisions少很多,但感觉大家发的图片都很接近expected,有点奇怪。。。。
3. 另外大家都在说的int截取问题一开始其实我都没想到(int截取低32位)4. 还有出错的地方是在算expected collisions的时候,要精确的话要把运算中的任一个cast成double或float(这个作业里就是double)
5. 并不太懂((a * hashcode + b) % p) % N,这里a,b,p的取值该怎么取,我都是挑的正质数

更多图片 小图 大图
组图打开中,请稍候......
回复

使用道具 举报

游客
请先登录
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地

GMT+8, 2019-7-19 22:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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