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

交作业，本来觉得不是很难，但是在一个小问题上卡了一晚上TAT。。。当定义一个list类型的数组的时候，数组里存放的并不是list,而是指向list的指针！要对数组里的元素赋过值，即新建list并使数组元素指向该list以后才能通过数组下标找到list,否则就会出现nullpointerexception

SaltSprayAir 发表于 2017-6-23 18:44
还算简单，list中把之前作业里的nth用在了HW5的list包了，就很方便。SimpleBoard的hashcode直接sum = sum*2 ...

是不是应该是sum*3 ？

a9x26j8i 发表于 2018-6-22 03:18
我一直不太明白readme.pdf中的a tutorial on collision probability 中：
So when you have i keys in the ...

那你是假定了前面i个item的分布情况，实际上它们的分布情况不知道，可能在一个bucket里，也可能不在。因为新加入的item与任何一个已有的item 不重叠的概率都是 1 － 1/N，那么与前i个都不重叠的概率就是它的i次方。

问一个问题，remove 的时候如果有相同的key随机删除一个是怎么做到的？

本次作业是关于hash table，总体来说难度不是很大，但是自己实现的时候还是磕磕绊绊的，参考了别人的代码。
1.对于N的选取，我是用了sieve of eratosthenes找素数的方法，然后检查 sizeEsitimate~2*sizeEsitimate中，取一个素数p，使得 sizeEsitimate/p的值最接近0.75
2.写SimpleBoard类中的hashcode()我们可以将每个格子对应的（i，j）对应不同的幂（从0~63)，但是我不理解的是为什么要舍掉高位？虽然我理解舍掉高位之后会造成冲突..
3.本次好多测试代码都要自己写，一脸懵逼，最后的Homework6Test中的 histograph输出方法还是从别人那找来的...心累

打卡hw6，感觉难度不是很大，遇到的唯一bug就是一开始总是提示insert函数数组索引越界，发现java自带的hashcode函数可能会求出负数，于是加上绝对值即可:Math.abs(((a*code+b)%p)%N)，另外就是对于hashcode的原理还是不太了解，数论基础太差，，，，继续，，，，hw7走起！！！！！

1. 不知道为啥得到的bucket index有负数，有一个同学说"hashcode在乘以一个常数a后溢出导致变为了负数"。但依照lecture notes的意思，是因为hashcode本身很可能是负数（为啥会这样？），所以要用mod这个运算符，这样就会得到正数，可我好像是用不了这个运算符，不知道大家能不能。。。。总之我后来用的运算符是%并且对负值的index加了一个N2. buckets我考虑到loadfactor控制在0.5-1，我想接近0.5就用了小于2倍entry数的最小质数，但出来的结果有时候会比expected collisions少很多，但感觉大家发的图片都很接近expected，有点奇怪。。。。
3. 另外大家都在说的int截取问题一开始其实我都没想到（int截取低32位）4. 还有出错的地方是在算expected collisions的时候，要精确的话要把运算中的任一个cast成double或float（这个作业里就是double）
5. 并不太懂((a * hashcode + b) % p) % N，这里a,b,p的取值该怎么取，我都是挑的正质数

附上截图：

其实主要考察的就是HashCode()和CompressionFunction()函数的实现及其作用：

一句话概括，就是为了使得某种object（例如String类，SimpleBoard类）作为key可以尽可能离散地分布在Dictionary（由HashTable或SearchTree实现）中。
因此，hashcode与compression function函数的好坏主要由keys能否在buckets里面实现随机分布决定，loadfactor越大，collision越小，离散性越好。

1、关于hashcode
对于不同的object，有不同的hashcode求法，尽可能使object在不同状态时，hashcode没有重复的数字，所以hashcode的求法最好范围比较大，事实上，在int 的范围内（±2^32）都可以，超过也可以考虑，因为java会将超出的高位截掉。
对于homework06而言，对于一个8*8的棋盘，每个点有三种状态（0,1,2）（空，白棋，黑棋），我们视棋盘的第1到第64个棋点分别为（k=1-64）,k设为权数。然后每个棋点视为以3为基数的digit。即3^k。
这样保证了每个不同的棋点的离散性很好。最后的整个棋盘的hashcode即为3^k乘上对应的棋点的状态（0,1,2）。超出int 的部分被截取掉了。

事实上这又有点blackart，不能用很严谨的说法说明这个的正确性，这也是离散令人着迷的地方。（同时说明学什么最后都是学数学TAT）


2、关于CompressionFunction
【Compression Function的作用：】
     *  Converts a hash code in the range Integer.MIN_VALUE...Integer.MAX_VALUE to a value in the range 0...(size of hash table) - 1.

h(i) = |i| mod N，h(i) = ((ai + b) mod p) mod N)其实效果差不多，得到的结果都比较接近expected number，可能是样本量太小的原因。

2.1 取质数的原因
因为被除和p如果有公约数c，则该公约数c也是余数r的约数，即r必须是c的倍数；这就限制了余数的分布

2.2 ((ai + b) mod p) mod N)的合理性
Ar+b 在（B,Ar+B)这个长度为Ar的区间里，用它去%n会得到平均间隔为A的分布，相当于把原来在(0,r)里面 %n 的分布稀释了A倍。然而，Ar和r形成了对r而言的【线性映射】，比如原来长度为r的区间里可能的取值为(0,1,2),长度为3；假设A＝2，B＝0, 那么映射到长度为3*2的区间里就是(0,2,4);给的空间大了，但是间隔也相应变大了，1,3,5这些值没有可能取到！所以collision的概率是一样的。那么只要破坏这种线性映射就好了，取mod明显是非线性的，而且是mod质数。

2.3 为什么p>>N？
因为mod p 就会映射到(0,p)，第二步mod n要从(0,p)映射到(0,n), 如果这两个区间大小差不多的话，就没有第二步的必要了，直接认为p就是n就可以了。另外一个理由：因为要一直resize hash table, 通常就是翻倍, 所以N必须比P小很多。

3、HashTable的结构
哈希表是由一个static type为List的Array，以及很多个链表（一般是单向链表）组成，Array的size由constructor来定，homework06里面给了两种方法。其中Array中的每个项都指向一个List，这个一般是SList，所以可以直接用homework05中的SList和SListNode，在后面implementation时用了这两个class中的public method，非常的方便。让我们重新复习了Elegant Interface的重要性。

这里SList又可以视为Chain，SListNode中储存item（Entry类）和next（SListNode类），如果有collision，next指向新增的那个Node，否则指向null；

交作业了 题目不难 但debug了好久 主要是数字的类型转换有问题 第一次超过int的上界了 换了long之后好了