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

这次的作业怎么这么恶心，感觉一次比一次难了。。。做得我要吐血了。。。

这是啥？只觉得不闭合。。。

18258170717 发表于 2014-11-29 16:40
有点没搞明白的是Be careful not to use floating-point numbers for this purpose, because they round of ...

算3^n 的时候如果用java自带的函数返回的是double.

这个作业真是做的如痴如醉！   求加学分~~~part2的
hashcode（）部分也是醉了
另外在HashTableChained中我加了很多Test code 用来测试part1中的方法，输出结果如图三

又看了下，看来 collision预测的还很准：）

新技能hash table GET!

谢谢严谨负责的版主大人     补上case2

小问题卡住了很久，感谢楼上一位好心同学的指点。

我来个暴力的，直接输出hash表的结构，bucket和对应的list，以及每个entry对应的key和value值。。。

太大的话图不好截，所以发的图是n＝50的；n＝100和n＝150的只截结果好了：

小结：
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小很多

终于做完了，，，多谢同学的帮助啊，，，惭愧，希望追赶大牛们的步伐

交作业了，求加分