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

作业入口：  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数目。
输出见图：

做了一下午才做完。。各种出错，对hashtable的理解不够到位，一开始构建hashtable想了不少时间

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

复制代码

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

hw6 done....

交作业，图片能看到吗？

homework 6 终于写完了，这次赶脚比前几次简单

这次作业我有一点始终没想明白，如果要表达3*3......*3，一共3^64个不同的格点图，可是32位int只能拥有2^32个不同的数。不管再怎么优秀的计算方法，也不可能用少量的数，表达数量比他还要多的图啊？

交作业，拿学分

chaosyi 发表于 2014-11-8 11:39
这次作业我有一点始终没想明白，如果要表达3*3......*3，一共3^64个不同的格点图，可是32位int只能拥有2^32 ...

int 将超出的高位数截掉了

这个题目要思考的其实挺多的，
第一是 bucket 的数目 N 怎么取？  
第二是 Board 的 hashCode() 函数怎么写？ Java的int是怎么截取的？
第三是分配 bucket 的 compression 函数怎么写？

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

交作业啦

有点没搞明白的是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的概率将会减少。
各位大神我可能表达的不太清楚，不知道这样理解对不对。