我在面试中被问到这个问题并且被遗忘了,尽管我想出了一个答案我对我的解决方案感到不舒服.我想看看这里的专家对这个问题的看法.
我正在引用面试官的问题."设计一个哈希表,你可以使用你想要的任何数据结构.我想看看你如何实现O(1)查找时间".最后他说,这更像是通过另一个数据结构模拟哈希表.
有关这个问题的更多信息,任何人都可以点亮我.谢谢!
PS:我提出这个问题的主要原因是要知道专家设计师如何从这个问题的设计开始&&还有一件事,我根据提出的其他问题以某种方式清除了采访,但这个问题在我脑海中,我想找出答案!
bra*_*ain 36
这是一个相当标准的面试问题,它表明你理解了基础概念是有用的Java数据结构,比如HashSet和HashMap.
您将使用列表数组,这些列表通常称为存储桶.您以给定容量n开始哈希表,这意味着您有一个包含10个列表的数组(全部为空).
要向hastable中添加一个对象,可以调用objects hashCode函数,该函数为你提供一个int(一个非常大的范围内的数字).因此,您必须将hashCode wrt模数为n,以便为其提供存储的存储桶.将对象添加到该存储桶中列表的末尾.
要查找对象,请再次使用hashCode和mod函数查找存储区,然后使用.equals()查找正确的对象来遍历列表.
随着表格越来越丰富,您最终会进行越来越多的线性搜索,因此您最终需要重新哈希.这意味着构建一个全新的,更大的表并再次将对象放入其中.
如果您想要的那个位置已满,则可以重新计算不同的铲斗位置,而不是在每个阵列位置使用List,常见的方法是二次探测.这样做的优点是不需要像列表那样的任何动态数据结构,但更复杂.