为什么HashMap的get方法有一个FOR循环？

问题描述 投票：46回答：7

我在Java 7中查看HashMap的源代码，我看到put方法将检查是否存在任何条目，如果它存在，那么它将用新值替换旧值。

    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

所以，基本上它意味着给定密钥总是只有一个条目，我也通过调试看到了这一点，但如果我错了，那么请纠正我。

现在，由于给定键只有一个条目，为什么get方法有FOR循环，因为它可以简单地直接返回值？

    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }

我觉得上面的循环是不必要的。如果我错了，请帮助我理解。

java hashmap
7个回答
62
投票

table[indexFor(hash, table.length)]是HashMap的桶，可能包含我们正在寻找的钥匙（如果它存在于Map）。

但是，每个存储桶可能包含多个条目（不同的密钥具有相同的hashCode()，或者具有不同hashCode()的不同密钥仍然映射到同一个存储区），因此您必须迭代这些条目，直到找到您要查找的密钥。

由于每个桶中的预期条目数应该非常小，因此该循环仍然在预期的O(1)时间内执行。

18
投票

如果你看到HashMap的get方法的内部工作。

public V get(Object key)  {
        if (key == null)
           return getForNullKey();
         int hash = hash(key.hashCode());
         for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) 
         {
             Object k;
             if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                 return e.value;
         }
             return null;
}
  • 首先，它获取传递的密钥对象的哈希码，并找到存储桶位置。
  • 如果找到正确的存储桶，则返回值（e.value）
  • 如果未找到匹配项，则返回null。

有时可能存在Hashcode冲突的可能性，并且为了解决此冲突，Hashmap使用equals（），然后将该元素存储到同一存储桶中的LinkedList中。

让我们举个例子：enter image description here

获取密钥vaibahv的数据：map.get（new Key（“vaibhav”））;

脚步：

  1. 计算Key {“vaibhav”}的哈希码。它将生成为118。
  2. 使用索引方法计算索引将为6。
  3. 转到数组的索引6并将第一个元素的键与给定键进行比较。如果两者都是等于则返回值，否则检查下一个元素是否存在。
  4. 在我们的例子中，它不是第一个元素，节点对象的下一个不是null。
  5. 如果node的下一个为null，则返回null。
  6. 如果node的下一个非空遍历到第二个元素并重复进程3，直到找不到key或next不为null。

对于此检索过程，将使用循环。有关更多参考，请参阅this

5
投票

对于记录，在java-8中，这也存在（有点，因为还有TreeNodes）：

if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }

基本上（对于bin不是Tree的情况），迭代整个bin，直到找到我们正在寻找的条目。

看看这个实现，你可能会理解为什么提供一个好的哈希是好的 - 所以不是所有的条目最终都在同一个桶中，因此需要更长的时间来搜索它。

4
投票

我认为@Eran已经很好地回答了你的问题，并且@Prashant也和其他已经回答的人一起做了很好的尝试，所以让我用一个例子来解释它，这样概念就变得非常明确了。

Concepts

基本上@Eran试图在给定的桶中（基本上在数组的给定索引处）说有可能存在多个条目（只有Entry对象），当2个或更多个键给出不同的哈希值时，这是可能的但是给出相同的索引/桶位置。

现在，为了将条目放在hashmap中，这就是在高级别发生的事情（请仔细阅读，因为我已经花了很多时间来解释一些好东西，否则这些东西不是你问题的一部分）：

  • 获取哈希：这里发生的是为给定密钥计算第一个哈希值（请注意，这不是hashCode，哈希是使用hashCode计算的，并且它是为了减少编写糟糕的哈希函数的风险）。
  • 获取索引：这基本上是数组的索引，换句话说就是桶。现在，为什么计算此索引而不是直接使用散列作为索引，是因为为了降低散列可能超过散列映射大小的风险，因此此索引计算步骤确保索引始终小于散列的大小HashMap中。

当一个情况发生时，2个密钥给出不同的散列但是相同的索引，那么这两个密钥将进入同一个桶，这就是FOR循环很重要的原因。

Example

下面是我创建的一个简单示例，用于向您演示这个概念：

public class Person {
    private int id;

    Person(int _id){
        id = _id;
    }

    public int getId() {
        return id;
    }
    public void setId(int id) {
        this.id = id;
    }

    @Override
    public int hashCode() {
        return id;
    }
}

测试类：

import java.util.Map;

public class HashMapHashingTest {
    public static void main(String[] args) {
        Person p1 = new Person(129);
        Person p2 = new Person(133);

        Map<Person, String> hashMap = new MyHashMap<>(2);
        hashMap.put(p1, "p1");
        hashMap.put(p2, "p2");
        System.out.println(hashMap);
    }
}

调试截图（请点击并缩放，因为它看起来很小）：

enter image description here

请注意，在上面的示例中，两个Person对象都给出了不同的哈希值（分别为136和140）但是给出了相同的0索引，因此两个对象都在同一个桶中。在屏幕截图中，您可以看到两个对象都在索引0，并且您还有一个填充的next，它基本上指向第二个对象。

