考虑一个 int 数组变量 x[]。变量 X 将具有起始地址引用。当使用索引 2(即 x[2])访问数组时，其内存位置计算为
x[2] 的地址是起始地址 + 索引 * int 的大小。
即。 x[2]=x + 2*4。
但是在 hashmap 的情况下，内存地址将如何在内部映射。
通过阅读之前的很多帖子，我发现HashMap使用链表来存储键值列表。但如果是这种情况，那么为了找到一个键，它会生成一个哈希码，然后它会检查列表中是否有相同的哈希码并检索该值。
这需要 O(n) 复杂度。 如果我的上述观察有误，请纠正我......我是初学者。 谢谢
最佳答案
HashMap 的传统实现是使用函数生成键，然后使用该键直接访问值。将其视为生成将转换为数组索引的东西。它不会查看 HashMap ，将元素哈希值与生成的哈希值进行比较；它生成哈希，并使用哈希直接访问元素。
我认为你正在谈论的是 HashMap 中的两个值生成相同键的情况。然后它使用这些列表，并且必须仔细查看它们以确定它想要哪个。但这不是 O(n)，其中 n 是 HashMap 中的元素数量，而只是 O(m)，其中 m 是具有相同哈希的元素数量。显然，游戏的名称是找到一个哈希函数，其中生成的哈希对于所有元素来说都是唯一的，尽可能可行。
--- 编辑以扩展解释 ---
在您的帖子中，您声明:
By reading many previous posts I observed that HashMap uses a linked list to store the key value list.
这对于整个 HashMap 来说是错误的。为了使 HashMap 合理工作，必须有一种方法可以使用键来计算直接访问相应元素的方法，而不是通过搜索 HashMap 中的所有值。
“完美”的哈希计算会将每个可能的键转换为未针对任何其他键计算的哈希值。这通常是不可行的，因此两个不同的 key 通常可能会产生相同的哈希计算结果。在这种情况下，HashMap 实现可以使用值的链接列表，并且需要查看所有此类值以找到它正在查找的值。但这个数字远小于整个 HashMap 中值的数量。
您可以创建一个散列，其中字符串为键，其中字符串的第一个字符被转换为数字，然后用作数组索引。只要您的字符串都有不同的第一个字符，那么访问该值就是一个简单的计算加上数组访问 - O(1)。或者您可以将字符串索引的所有字符值加在一起并取最后两位(或三位)数字，这就是您的哈希计算。只要加法为每个索引字符串生成唯一的值，您就不必查看列表；再次，O(1)。
事实上，只要哈希计算近似完美，查找总体上仍然是 O(1)，因为您必须查找短列表的有限次数不会改变整体效率。
关于java - 如何使用 O(1) get() 方法将键映射到 java 中的 hashmap 中的值？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19425010/