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

时隔许久继续复习数据结构！求加分！

第六次作业出炉

终于搞出来了
1.hashcode压缩后 我有几次就成了负的 然后数组下标就报错了  
2. 一开始不理解那个hashcode的方法  看了前面网友回答 知道了8x8的数组 从[0,0]到[7,7]一共64个数  正好只有0,1,2的数值 所以可以看成011221021021021....一共64个 一int就可能变成负的了 这得看compFunction（）了。。
3这次作业很好  发现还是做作业能巩固知识

实在不知道怎么测试得出前面的结果 复制了贴出测试 代码 可是有错 不会改 参考了 http://gaotx.com/cs61b/ 的代码 来测试了下 也是remove那个地方 报null的错 于是把它 ／／了
不过总的来说 思路是真懂了 也知道怎么实现 目的达到了 这些地方就先不纠结了 毕竟还要赶紧结束算法的学习 然后刷题   不过还是希望有大神能够指点一二 好像得到前面那些个模样的结果 可是。。。。。。 臣妾做不到啊

后人或者前人们  如果你们输出了前面那种的答案  又刚好看到此喽  可否私信你的代码供我个人学习一下？！  谢谢谢谢！！！！！

考完期末继续回来做这个作业。
几天不看就生疏了。打打游戏写写代码花了两天。。

Hw6做的还算顺利，光看lecture对hash table理解的还是有点模糊，边做作业边回过头再看lecture之后知识点确实巩固了很多，挺有意思的。

没有输出小方格，这次感觉参考了下github，可能自己一开始并没有特别理解如何使用linked list去实现hashtable和hashtable内的chained list。 后来看了下别人的慢慢懂了。

造福一下后来人。我的compFunction

1.   int compFunction(int code) {
   
2.     // Replace the following line with your solution.
   
3.     int a = 7;
   
4.     int b = 11;
   
5.     int p = 805306457;
   
6. 
   
7.     int hashCode = (a * code + b) % p;
   
8.     if(hashCode < 0) {hashCode += p;}
   
9.     hashCode = hashCode % bucketNum;
   
10. 
    
11.     return hashCode;
    
12.   }

复制代码

测试insert，find和remove的代码

1.     //Test hashTable methods
   
2.     table = new HashTableChained(numBoards);
   
3.     System.out.println("*************** size, isEmpty ***************");
   
4.     System.out.println("table's size is: " + table.size());
   
5.     System.out.println("table is Empty: " + table.isEmpty());
   
6.    
   
7.     System.out.println("*************** insert ***************");
   
8.     table.insert("1", "The first one");
   
9.     table.insert("2", "The second one");
   
10.     table.insert("3", "The third one");
    
11.     table.insert("4", "The fourth one");
    
12.     table.insert("5","The fifth one");
    
13.     System.out.println("table's size is: " + table.size());
    
14.     System.out.println("table is Empty: " + table.isEmpty());
    
15.     table.printBucketContent();
    
16.    
    
17.     System.out.println("*************** find, remove ***************");
    
18.     Entry e1 = table.find("1");
    
19.     if(e1 == null)
    
20.       System.err.println("find() has a problem.");
    
21.     else
    
22.       System.out.println("Found " + e1);
    
23. 
    
24.     Entry e2 = table.find("2");
    
25.     if(e2 == null)
    
26.       System.err.println("find() has a problem.");
    
27.     else
    
28.       System.out.println("Found " + e2);
    
29. 
    
30.     Entry e3 = table.find("10");
    
31.     if(e3 != null)
    
32.       System.err.println("find() has a problem.");
    
33.     else
    
34.       System.out.println("Cannot find 10");
    
35.    
    
36.     Entry e4 = table.remove("10");
    
37.     if(e4 != null)
    
38.       System.err.println("remove() has a problem.");
    
39.     else
    
40.       System.out.println("10 cannot be deleted.");
    
41. 
    
42.     Entry e5 = table.remove("4");
    
43.     if(e5 == null) {
    
44.       System.err.println("remove() has a problem");
    
45.     }
    
46.     else {
    
47.       System.out.println("Deleted is " + e5);
    
48.     }
    
49.     table.printBucketContent();
    
50.    
    
51.     System.out.println("*************** makeEmpty ***************");
    
52.     table.makeEmpty();
    
53.     table.printBucketNum();

复制代码

做的好艰难啊~！！！打卡坚持

写了一天，看了楼里的而一些提示总算是做出来了，不过还是有好几个地方不明白：
（1）hashdcode为啥h(i) = ((ai + b) mod p) mod N效果最好？前面某位大神的回答感觉很有道理。
（2）对board的处理，看成64位3进制数，然后用int去掉超过2^32以上的部分，不明白为什么可以直接让他自由溢出？？这样不是相当于砍掉了前面的很多位吗，也就是说不同的board如果前好多位都不同的话得到的hashcode还是相等的？
（3）为啥要用int截取，为啥readme里说不能用float型？看前面说会产生乘法溢出。。。不是很理解乘法为何会溢出？？？以及跟float有啥关系？