一个 Hashmap 桶可以包含不同的哈希编码对象。如果是 hashmap 如何实现 O(1)
A Hashmap bucket can contain different hashcoded object. If so How hashmap achieves O(1)
您好，我正在尝试了解 hashmap 的工作原理。 Hashmap基于hasing原理工作。
我怀疑是否可以在同一个桶中包含不同的哈希编码对象？如果可能意味着 get(key) 如何实现 O(1) 时间 ？因为根据hashcode和hashing，就会找到Bucket。但是必须正确地迭代元素。那么它将如何 O(1).
例如
我的桶大小是 4
我将放置元素 "X"( hashcode - 3) ， "Y" ( hashcode - 7) ， "Z"( hashcode - 11) 。所有这三个元素的桶位置都是 3 。如果我调用 get("Z") 意味着它必须遍历桶中的元素，那么只有它可以找到。那么那将是O(1).
请任何人帮助我消除疑惑。提前致谢
首先，HashMap 的 get(Key)s 时间复杂度 并不总是 O(1)。 O(1) 是理想情况。
HashMap 有一个实例数组 Entry。对象的 HashCode 决定了 "new entry" 应该放在这个数组的哪个索引中。如果 2 个对象必须进入同一个桶/索引（如果存在冲突），则使用 LinkedList 并将新条目添加到 LinkedList。
最坏的情况，所有的条目都可以映射到同一个索引（如果只有一个桶），时间复杂度将是 O(n)。
因为 hashmap 查找算法是这样工作的：
- 从对象中导出整数哈希值 -
O(1)
- 找到该哈希的存储桶 -
O(1)
- 在那个桶中找到对象 -
O(number of collided hashes in that bucket)
尽管在极端情况下（例如我们只有一个桶）number of collided hashes in that bucket可以向n增加，但在推导时不考虑这些情况O算法的正确性。这个值被认为是 1 因为增加 n 不会影响它的成本，即使在 正常 情况下也是线性的。
您好，我正在尝试了解 hashmap 的工作原理。 Hashmap基于hasing原理工作。
我怀疑是否可以在同一个桶中包含不同的哈希编码对象？如果可能意味着 get(key) 如何实现 O(1) 时间 ？因为根据hashcode和hashing，就会找到Bucket。但是必须正确地迭代元素。那么它将如何 O(1).
例如 我的桶大小是 4 我将放置元素 "X"( hashcode - 3) ， "Y" ( hashcode - 7) ， "Z"( hashcode - 11) 。所有这三个元素的桶位置都是 3 。如果我调用 get("Z") 意味着它必须遍历桶中的元素，那么只有它可以找到。那么那将是O(1).
请任何人帮助我消除疑惑。提前致谢
首先，HashMap 的 get(Key)s 时间复杂度 并不总是 O(1)。 O(1) 是理想情况。
HashMap 有一个实例数组 Entry。对象的 HashCode 决定了 "new entry" 应该放在这个数组的哪个索引中。如果 2 个对象必须进入同一个桶/索引（如果存在冲突），则使用 LinkedList 并将新条目添加到 LinkedList。
最坏的情况，所有的条目都可以映射到同一个索引（如果只有一个桶），时间复杂度将是 O(n)。
因为 hashmap 查找算法是这样工作的：
- 从对象中导出整数哈希值 -
O(1) - 找到该哈希的存储桶 -
O(1) - 在那个桶中找到对象 -
O(number of collided hashes in that bucket)
尽管在极端情况下（例如我们只有一个桶）number of collided hashes in that bucket可以向n增加，但在推导时不考虑这些情况O算法的正确性。这个值被认为是 1 因为增加 n 不会影响它的成本，即使在 正常 情况下也是线性的。