java - 如何在自定义 HashMap 实现中创建 O(1) 时间复杂度的查找方法和插入方法？

Question

我正在自定义 HashMap 实现，但不使用 HashMap 数据结构作为分配的一部分，目前我可以选择使用两个一维数组或使用一个二维数组来存储我的键和值。我希望能够检查某个键是否存在并以 O(1) 时间复杂度(赋值要求)返回相应的值，但我假设它不使用 containsKey() 。

此外，当将键和值对插入到我的数组时，我很困惑，因为逻辑上它不应该是 O(1)，因为偶尔会出现冲突并且我必须重新计算索引，所以为什么是插入的赋值要求 O(1)？

Answer 1

里面有很多问题，我来试试。

I want to be able to check if a key exists and return the corresponding value in O(1) time complexity (assignment requirement) but i am assuming it is without the use of containsKey().

这实际上没有什么区别。 O(1) 意味着执行时间与输入无关，并不意味着使用单个操作。如果您的 containsKey() 和 put() 实现都是 O(1)，那么您的解决方案仅使用它们一次。

Also, when inserting key and value pairs to my arrays, i am confused because it should not be O(1) logically, since there would occasionally be cases where there is collision and i have to recalculate the index, so why is the assignment requirement for insertion O(1)?

O(1) 是最好的情况，假设不存在哈希冲突。如果每个键生成相同的哈希码，最坏的情况是 O(n)。因此，当 HashMap 的查找或插入性能计算为 O(1) 时，就假设了完美的 hashCode 实现。

最后，说到数据结构，通常的做法是使用单个数组，其中数组项是链表节点。数组偏移量对应于 hashcode() % 数组大小(还有比这更多的高级公式，但这是一个很好的起点)。如果发生哈希冲突，您将必须导航链表节点，直到找到正确的条目。