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

花了一下午时间终于做完了
感觉hashcode的方法并不是很好
坚持学习！打卡求加分！

一开始不明白为什么key可以直接调用hashcode。后来想想，是不是因为key是object类型，超类可以调用任何一个类？？求大神回复。不对，好像我错了。是因为hashcode所在的类SimpleBoard在默认包里，dict包里的key可以直接调用默认包里的hashcode。所以是默认包里的类可以被其他包任意调用不用import？？？

对实现hashtable有了一定的了解。下图是测试HashTableChained的结果：

下面两张图是计算collisions.

hash table的大小不同，得出来的collision number也不同，挺有意思的

1. hw6 $ java Homework6Test
   
2. HashTableChain overview:
   
3. 
   
4. Bucket[0]:
   
5. 
   
6. Bucket[1]: (SimpleBoard@89c21b, 0)
   
7. 
   
8. Bucket[2]: (SimpleBoard@ffc57689, 87)
   
9. 
   
10. Bucket[3]:
    
11. 
    
12. Bucket[4]: (SimpleBoard@ff4502f9, 39) (SimpleBoard@30c70d, 85)
    
13. 
    
14. Bucket[5]:
    
15. 
    
16. Bucket[6]: (SimpleBoard@ff5dac31, 75)
    
17. 
    
18. Bucket[7]:
    
19. 
    
20. Bucket[8]:
    
21. 
    
22. Bucket[9]: (SimpleBoard@b8deae, 84)
    
23. 
    
24. Bucket[10]:
    
25. 
    
26. Bucket[11]:
    
27. 
    
28. Bucket[12]: (SimpleBoard@ffd21fc7, 57)
    
29. 
    
30. Bucket[13]: (SimpleBoard@ff9c5fd5, 34)
    
31. 
    
32. Bucket[14]:
    
33. 
    
34. Bucket[15]: (SimpleBoard@ffcef9e6, 78)
    
35. 
    
36. Bucket[16]:
    
37. 
    
38. Bucket[17]:
    
39. 
    
40. Bucket[18]:
    
41. 
    
42. Bucket[19]:
    
43. 
    
44. Bucket[20]: (SimpleBoard@77ec63, 13)
    
45. 
    
46. Bucket[21]:
    
47. 
    
48. Bucket[22]:
    
49. 
    
50. Bucket[23]: (SimpleBoard@ffe5c0d7, 51) (SimpleBoard@ff5ce3a0, 92)
    
51. 
    
52. Bucket[24]:
    
53. 
    
54. Bucket[25]: (SimpleBoard@16ae97, 44)
    
55. 
    
56. Bucket[26]:
    
57. 
    
58. Bucket[27]:
    
59. 
    
60. Bucket[28]:
    
61. 
    
62. Bucket[29]: (SimpleBoard@ffa98f3b, 99)
    
63. 
    
64. Bucket[30]:
    
65. 
    
66. Bucket[31]: (SimpleBoard@63bdb2, 79)
    
67. 
    
68. Bucket[32]:
    
69. 
    
70. Bucket[33]:
    
71. 
    
72. Bucket[34]:
    
73. 
    
74. Bucket[35]:
    
75. 
    
76. Bucket[36]: (SimpleBoard@9f380, 12)
    
77. 
    
78. Bucket[37]:
    
79. 
    
80. Bucket[38]:
    
81. 
    
82. Bucket[39]: (SimpleBoard@fffc9132, 28) (SimpleBoard@ff2140c4, 82)
    
83. 
    
84. Bucket[40]:
    
85. 
    
86. Bucket[41]:
    
87. 
    
88. Bucket[42]:
    
89. 
    
90. Bucket[43]: (SimpleBoard@fffd0f2b, 45)
    
91. 
    
92. Bucket[44]:
    
93. 
    
94. Bucket[45]: (SimpleBoard@ffcc909f, 37) (SimpleBoard@d051b7, 56)
    
95. 
    
96. Bucket[46]:
    
