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

这次作业写了好久。。 一开始犯了超傻逼的错误，非要重写List改成泛型，忘记object是所有类的超类，entry可以直接作为item了...
然后关于simpleBoard的hash函数纠结了好久，一直觉得直接舍弃高位是不对的，然而并没有找到很好的解决方法...
总之这次作业让我对哈希有了更深的理解，赞！

这次作业更透彻的理解了hashTable, 一个array ,每个index 又对应了一个list. list node 的item ,object又对应着Entry 这个object。
在输入参数时用到了BankApp中的方法。

总算有点明白hashcode了

buildgood 发表于 2016-2-11 22:29
总算有点明白hashcode了

层主，请问能不能分享一下你的hashCode和compression function的代码？
我纠结了很久。hashcode我用readme里的方法，就是看作64位的3进制数然后转化成int型舍去高位；compression function按照readme和课堂讲义里的方法是((a * hashcode + b) % p) % N，可是a,b,p的取值又该怎么取？我是随便取了2个整数a,b和一个大素数p，这样做对吗？
可是为什么我的程序最终的运行结果actual collision数和expected collision数差的很多呢？

做是做完了，可是我的actual collision和expected collision差很多？
是不是因为我的hashcode或者compression function写得不好？
hashcode我用readme里的方法，就是看作64位的3进制数然后转化成int型舍去高位；compression function按照readme和课堂讲义里的方法是((a * hashcode + b) % p) % N，可是a,b,p的取值又该怎么取？我是随便取了2个整数a,b和一个大素数p，这样做对吗？
跪求大神解答
如果可以的话，能不能分享一下你们的hashcode和compression function代码？

付运行结果：

hypsm 发表于 2016-1-30 17:35
这次作业写了好久。。 一开始犯了超傻逼的错误，非要重写List改成泛型，忘记object是所有类的超类，e ...

层主，请问能不能分享一下你的hashCode和compression function的代码？
我纠结了很久。hashcode我用readme里的方法，就是看作64位的3进制数然后转化成int型舍去高位；compression function按照readme和课堂讲义里的方法是((a * hashcode + b) % p) % N，可是a,b,p的取值又该怎么取？我是随便取了2个整数a,b和一个大素数p，这样做对吗？
可是为什么我的程序最终的运行结果actual collision数和expected collision数差的很多呢？

阿童木 发表于 2016-2-28 12:04
层主，请问能不能分享一下你的hashCode和compression function的代码？
我纠结了很久。hashcode我用read ...

给你发了私信。

hypsm 发表于 2016-2-28 12:16
给你发了私信。

太感谢啦！！！

据前面的一些层主和readme里的提示，expected collision和actual collision越接近，说明hashcode和compression function越好。
但是，当用SimpleBoard做哈希表时，每次测试插入hashTable的元素是不同的（每个SimpleBoard都用随机数生成，每次测试都不同），那么每次测试对应的hashcode值也不同，压缩后映射到哈希表中的分布就不同，所以每次测试的actual collision的都会不同啊！？
这样每次和expected collision比较的结果都不同，这样又怎么去评估hashcode和compression function的优劣呢？
有没有小伙伴可以解释一下？
或者是我从一开始就理解错了？
好纠结，求解！

hypsm 发表于 2016-2-28 12:16
给你发了私信。

同学好，我看了你的代码，很受益！但是我还是有一点不明白的，想向你请教：
据前面的一些层主和readme里的提示，expected collision和actual collision越接近，说明hashcode和compression function越好。
但是，当用SimpleBoard做哈希表时，每次测试插入hashTable的元素是不同的（每个SimpleBoard都用随机数生成，每次测试都不同），那么每次测试对应的hashcode值也不同，压缩后映射到哈希表中的分布就不同，所以每次测试的actual collision的都会不同啊！？
这样每次和expected collision比较的结果都不同，这样又怎么去评估hashcode和compression function的优劣呢？
是我从一开始就理解错了吗？