吐槽一下Morgan Stanley的电面

实现一个HashMap应该算是放水题呀，这个考点应该是如何实现一个比较好的hash function

Sipsontit 发表于 2018-6-12 22:52
实现一个HashMap应该算是放水题呀，这个考点应该是如何实现一个比较好的hash function

哎，我也不是完全答不上来呀，前面也答对了，就是问到后面细节的时候，比如如何做到O(1)的时候有点儿卡住了，然后他就开始说那些你cs的怎么连这个都不知道之类的话……我承认我准备得是不充分，因为我平时也用不上这些东西，我工作上用的是functional language，但是我觉得这个面试官这么赤裸裸地挖苦一个去面试的人，实在是不妥……我水平不够就行了，何必直接鄙视呢？

MonikaZ 发表于 2018-6-12 23:54
哎，我也不是完全答不上来呀，前面也答对了，就是问到后面细节的时候，比如如何做到O(1)的时候有点儿卡住 ...

黑人问号.jpg
有点好奇能不能把不是O(1)的代码贴一下，多谢了!

Sipsontit 发表于 2018-6-12 22:52
实现一个HashMap应该算是放水题呀，这个考点应该是如何实现一个比较好的hash function

请问层主有没有好的资料讲如何实现good hash function呢？

Sipsontit 发表于 2018-6-13 02:27
黑人问号.jpg
有点好奇能不能把不是O(1)的代码贴一下，多谢了!

我想不通的是，一百万个记录，放在size为300的hashmap里，那肯定有很多的collision，每个key对应的链表（或者红黑树）也会非常的长（大），我们需要遍历这部分去寻找是不是有存在的key，value对呀，你这部分怎么做到O(1)?

补充内容 (2018-6-13 10:39):
不是遍历，是查找……笔误

补充内容 (2018-6-13 10:43):
换句话说，O(1)是理想状态下的（没有冲突），但是按照面试官出题的这个思路，我是打死都想不通怎么可以做到O(1)... 哪位大神能点播一下我？

MonikaZ 发表于 2018-6-13 10:38
我想不通的是，一百万个记录，放在size为300的hashmap里，那肯定有很多的collision，每个key对应的链表（ ...

有冲突也是O(1)啊，worst case才是O(N)，所以需要一个分布均匀的hash function