97. 
    
98. Bucket[47]: (SimpleBoard@45afb8, 30)
    
99. 
    
100. Bucket[48]: (SimpleBoard@ff658fcb, 54)
     
101. 
     
102. Bucket[49]: (SimpleBoard@84cbaa, 33)
     
103. 
     
104. Bucket[50]: (SimpleBoard@503571, 20)
     
105. 
     
106. Bucket[51]:
     
107. 
     
108. Bucket[52]:
     
109. 
     
110. Bucket[53]: (SimpleBoard@9271de, 93)
     
111. 
     
112. Bucket[54]: (SimpleBoard@ffbbff56, 94)
     
113. 
     
114. Bucket[55]:
     
115. 
     
116. Bucket[56]: (SimpleBoard@b3c6ff, 42)
     
117. 
     
118. Bucket[57]: (SimpleBoard@ffa13381, 19)
     
119. 
     
120. Bucket[58]:
     
121. 
     
122. Bucket[59]:
     
123. 
     
124. Bucket[60]:
     
125. 
     
126. Bucket[61]:
     
127. 
     
128. Bucket[62]: (SimpleBoard@ff531df8, 1)
     
129. 
     
130. Bucket[63]: (SimpleBoard@d19102, 17) (SimpleBoard@6bb375, 18)
     
131. 
     
132. Bucket[64]:
     
133. 
     
134. Bucket[65]: (SimpleBoard@fffca230, 6)
     
135. 
     
136. Bucket[66]:
     
137. 
     
138. Bucket[67]: (SimpleBoard@645671, 89)
     
139. 
     
140. Bucket[68]:
     
141. 
     
142. Bucket[69]:
     
143. 
     
144. Bucket[70]:
     
145. 
     
146. Bucket[71]:
     
147. 
     
148. Bucket[72]:
     
149. 
     
150. Bucket[73]:
     
151. 
     
152. Bucket[74]:
     
153. 
     
154. Bucket[75]: (SimpleBoard@4fc65b, 29) (SimpleBoard@ffa9ff46, 77)
     
155. 
     
156. Bucket[76]: (SimpleBoard@ff6b12f9, 40)
     
157. 
     
158. Bucket[77]:
     
159. 
     
160. Bucket[78]:
     
161. 
     
162. Bucket[79]:
     
163. 
     
164. Bucket[80]:
     
165. 
     
166. Bucket[81]:
     
167. 
     
168. Bucket[82]: (SimpleBoard@5640b3, 62)
     
169. 
     
170. Bucket[83]: (SimpleBoard@c57782, 91)
     
171. 
     
172. Bucket[84]: (SimpleBoard@30b2ec, 36) (SimpleBoard@ff30ee7b, 66) (SimpleBoard@803101, 72)
     
173. 
     
174. Bucket[85]: (SimpleBoard@89d28e, 38)
     
175. 
     
176. Bucket[86]: (SimpleBoard@449c60, 21) (SimpleBoard@ff23bd55, 96)
     
177. 
     
178. Bucket[87]: (SimpleBoard@ffd80fb5, 24)
     
179. 
     
180. Bucket[88]:
     
181. 
     
182. Bucket[89]: (SimpleBoard@ae9774, 11)
     
183. 
     
184. Bucket[90]: (SimpleBoard@b24f84, 35)
     
185. 
     
186. Bucket[91]:
     
187. 
     
188. Bucket[92]: (SimpleBoard@d03352, 67)
     
189. 
     
190. Bucket[93]: (SimpleBoard@7dc54, 71)
     
191. 
     
192. Bucket[94]:
     
193. 
     
194. Bucket[95]:
     
195. 
     
196. Bucket[96]: (SimpleBoard@cc5440, 68)
     
197. 
     
198. Bucket[97]:
     
199. 
     
200. Bucket[98]:
     
201. 
     
202. Bucket[99]:
     
203. 
     
204. Bucket[100]:
     
205. 
     
