hashmap 如何提供恒定时间性能？

Question

这可能看起来像是一个问题，之前被问过一百万次。但是我有一些疑问很久了，一直没有得到正确的答案。

假设我有一个包含 1100 个元素的哈希图。我假设地图中有 1000 个桶。

所以当我插入一个新元素时，它首先导出键的哈希值，比如它的 676，现在它会检查 676 存储桶在哪里，并将对象作为 EntryObject 放入存储桶中。

现在我的问题是它是如何到达 676 桶的？我假设这些桶哈希已编入索引，我的意思是有序。就像我有一本1000页的书，我想去676页，我不能直接打开页面，我可以到达接近676的页面，基于书的宽度的假设，并且再试几次，我就可以翻到第 676 页。这本书是 100 页还是 1000000 页，与 1:10000 没有太大区别，但在到达确切页面之前，我必须进行几次试验。

我的问题是，它在 HashMap 中是如何发生的？此外，如果你们中的任何人给我一些深入了解内部工作的线索，这将非常有帮助。

谢谢

Answer 1

这是一个数组查找。当您解析 someArray[index] 时，您不会翻阅页面，您将一个元素的大小乘以索引添加到第一个条目的地址，然后就可以了。