解决冲突的Hashmap过程

Question

好的，所以我最近读了很多关于HashMap的文章，我认为有些人让它比实际更令人困惑。我想知道这个过程是否正确。

因此，当您有一个键和值时，例如出生于 1805-02-13 的彼得·狄利克雷，在这种情况下，键将是“彼得·狄利克雷”和值“1805-02-13”。

第一步是在Key上使用哈希函数，即“Peter Dirichlet”。让我们假设哈希函数生成这个值到bucket nr＜code＞5＜/code＞。这意味着在该特定桶中，索引5上，键/值对“Peter Dirichlet”，“1805-02-13”将被存储。

因此，如果我们想检索这些信息，我们使用get（"Peter Dirichlet"）并且将使用散列函数，将找到索引号并找到Key/Vale-对Peter Dirichlet 1805-02-13。

然后我们有碰撞的情况。假设我们现在有“Leo Euler”出生“1783-09-18”。出于某种原因，我们的哈希函数也将珍贵的Leo放在索引号5中。由于Key-Value与Peter Dirichlet不同，因此不会有替换。

现在，在第五个“桶”中，我们有利奥·欧拉和彼得·狄利克雷。如果我们现在想要检索 Leo，我们使用 get（“Leo Euler”），哈希函数会将我们指向第五个桶。“哎呀，”HashMap说，“这是一次碰撞”。然后我们将遍历这些对象，直到找到“Leo Euler”.equals（“Leo Euler”）。所以它会得到key.equals（key）？因此，对于“Peter Dirichlet”，我们不是这样，而是对于Leo并返回键/值对。

这是对HashMap的正确解释吗？

Answer 1

是的，这是正确的解释。.hashcode（）（对于Java，等同于其他编程语言）是不够的。可能会发生碰撞。它将遍历存储桶，并针对每个元素将查询（键）与该键值对的键进行比较。当然，从找到正确键的那一刻起，就会返回其相应的值。如果在存储桶中找不到密钥，我们知道它不在哈希图中。

这就是为什么. equals和. hashcode相互之间有一个契约：如果a.equals（b），那么a的hashcode必须等于b：a.hashcode () == b.hashcode（）。请注意，相反的情况并非如此：拥有相同的hashcode并不意味着对象是等价的。

也许关于您的问题的一个小评论是，HashMap 的内部数组不是由键值对组成，而是由键值对的集合组成。在许多情况下，这要么是 LinkedList 要么是 ArrayList。一些实现使用二叉搜索树，尽管通常它往往没有太大回报：毕竟使用一个好的哈希函数应该减少冲突的数量。