一亩三分地论坛

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

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

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

  [复制链接] |试试Instant~ |关注本帖
gougou9901 发表于 2014-7-20 15:55:11 | 显示全部楼层 |阅读模式

[其他]Berkeley CS 61B Data Structures(in Java) #1 - 2014-06-18@Berkeley

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

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

x
作业入口:  http://www.cs.berkeley.edu/~jrs/61b/hw/hw6/
作业用到了hashTable以及hashCode()。
最后的test code有一部分是要自己写的,反正就是算出自己hashTable的collisions总数,把它和good hashCode() 和 compFunction()下的collisions总数相比较。
这些方法其实G&T那本书里都写了,沿用一下就OK了~
我的输出中[][][][][][]....这一系列小方框代表了hashTable中的一个个bucket,方框中的数字就是bucket中所包含的entry数目。
输出见图:
hw6.png





评分

1

查看全部评分

Chris1993 发表于 2016-4-19 17:28:28 | 显示全部楼层
做了一下午才做完。。各种出错,对hashtable的理解不够到位,一开始构建hashtable想了不少时间
Screen Shot 2016-04-19 at 5.25.53 PM.png

评分

1

查看全部评分

回复 支持 0 反对 1

使用道具 举报

lyc1994 发表于 2015-7-26 10:24:25 | 显示全部楼层
HW6总结:
1. 本次作业主要的点是写hashcode函数和compression function函数。
2.hashcode与compression function函数的好坏主要由keys能否在buckets里面实现随机分布决定,因此,实际得到的collision数量越接近使用概率论计算得到的expected number,说明hashcode与compression function越好。而不是collision的数量越少越好。
3.通过最后的结果,发现compression function:h(i) = |i| mod N,h(i) = ((ai + b) mod p) mod N)其实效果差不多,得到的结果都比较接近expected number。


Homework6.JPG
回复 支持 1 反对 0

使用道具 举报

imposiwind 发表于 2014-11-22 12:52:30 | 显示全部楼层
这个题目要思考的其实挺多的,
第一是 bucket 的数目 N 怎么取?  
第二是 Board 的 hashCode() 函数怎么写? Java的int是怎么截取的?
第三是分配 bucket 的 compression 函数怎么写?

我的结果,应该还有改进的空间,有机会再看看。

n=100

n=100

n=200

n=200

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

俘虏你的心 发表于 2016-1-6 11:34:55 | 显示全部楼层
写了好久终于写出来了!
贡献一下测试HashTableChained的代码吧。
  1. System.out.println("=====================size, isEmpty=========================");
  2.         System.out.println("table's size is: " + table.size());
  3.         System.out.println("table is Empty: " + table.isEmpty());
  4.        
  5.         System.out.println("=====================insert================================");
  6.         table.insert("1", "The first one");
  7.         table.insert("2", "The second one");
  8.         table.insert("3", "The third one");
  9.         table.insert("what", "nani?");
  10.         table.insert("the","Eh-heng");
  11.         table.insert("hell!","impolite");
  12.         System.out.println("table's size is: " + table.size());
  13.         System.out.println("table is Empty: " + table.isEmpty());
  14.         try{
  15.                 String [] output = table.String();
  16.                 for(String s : output){
  17.                         if(s != null)        System.out.println(s);
  18.                 }
  19.         }
  20.         catch(InvalidNodeException ine){
  21.                 System.err.println(ine);
  22.         }
  23.        
  24.         System.out.println("====================find, remove===========================");
  25.         Entry e1 = table.find("6");
  26.         if(e1 != null)
  27.                 System.out.println("The item found is: [ " + e1.toString() + " ]");
  28.         else
  29.                 System.out.println("The is no such item in the table to be found.");
  30.        
  31.         Entry e2 = table.remove("hell!");
  32.         if(e2 != null)
  33.                 System.out.println("The item deleted is: [ " + e2.toString() + " ]");
  34.         else
  35.                 System.out.println("The is no such item in the table to be deleted.");
  36.        
  37.         try{
  38.                 String [] output = table.String();
  39.                 for(String s : output){
  40.                         if(s != null)        System.out.println(s);
  41.                 }
  42.         }
  43.         catch(InvalidNodeException ine){
  44.                 System.err.println(ine);
  45.         }
  46.        
  47.         System.out.println("=====================makeEmpty=============================");
  48.         table.makeEmpty();
  49.         try{
  50.                 String [] output = table.String();
  51.                 for(String s : output){
  52.                         if(s != null)        System.out.println(s);
  53.                 }
  54.         }
  55.         catch(InvalidNodeException ine){
  56.                 System.err.println(ine);
  57.         }
  58.         */