206. Bucket[101]:
     
207. 
     
208. Bucket[102]: (SimpleBoard@fffa2e4c, 2)
     
209. 
     
210. Bucket[103]:
     
211. 
     
212. Bucket[104]:
     
213. 
     
214. Bucket[105]:
     
215. 
     
216. Bucket[106]:
     
217. 
     
218. Bucket[107]:
     
219. 
     
220. Bucket[108]: (SimpleBoard@2f3af2, 98)
     
221. 
     
222. Bucket[109]: (SimpleBoard@9f7df0, 26)
     
223. 
     
224. Bucket[110]: (SimpleBoard@9644f6, 22) (SimpleBoard@ff7486d2, 61) (SimpleBoard@ff3aa8fb, 65)
     
225. 
     
226. Bucket[111]:
     
227. 
     
228. Bucket[112]: (SimpleBoard@ffa347fe, 64)
     
229. 
     
230. Bucket[113]:
     
231. 
     
232. Bucket[114]: (SimpleBoard@922ad0, 55)
     
233. 
     
234. Bucket[115]: (SimpleBoard@984cdd, 48)
     
235. 
     
236. Bucket[116]: (SimpleBoard@ff6b2165, 14) (SimpleBoard@487b6c, 52)
     
237. 
     
238. Bucket[117]:
     
239. 
     
240. Bucket[118]: (SimpleBoard@9687e6, 53) (SimpleBoard@ffc59ddf, 63)
     
241. 
     
242. Bucket[119]: (SimpleBoard@ff9082b9, 10)
     
243. 
     
244. Bucket[120]:
     
245. 
     
246. Bucket[121]:
     
247. 
     
248. Bucket[122]:
     
249. 
     
250. Bucket[123]:
     
251. 
     
252. Bucket[124]:
     
253. 
     
254. Bucket[125]:
     
255. 
     
256. Bucket[126]: (SimpleBoard@4c6c22, 9)
     
257. 
     
258. Bucket[127]: (SimpleBoard@8a032, 5) (SimpleBoard@fff031b0, 50)
     
259. 
     
260. Bucket[128]:
     
261. 
     
262. Bucket[129]:
     
263. 
     
264. Bucket[130]:
     
265. 
     
266. Bucket[131]: (SimpleBoard@2bab90, 46) (SimpleBoard@16ddfb, 49)
     
267. 
     
268. Bucket[132]:
     
269. 
     
270. Bucket[133]: (SimpleBoard@644e36, 70) (SimpleBoard@ffc18b08, 80)
     
271. 
     
272. Bucket[134]:
     
273. 
     
274. Bucket[135]: (SimpleBoard@9c8fb1, 32)
     
275. 
     
276. Bucket[136]:
     
277. 
     
278. Bucket[137]:
     
279. 
     
280. Bucket[138]:
     
281. 
     
282. Bucket[139]:
     
283. 
     
284. Bucket[140]: (SimpleBoard@ff9d5641, 69)
     
285. 
     
286. Bucket[141]: (SimpleBoard@6ec75b, 47)
     
287. 
     
288. Bucket[142]: (SimpleBoard@ffc6a418, 60)
     
289. 
     
290. Bucket[143]:
     
291. 
     
292. Bucket[144]:
     
293. 
     
294. Bucket[145]:
     
295. 
     
296. Bucket[146]: (SimpleBoard@ff140356, 59)
     
297. 
     
298. Bucket[147]: (SimpleBoard@de21c8, 15) (SimpleBoard@ffae0e94, 31)
     
299. 
     
300. Bucket[148]: (SimpleBoard@ffc207c3, 95)
     
301. 
     
302. Bucket[149]:
     
303. 
     
304. Bucket[150]:
     
305. 
     
306. Bucket[151]: (SimpleBoard@43d070, 3) (SimpleBoard@ff7c176e, 90)
     
307. 
     
308. Bucket[152]: (SimpleBoard@ff94d2b6, 43)
     