Update: Another easiest way to see that more than one key is going into the same bucket is by creating a class and overriding the hashCode method to always return the same int value, now what would happen is that all the objects of that class would give the same index/bucket location but since you have not overridden the equals method so they would not be considered same and hence will form a list at that index/bucket location.

这里的另一个转折是假设你也覆盖了equals方法并且比较了所有相等的对象，那么只有一个对象将出现在索引/桶位置，因为所有对象都是相等的。

2
投票

虽然其他答案解释了正在发生的事情，OP对这些答案的评论使我认为需要一个不同的解释角度。

简化示例

假设您要将10个字符串放入哈希映射：“A”，“B”，“C”，“Hi”，“Bye”，“Yo”，“Yo-yo”，“Z”，“1 “，”2“

您使用HashMap作为哈希映射而不是制作自己的哈希映射（不错的选择）。下面的一些内容不会直接使用HashMap实现，但会从更理论和抽象的角度来看待它。

HashMap并不神奇地知道你要为它添加10个字符串，也不知道你将在以后添加什么字符串。它必须提供放置任何你可能给它的东西的地方...因为它知道你将要放入100,000个字符串 - 也许是字典中的每个字。

让我们说，因为你在制作new HashMap(n)时选择的构造函数参数，你的哈希映射有20个桶。我们将通过bucket[0]称他们为bucket[19]。

  1. map.put("A", value);让我们说“A”的哈希值是5.哈希映射现在可以做bucket[5] = new Entry("A", value);
  2. map.put("B", value);假设哈希（“B”）= 3.所以，bucket[3] = new Entry("B", value);
  3. map.put("C"), value); - 哈希（“C”）= 19 - bucket[19] = new Entry("C", value);
  4. map.put("Hi", value);现在这里有趣的地方。假设您的哈希函数是哈希（“Hi”）= 3.所以现在哈希映射想要做bucket[3] = new Entry("Hi", value);我们有一个问题！ bucket[3]是我们放置键“B”的地方，而“Hi”肯定是与“B”不同的键......但它们具有相同的散列值。我们碰撞了！

由于这种可能性，HashMap实际上并没有这样实现。哈希映射需要具有可以在其中包含多于1个条目的存储桶。注意：我没有说过多于1个具有相同密钥的条目，因为我们不能拥有它，但它需要具有可以容纳多个不同密钥的条目的桶。我们需要一个可以同时保持“B”和“Hi”的铲斗。

所以，我们不要做bucket[n] = new Entry(key, value);，而是让我们的bucket是Bucket[]而不是Entry[]。所以现在我们做bucket[n].add( new Entry(key, value) );

那么让我们改变......

bucket[3].add("B", value);

和

bucket[3].add("Hi", value);

如您所见，我们现在在同一个桶中有“B”和“Hi”的条目。现在，当我们想让它们退出时，我们需要遍历存储桶中的所有内容，例如，使用for循环。

因此，由于碰撞而存在循环。不是key的碰撞，而是hash(key)的碰撞。

为什么我们使用这种疯狂的数据结构？

你可能会在这一点上问，“等等，什么！？！为什么我们会这样做一个奇怪的事情???为什么我们使用这样一个人为的，错综复杂的数据结构？”这个问题的答案是......

哈希映射的工作方式与此类似，因为由于数学运算的方式，这种特殊的设置为我们提供了这些属性。如果你使用一个很好的哈希函数来最小化冲突，并且如果你调整你的HashMap以获得比你猜中它将在其中的条目数更多的桶，那么你有一个优化的哈希映射，这将是插入的最快的数据结构和复杂数据的查询。

你的HashMap可能太小了

因为你说你经常看到这个for循环在你的调试中被多个元素迭代，这意味着你的HashMap可能太小了。如果您对可能放入的内容有合理的猜测，请尝试将大小设置为大于此值。请注意，在上面的示例中，我插入了10个字符串但是有一个带有20个桶的哈希映射。使用良好的哈希函数，这将产生非常少的冲突。

注意：

注意：上面的例子是对问题的简化，并且为了简洁起见确实采取了一些捷径。完整的解释甚至会稍微复杂一些，但是您回答所提问题时需要知道的一切都在这里。

1
投票

散列表具有存储桶，因为对象的散列不必是唯一的。如果对象的散列相等，则平均值，对象可能是相等的。如果对象的散列不同，则对象完全不同。因此，具有相同散列的对象被分组为桶。 for循环用于迭代此类存储桶中包含的对象。

实际上，这意味着在这样的哈希表中查找对象的算法复杂性不是恒定的（虽然非常接近它），但是在对数和线性之间。

0
投票

我想用简单的话说。 put方法有一个FOR循环来迭代密钥列表，这些密钥列在hashCode的同一桶中。

当put将key-value对进入hashmap时会发生什么：

  1. 因此，对于传递给key的每个HashMap，它将为它计算hashCode。
  2. 如此多的keys可以属于同一个hashCode桶。现在，HashMap将检查相同的存储桶中是否存在相同的key。
  3. 在Java 7中，HashMap在列表中维护同一个存储桶的所有密钥。因此，在插入密钥之前，它将遍历列表以检查是否存在相同的密钥。这就是FOR循环的原因。

所以在平均情况下它的时间复杂度：O(1)，在最坏的情况下，它的时间复杂度是O(N)。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.