复制代码
QQ截图20160105213054.jpg
QQ截图20160105213108.jpg

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

candy_shmily 发表于 2015-11-26 08:49:29 | 显示全部楼层
用了两种compression function 图1为hashcode % N 图2为((a * hashcode + b) % p) % N 其中p为maxPrime(10000*N) 随便设的= = 然而感觉并没有优化多少 大概是simpleboard的hashcode写得太渣。。。 然而已经吭哧吭哧了= =
有木有大神分享一下自己的hashcode
61bhw6.png
61bhw6.mad.png

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

enirinth 发表于 2015-6-1 23:36:53 | 显示全部楼层
我来个暴力的,直接输出hash表的结构,bucket和对应的list,以及每个entry对应的key和value值。。。
111.png 222.png


太大的话图不好截,所以发的图是n=50的;n=100和n=150的只截结果好了:


333.png 444.png



小结:
1. 给定的load factor是个区间(0.5-1),所以找出来的质数有可能不止一个,我取得是质数数组的中位数(想让load factor接近0.75这样比较好);可能楼上诸君比较多的找的是最小的一个满足要求的质数,所以我的bucket比较多一些,collision也要小一点。

2.(A*hashCode+B)%p%N
以下先把N计作n, 方便大小写统一
i.为什么要n要是素数:因为被除和p如果有公约数c,则该公约数c也是余数r的约数,即r必须是c的倍数;这就限制了余数r的distribution  (m =Cn+r;  c|m, c|Cn, => c|r);
ii.为什么要用线性结构m=Cn+r; => Am+B = ACn +(Ar+B); 0<= r <n => (Am+B)%n = (Ar+B)%n;   Ar+b 在(B,Ar+B)这个长度为Ar的区间里,用它去%n会得到平均间隔为A的distribution,相当于把原来在(0,r)里   面%n的distribution稀释了A倍。咋看之下,稀释的好处当然就是减少collision的概率了。
iii.为什么要先%p再%n:  然而,上一步并没有什么卵用;因为Ar和r形成了对r而言的一一线性映射,比如原来长度为r的区间里可能的取值为(0,1,2),长度为3;假设A=2,B=0, 那么映射到长度为3*2的区间里就是(0,2,4);给的空间大了,但是间隔也相应变大了,1,3,5这些值没有可能取到!所以collision的概率一毛一样。那么只要破坏这种线性映射就好了,取mod明显是非线性的,而mod一个质数的理由见i;
iv.为什么需要p>>N: 因为mod p 就会映射到(0,p),第二步mod n要从(0,p)映射到(0,n), 如果这两个区间大小差不多的话,就没有第二步的必要了,直接认为p就是n就可以了。
我还在找严谨的数学推导为什么collision概率会减小;暂时先这么理解了。



补充内容 (2015-6-12 16:12):
关于为什么要P>>N, 又想到一点理由, 因为要一直resize hash table, 通常就是double, 所以N必须比P小很多

评分

2

查看全部评分

回复 支持 1 反对 0

使用道具 举报

imposiwind 发表于 2014-11-21 22:40:02 | 显示全部楼层
chaosyi 发表于 2014-11-8 11:39
这次作业我有一点始终没想明白,如果要表达3*3......*3,一共3^64个不同的格点图,可是32位int只能拥有2^32 ...