309. 
     
310. Bucket[153]:
     
311. 
     
312. Bucket[154]:
     
313. 
     
314. Bucket[155]:
     
315. 
     
316. Bucket[156]:
     
317. 
     
318. Bucket[157]:
     
319. 
     
320. Bucket[158]: (SimpleBoard@ff9b3cea, 23) (SimpleBoard@ffd00e08, 86)
     
321. 
     
322. Bucket[159]:
     
323. 
     
324. Bucket[160]:
     
325. 
     
326. Bucket[161]:
     
327. 
     
328. Bucket[162]:
     
329. 
     
330. Bucket[163]:
     
331. 
     
332. Bucket[164]:
     
333. 
     
334. Bucket[165]:
     
335. 
     
336. Bucket[166]:
     
337. 
     
338. Bucket[167]:
     
339. 
     
340. Bucket[168]:
     
341. 
     
342. Bucket[169]: (SimpleBoard@ffcdc5c8, 27)
     
343. 
     
344. Bucket[170]:
     
345. 
     
346. Bucket[171]: (SimpleBoard@ffd85759, 81)
     
347. 
     
348. Bucket[172]:
     
349. 
     
350. Bucket[173]:
     
351. 
     
352. Bucket[174]:
     
353. 
     
354. Bucket[175]: (SimpleBoard@fff6fead, 7)
     
355. 
     
356. Bucket[176]: (SimpleBoard@343bf6, 4)
     
357. 
     
358. Bucket[177]: (SimpleBoard@dc7311, 88) (SimpleBoard@c0381a, 97)
     
359. 
     
360. Bucket[178]:
     
361. 
     
362. Bucket[179]:
     
363. 
     
364. Bucket[180]:
     
365. 
     
366. Bucket[181]:
     
367. 
     
368. Bucket[182]:
     
369. 
     
370. Bucket[183]:
     
371. 
     
372. Bucket[184]: (SimpleBoard@ff95c1b3, 73)
     
373. 
     
374. Bucket[185]: (SimpleBoard@ff742f34, 58)
     
375. 
     
376. Bucket[186]:
     
377. 
     
378. Bucket[187]:
     
379. 
     
380. Bucket[188]: (SimpleBoard@ff993279, 74)
     
381. 
     
382. Bucket[189]: (SimpleBoard@ff7c2ae2, 16) (SimpleBoard@ffc33349, 41)
     
383. 
     
384. Bucket[190]:
     
385. 
     
386. Bucket[191]:
     
387. 
     
388. Bucket[192]:
     
389. 
     
390. Bucket[193]: (SimpleBoard@4259d2, 8)
     
391. 
     
392. Bucket[194]:
     
393. 
     
394. Bucket[195]:
     
395. 
     
396. Bucket[196]: (SimpleBoard@e75577, 76)
     
397. 
     
398. Bucket[197]: (SimpleBoard@deb412, 83)
     
399. 
     
400. Bucket[198]: (SimpleBoard@63910b, 25)
     
401. Expected number of collisions is: 21.24428979291629
     
402. Actual number of collisions is: 21
     

复制代码

顺便问一下,好像大家的截图里,实际冲突数都少于期望值. 你们提交的时候,选了少的,还是总是少于期望冲突数?我觉得应该是上下浮动的吧! 只要平均值是期望值就可以了.

很有意思，继续努力！！！！！！！！
还是感觉难。。。做完之后感觉好点

记录几个点：
1. for each 不能用来赋值
2. readme 里这句话超级重要(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.  Better to round off the most
significant digits, which is what happens when an int gets too big.)那个Math函数是浮点数，导致截取错误hashcode一直是同一个3. 区分好N(总共的bucket)和n（总共的entry）

这次作业好难，，，感觉自己hashcode写的并不是特别好，伤心

hw6打卡，求学分

做完了，不难。但总感觉hashtable这里很繁杂，希望以后用到时候不要头大。
另外，没有人一起做project2 吗？