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

交作业 挣学分～

1. /Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/bin/java "-javaagent:/Applications/IntelliJ IDEA CE.app/Contents/lib/idea_rt.jar=60548:/Applications/IntelliJ IDEA CE.app/Contents/bin" -Dfile.encoding=UTF-8 -classpath /Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/charsets.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/deploy.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/cldrdata.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/dnsns.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/jaccess.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/jfxrt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/localedata.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/nashorn.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/sunec.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/sunjce_provider.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/sunpkcs11.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/ext/zipfs.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/javaws.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/jce.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/jfr.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/jfxswt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/jsse.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/management-agent.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/plugin.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/resources.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/jre/lib/rt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/ant-javafx.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/dt.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/javafx-mx.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/jconsole.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/packager.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/sa-jdi.jar:/Library/Java/JavaVirtualMachines/jdk1.8.0_161.jdk/Contents/Home/lib/tools.jar:/Users/Lim/@inbox/cs61b14/hw/hw6/out/production/hw6 Homework6Test 200
   
2. [0] [3] [4] [2] [2] [0] [1] [0] [0] [1]
   
3. [1] [0] [0] [0] [2] [0] [0] [1] [1] [0]
   
4. [3] [1] [1] [0] [1] [1] [2] [0] [2] [2]
   
5. [2] [1] [2] [1] [1] [1] [2] [0] [2] [0]
   
6. [0] [0] [0] [1] [1] [3] [2] [2] [2] [2]
   
7. [0] [2] [1] [0] [1] [1] [0] [1] [2] [1]
   
8. [2] [0] [1] [0] [1] [2] [3] [3] [2] [0]
   
9. [1] [0] [0] [0] [1] [1] [1] [0] [1] [3]
   
10. [1] [0] [1] [0] [0] [0] [1] [1] [0] [1]
    
11. [2] [2] [2] [1] [1] [0] [1] [1] [0] [1]
    
12. [0] [0] [1] [0] [2] [0] [0] [0] [0] [2]
    
13. [0] [0] [1] [0] [2] [1] [1] [1] [3] [4]
    
14. [0] [4] [1] [2] [3] [0] [1] [2] [1] [1]
    
15. [1] [1] [0] [1] [1] [0] [0] [1] [1] [0]
    
16. [0] [1] [0] [0] [1] [0] [0] [0] [1] [1]
    
17. [0] [3] [0] [1] [3] [1] [0] [1] [0] [0]
    
18. [1] [3] [1] [1] [3] [0] [2] [1] [1] [0]
    
19. [0] [0] [2] [1] [1] [1] [0] [1] [0] [2]
    
20. [2] [0] [1] [2] [0] [1] [0] [0] [1] [3]
    
21. [0] [0] [0] [2] [0] [1] [4] [1] [1] [0]
    
22. [1] [1] [1] [0] [0] [0] [0] [0] [0] [0]
    
23. [2]
    
24. 
    
25. the number of boards = 200
    
26. the number of buckets = 211
    
27. actual number of collision = 72
    
28. expected number of collision = 70.59251923749707
    
29. 
    
30. Process finished with exit code 0

复制代码

(1) Math.pow() 返回值是double哇
(2) 理论概率是概率论的问题，还蛮有趣的

hashtable打卡。
这次作业还挺简单的，要是按readme的提示做的话。
不过要自己设计hashcode应该就难了

继续打卡

the number of boards is 100 the number of buckets is 151
the expected collisions is 26.69769293278702
showing the table now
[0] [1] [0] [0] [1] [1] [2] [0] [2] [0] [2]
[1] [2] [1] [0] [0] [0] [1] [1] [1] [0]
[0] [0] [5] [0] [1] [1] [0] [0] [0] [0]
[1] [2] [1] [1] [0] [0] [0] [1] [0] [1]
[0] [0] [0] [0] [1] [1] [0] [0] [1] [0]
[2] [0] [0] [0] [0] [1] [0] [1] [4] [0]
[0] [0] [0] [0] [0] [0] [0] [3] [1] [0]
[0] [0] [1] [0] [1] [2] [1] [1] [0] [0]
[1] [2] [0] [1] [1] [1] [0] [1] [1] [0]
[3] [1] [0] [1] [0] [0] [0] [1] [1] [0]
[2] [1] [0] [1] [0] [3] [0] [1] [1] [0]
[2] [0] [0] [0] [0] [0] [0] [0] [0] [2]
[0] [2] [1] [1] [0] [0] [3] [2] [2] [0]
[0] [0] [1] [1] [0] [1] [0] [0] [0] [2]
[0] [0] [1] [0] [2] [0] [0] [2] [0] [0]
the collisions in the table is32


不知道为什么有些时候论坛上传不了图片。这是我运行的结果。
     关于compressFuntion我感觉将bucket的数量设为质数就完全可以了，没必要再%p%bucketnum。
另外由于我hashcode函数的返回值本身很大，而且是对int的最大范围

2147483647取的模。所以我在进行（An+B）%p%bucketnum的时候遇到了数据溢出的问题。hashcode在乘以一个常数a后溢出导致变为了负数。虽然是很简单的问题但是做的时候真Tm是找了半天也不知道为什么会出现负数。

      我感觉老师所说的CompressFunction的算法是针对hashcode（）函数不够离散的情况加以修正的，可以将hashcode的间距放大A倍。就拿这次作业来说，我的hashcode函数本身的值是3的64次方%2147483647，就完全没有必要进行这样的操作，只需要将bucketnum设为质数避免公因数的产生就行了。

按题目要求，要保证load factor在0.5和1之间，
我是n =  sizeEstimate * 2， 然后找小于等于n的最大的prime。

这样就保证了load factor 永远在0.5和1之间。
感觉一定有更好的方法。

交作业～～这次作业 重在理解hash的过程～～ 自己实际需要书写的代码量不多～～前面大家总结的都很棒！给了很多启发1. 对于数组来说 没有initialize 是不能直接用index的...
buckets[i]=new DList(); 以后才能对buckets[i]进行进一步操作
2. compression function 和hashcode()...彷佛在嘲笑我的数学水平...学啥最后都是学数学...
希望下个月之前能把公开课看完～～

有几个地方卡了很久，但是难度不高：
1. 由于先刷题了解到了hashmap，讲hashtable的时候听的不是很认真，实际上它们有很大的不同
2. 在这个叫table的ADT中，它的组成是由N个buckets组成，N是用户自己定的，真正的输入是n，n在这里的测试代码中是numBoards，也就是输入的board的数量
3. 开始写compressFunction把h(i) = ((ai + b) mod p) mod N 这个公式直接用了进去，不知道ab设定什么就乱设了，后来结果不对一直存放在一个list里估计就有问题，改成了绝对值就好了
4. hashcode实际上可以用视频中% 16908799的那个公式 也比较简单，但是它就是个black art 自己搞肯定不行
5. 测试代码其实不难写，但是找了半天想用下大家的发现没有，自力更生了
加油~

我一直不太明白readme.pdf中的a tutorial on collision probability 中：
So when you have i keys in the table and
insert key i + 1, the probability that the new key does NOT collide with any
old key is (1 - 1/N)^i.
里面的1/N不应该是随着key的数量增加？应该是(1-1/N)*(1-2/N)*(1-3/N)...*(1-i/N)吗？