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

越後面的homework越好玩了
上傳homework 6的執行結果

还是写了大半天..
对照教材上的思路，linked-list包引用的hw2的代码，挺多细节需要注意
比如import list后，还得把要创建的类(SListNode)的constructor声明为public才行
hashcod就用的lecture里的方法，效果似乎也挺好的
测试时增加了把每个board的经过compressed后的hashvalue显示了出来的部分，分别测试100和200的case。

用了两种compression function 图1为hashcode % N 图2为((a * hashcode + b) % p) % N 其中p为maxPrime(10000*N) 随便设的= = 然而感觉并没有优化多少 大概是simpleboard的hashcode写得太渣。。。 然而已经吭哧吭哧了= =
有木有大神分享一下自己的hashcode

最后测试代码部分感觉应该还要再加remove(), find()的测试，但是懒得写了……
hashCode()部分在readme中没有看懂啊，求大神解释

run:
[1][0][3][0][1][1][0][0][1][0][0][0][2][3][1][1][0][0][2][1][0][1][0][0][0][0][1][1][1][0][1][0][1][3][1][0][0][0][0][1][1][1][0][2][0][1][1][0][0][1][0][0][0][1][1][1][0][0][2][0][3][0][1][1][0][0][0][0][0][0][1][0][1][0][0][1][1][0][0][0][0][0][0][1][2][0][1][0][2][1][0][0][2][1][0][2][0][1][2][1][0][0][0][0][2][2][1][0][0][0][1][0][1][0][0][2][0][1][2][1][2][3][1][1][0][2][0][1][1][0][0][3][1][2][2][1][2]
Expected collisions: 36.60323412732292/100
Report collisions: 30/100
成功构建 (总时间: 0 秒)

run:
[2][1][1][0][2][3][1][0][1][0][2][0][0][0][0][1][1][1][1][0][1][1][3][1][2][2][1][0][1][1][1][1][1][1][0][0][1][1][0][0][1][1][2][1][1][0][2][0][0][1][0][1][1][0][1][2][0][0][0][0][1][0][2][0][0][1][0][0][0][1][2][0][1][2][1][0][1][2][0][1][0][1][2][1][0][1][1][0][0][0][0][2][0][0][1][2][1][0][0][0][2][0][1][0][2][0][0][0][0][2][2][0][0][1][0][1][0][2][0][0][1][1][1][2][0][0][0][0][0][1][0][2][0][0][0][0][0][2][2][2][0][0][0][1][0][1][1][1][1][0][0][0][2][0][1][0][1][1][0][0][1][3][1][1][1][0][1][1][1][0][1][0][0][2][0][1][0][2][0][0][0][1][0][1][0][1][0][0][0][1][2][0][0][1][2][1][1][1][0][3][0][1][0][0][1][4][0][0][0][2][1][2][0][1][1][1][0][0][1][0][1][1][0][4][1][0][1][1][1][0][0][1][4][0][0][0][0][0][0][0][0][2][1][0][0][2][1][0][1][0][1][0][1][0][2][2][1][1][1][0][1][1][0][1][1][3][1][0][1]
Expected collisions: 73.3915643452334/200
Report collisions: 55/200
成功构建 (总时间: 0 秒)

写了好久终于写出来了！
贡献一下测试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.         */

复制代码

俘虏你的心 发表于 2016-1-6 11:34
写了好久终于写出来了！
贡献一下测试HashTableChained的代码吧。

问一下，那个expected number of collisions 是怎么算的，是需要自己写一个吗，算法是啥。。。。 在tutorial那。。。 好吧我看见了

交作业~~~第一张是100个board, 第二张是200个board。

mingruiyrh 发表于 2016-1-17 05:49
交作业~~~第一张是100个board, 第二张是200个board。

不知道你们是怎么存的hashTable呢? 我是把list变成了泛型， 然后哈希表就是一个泛型list的数组
hashTable = (List<Entry>[]) new Object[capacity];
可是这样初始化的时候就会报错... 好纠结，一边是泛型不能直接创建数组，另一边list又不是Object的子类...
求指点
还是说你们把list的item直接改成了Entry？