hashmap 实例化是如何工作的？
How does hashmap instantiation work under the hood?
有人告诉我哈希图的复杂度为 O(1)（忽略冲突）。向我解释如下：
内存中的一个范围是为散列图保留的。一个密钥被散列到这个范围内的一个看似随机的地址。我们将键值对存储在该地址。多个密钥可以散列到同一个地址的可能性可以通过每次发生这种冲突时重新散列来解决，或者通过让每个使用的地址存储一个指向散列到该地址的所有内容的链表的指针来解决。
稍后可以对键进行哈希处理，以检查是否找到匹配的键值对（如有必要，可重新利用存储期间使用的相同冲突解决方案）。如果找到密钥，则返回值。
但是如果将内存范围分配给哈希图，则之前存在的位可能会模仿存在的键值对。所以我认为 hashmap 的内存范围必须在实例化时清理（或者更早......？）。由于该范围不能明显小于要存储的物品数量，所以卫生不是 O(n) 吗？现代硬件是否通过任何指令用重复值填充内存范围来解决这个问题？如果是这样，这条指令的出现是否使 hashmaps 可行？否则，我不明白这是如何工作的。当然，这个 O(n) 将是实例化的一次性事件。但是其他存储方法应该永远不会比 O(log(n)) 慢。请帮助我，我错过了什么？
典型的 HashMap 实现在构造时会分配一个小的 table。然后当项目的数量超过 table 大小的某个常数因子时，它将分配一个 table 两倍大并将所有键移到新的。
这导致分摊的 O(1) 插入时间，但当需要分配 table 时，实际最坏情况下的 O(n) 插入时间。处理冲突会将“摊销”O(1) 时间降级为“预期”O(1) 时间。
可能，但是，逐步将密钥移至重新分配的table，分散该成本，以便每个操作确实是 O(1) .但是，很少这样做，因为它不能保证 O(1) 时间——再次出现冲突问题，并且不能保证您甚至可以在恒定时间内分配内存。
这回答了您关于哈希映射的问题，但您最初关于初始化成本的思路也理论上不适用。看到这个答案：
有人告诉我哈希图的复杂度为 O(1)（忽略冲突）。向我解释如下：
内存中的一个范围是为散列图保留的。一个密钥被散列到这个范围内的一个看似随机的地址。我们将键值对存储在该地址。多个密钥可以散列到同一个地址的可能性可以通过每次发生这种冲突时重新散列来解决，或者通过让每个使用的地址存储一个指向散列到该地址的所有内容的链表的指针来解决。
稍后可以对键进行哈希处理，以检查是否找到匹配的键值对（如有必要，可重新利用存储期间使用的相同冲突解决方案）。如果找到密钥，则返回值。
但是如果将内存范围分配给哈希图，则之前存在的位可能会模仿存在的键值对。所以我认为 hashmap 的内存范围必须在实例化时清理（或者更早......？）。由于该范围不能明显小于要存储的物品数量，所以卫生不是 O(n) 吗？现代硬件是否通过任何指令用重复值填充内存范围来解决这个问题？如果是这样，这条指令的出现是否使 hashmaps 可行？否则，我不明白这是如何工作的。当然，这个 O(n) 将是实例化的一次性事件。但是其他存储方法应该永远不会比 O(log(n)) 慢。请帮助我，我错过了什么？
典型的 HashMap 实现在构造时会分配一个小的 table。然后当项目的数量超过 table 大小的某个常数因子时，它将分配一个 table 两倍大并将所有键移到新的。
这导致分摊的 O(1) 插入时间，但当需要分配 table 时，实际最坏情况下的 O(n) 插入时间。处理冲突会将“摊销”O(1) 时间降级为“预期”O(1) 时间。
可能，但是，逐步将密钥移至重新分配的table，分散该成本，以便每个操作确实是 O(1) .但是，很少这样做，因为它不能保证 O(1) 时间——再次出现冲突问题，并且不能保证您甚至可以在恒定时间内分配内存。
这回答了您关于哈希映射的问题，但您最初关于初始化成本的思路也理论上不适用。看到这个答案：