int 将超出的高位数截掉了
回复 支持 1 反对 0

使用道具 举报

小A要当码农 发表于 2015-7-20 12:43:16 | 显示全部楼层
本帖最后由 小A要当码农 于 2015-7-20 12:47 编辑


实在不太理解readme上面的推荐hashcode方法,自己想了个hashcode法,
感觉不应该太纠结于hashcode()的具体形式,因为我觉得默认的形式也不错。
不知道想法对不对,anyway,结果如图。
屏幕快照 2015-07-20 12.39.42.png
屏幕快照 2015-07-20 12.40.15.png
回复 支持 1 反对 0

使用道具 举报

complete_46 发表于 2014-9-2 14:48:06 | 显示全部楼层
交作业,图片能看到吗?
Untitled.jpg

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

逃亡~ 发表于 2014-9-26 12:54:11 | 显示全部楼层
homework 6 终于写完了,这次赶脚比前几次简单
1.png 2.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

chaosyi 发表于 2014-11-8 11:39:22 | 显示全部楼层
这次作业我有一点始终没想明白,如果要表达3*3......*3,一共3^64个不同的格点图,可是32位int只能拥有2^32个不同的数。不管再怎么优秀的计算方法,也不可能用少量的数,表达数量比他还要多的图啊?
回复 支持 反对

使用道具 举报

831128 发表于 2014-11-14 05:25:44 | 显示全部楼层
交作业,拿学分
QQ截图20141113132427.png
QQ截图20141113132505.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

18258170717 发表于 2014-11-29 16:40:20 | 显示全部楼层
有点没搞明白的是Be careful not to use floating-point numbers for this purpose, because they round off the least significant digits, which is the opposite of what you want. 我们不都是直接用int吗,自己会直接舍去高位,怎么会跑出来floating-point numbers呢,如果要用floating-point numbers应该怎么用,为什么我们是要舍去高位而不是舍去低位呢,有点没明白。
PS: 是不是说64个格子中,第一个0/1/2 * 3^63 占了绝大部分的hashcode,说明第一个数字(或者是前面32个数字)对整体的影响比后32个大,因此,高位的那些数字如果被保留(用floating-point numbers的方法)即使很少几个得到的hashcode也会是一样的,而低位的(在64个value中靠后的)被保留的话(int截取低32位)即使很多个加起来也很难超过int的范围,这样collide的概率将会减少。
各位大神我可能表达的不太清楚,不知道这样理解对不对。
回复 支持 反对

使用道具 举报

jzc007 发表于 2014-12-6 17:03:21 | 显示全部楼层
本帖最后由 jzc007 于 2014-12-6 17:05 编辑

搞了好久,为什么ls说很简单!
分别测了100,200。求学分…
test100.png
test200.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

bruce2045 发表于 2014-12-29 05:14:20 | 显示全部楼层
终于做完了,一开始一直没想到新建一个List,把它作为每个bucket(ListNode)的item,然后再把Entry插入到这个List里,窝真是太笨了! TAT
100.png
200.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

lycandy 发表于 2014-12-29 17:28:55 | 显示全部楼层
本帖最后由 lycandy 于 2014-12-30 03:21 编辑

交作业啦~~~
Screen Shot 2014-12-29 at 1.26.33 AM.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

sicilianee 发表于 2015-1-12 16:47:19 | 显示全部楼层
回复 支持 反对

使用道具 举报

zj45499 发表于 2015-1-12 20:04:13 | 显示全部楼层
发现hashCode实现的好的话multiply-add-and-divide和直接求余方法差别不大...

Screen Shot 2015-01-12 at 8.01.53 PM.jpg


评分

1

查看全部评分

回复 支持 反对

使用道具 举报

urekuk 发表于 2015-1-16 16:27:05 | 显示全部楼层
回复 支持 反对

使用道具 举报

xlwx 发表于 2015-4-3 06:07:35 | 显示全部楼层
选择 good hashcode 很重要
捕获.PNG
捕获2.PNG

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 02:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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