java-为什么HashMap的get方法具有FOR循环?

我正在查看Java 7中get的源代码,并且看到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;
    }

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

pjj asked 2020-06-30T00:03:22Z
7个解决方案
62 votes

table[indexFor(hash, table.length)]O(1)的存储桶,其中可能包含我们正在寻找的密钥(如果它在hashCode()中存在)。

但是,每个存储桶可能包含多个条目(具有相同O(1)的不同密钥,或仍映射到相同存储桶的具有不同hashCode()的不同密钥),因此您必须遍历这些条目,直到找到要查找的密钥。

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

Eran answered 2020-06-30T00:03:44Z
18 votes

如果您看到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. 计算密钥{“ vaibhav”}的哈希码。它将生成为118。

  2. 使用索引方法计算索引将为6。

  3. 转到数组的索引6并将第一个元素的键与给定键。 如果两者相等,则返回值,否则检查下一个元素(如果存在)。

  4. 在我们的例子中,它不是节点对象的第一个元素和下一个不为空。

  5. 如果节点的下一个为null,则返回null。

  6. 如果节点的下一个不为null,则遍历第二个元素,并重复过程3,直到找不到密钥或next不为null。

对于此检索过程,将使用for循环。有关更多参考,您可以参考这个

Prashant Patil answered 2020-06-30T00:05:06Z
5 votes

作为记录,在java-8中也存在(因为也有Trees之类的):

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);
        }

基本上(对于垃圾箱不是Tree的情况),迭代整个垃圾箱,直到找到我们正在寻找的条目。

查看此实现,您可能会理解为什么提供良好的哈希值是件好事-并非所有条目都位于同一存储桶中,因此搜索时间更长。

Eugene answered 2020-06-30T00:05:35Z
4 votes

我认为@Eran已经很好地回答了您的查询,并且@Prashant也已经与其他回答过的人进行了很好的尝试,所以让我使用一个示例进行解释,以使概念变得非常清晰。

概念

基本上,@ Eran试图说的是,在给定存储桶(基本上在数组的给定索引中)中,可能有多个条目(除了Entry对象之外),并且当2个或多个键给出不同的哈希值时,这是可能的 但给出相同的索引/存储桶位置。

现在,为了将条目放入哈希图中,这是一个高层次的事情(请仔细阅读,因为我已经花了更多的力气来解释一些好事情,否则这些事情都不属于您的问题):

  • 获取哈希值:这里发生的是针对给定的密钥计算出第一个哈希值(注意这不是equals,使用equals计算出哈希值,并且这样做是为了减轻哈希函数编写不当的风险)。
  • 获取索引:这基本上是数组或换句话说就是存储区的索引。 现在,为什么计算此索引而不是直接使用哈希作为索引是因为减轻了哈希可能超过哈希图大小的风险,所以此索引计算步骤可确保索引始终小于索引的大小。 哈希图。

而且,当出现两个键给出不同的哈希值但索引相同的情况时,这两个键将位于同一存储桶中,这就是FOR循环很重要的原因。

以下是我创建的一个简单示例,向您演示了该概念:

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

注意,在上面的示例中,两个equals对象都给出了不同的哈希值(分别为136和140),但给出了相同的索引0,因此,这两个对象都位于同一存储桶中。 在屏幕截图中,您可以看到两个对象的索引都为equals,并且那里也有一个next,该对象基本上指向第二个对象。


更新:看到一个以上的键进入同一个存储桶的另一种最简单的方法是,创建一个类并重写equals方法以始终返回相同的int值,现在将发生的事情是该类的所有对象都将赋予相同的值 索引/存储桶位置,但由于您尚未覆盖equals方法,因此它们不会被视为相同,因此将在该索引/存储桶位置形成一个列表。

与此类似的另一种情况是,假设您也覆盖了equals方法,并且比较所有对象相等,则索引/存储桶位置将仅存在一个对象,因为所有对象均相等。

hagrawal answered 2020-06-30T00:06:55Z
2 votes

当其他答案解释发生了什么时,OP对这些答案的评论使我认为需要以不同的角度进行解释。

简化的例子

假设您要将10个字符串扔进一个哈希图中:“ A”,“ B”,“ C”,“ Hi”,“ Bye”,“ Yo”,“ Yo-yo”,“ Z”,“ 1” “,” 2“

您将HashMap用作哈希映射,而不是制作自己的哈希映射(不错的选择)。 以下某些内容将不会直接使用bucket实现,而是会从理论和抽象的角度进行处理。

HashMap并不神奇地知道您要向其中添加10个字符串,也不知道您稍后将在其中放入什么字符串。 它必须提供放置任何内容的地方……尽管它知道您将在其中放置100,000个字符串-也许字典中的每个单词。

这么说吧,由于您在使HashMap时选择的构造函数参数是哈希映射具有20个存储桶。 我们将其称为bucketBucket[]

  1. HashMap假设“ A”的哈希值为5。哈希映射现在可以执行bucket

  2. HashMap假设hash(“ B”)=3。因此,bucket

  3. HashMap-哈希(“ C”)= 19-bucket

  4. HashMap现在,这里变得很有趣。 假设您的哈希函数等于hash(“ Hi”)=3。因此,现在哈希映射想要执行bucket我们遇到了问题! Bucket[]是我们放置键“ B”的位置,“ Hi”绝对是与“ B”不同的键...但是它们具有相同的哈希值。 我们发生了碰撞!

由于这种可能性,实际上并未以这种方式实现HashMap。 哈希映射需要具有可以在其中包含多个条目的存储桶。 注意:我不能说多个相同键的项,因为我们不能拥有它,但是它需要具有可以容纳多个不同键的项的存储桶。 我们需要一个既可以容纳“ B”又可以容纳“ Hi”的水桶。

因此,我们不做HashMap,而是让bucket的类型为Bucket[]而不是Entry[]。所以现在我们做bucket[n].add( new Entry(key, value) );

所以我们换成...

HashMap

HashMap

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

因此,由于冲突而存在循环。 不是HashMap的冲突,而是HashMap的冲突。

为什么我们使用如此疯狂的数据结构?

您可能会在此时问:“等等,为什么!?!我们为什么要做这样奇怪的事情?为什么我们要使用这样一个复杂的数据结构?” 这个问题的答案将是...

哈希映射之所以这样工作,是因为由于数学运算的方式,这种特殊设置为我们提供了一些属性。 如果您使用良好的哈希函数来最大程度地减少冲突,并且如果将HashMap的大小设置为具有比您猜测的条目数更多的存储桶,那么您将获得优化的哈希图,这将是插入最快的数据结构 和复杂数据查询。

您的HashMap可能太小

既然您说过,您经常会在调试中看到这个for循环被多个元素迭代,这意味着HashMap可能太小。 如果您对可能放入的东西有合理的猜测,请尝试将大小设置为大于该大小。 请注意,在上面的示例中,我正在插入10个字符串,但是具有一个包含20个存储桶的哈希映射。 具有良好的哈希函数,这将产生很少的冲突。

注意:

注意:上面的示例只是此事的简化,为简洁起见确实有一些捷径。 完整的解释甚至稍微复杂一些,但是您需要回答的所有问题都在这里。

Loduwijk answered 2020-06-30T00:08:57Z
1 votes

哈希表具有存储桶,因为对象的哈希不必唯一。 如果对象的哈希值相等,则意味着对象可能相等。 如果对象的哈希值不同,则对象完全不同。因此,具有相同散列的对象将分组到存储桶中。 for循环用于迭代此存储桶中包含的对象。

实际上,这意味着在这样的哈希表中查找对象的算法复杂性不是恒定的(尽管非常接近),而是介于对数和线性之间。

Nikolay Lebedev answered 2020-06-30T00:09:22Z
0 votes

我想简单地说一下。 O(1)方法具有一个FOR循环,以循环访问属于同一hashCode存储桶的键列表。

当您将O(N)O(N)配对到哈希图中时会发生什么:

  1. 因此,对于每个传递给O(N)O(1),它都会为其计算hashCode。
  2. 如此多的O(1)可以落在同一个O(N)范围内。 现在,HashMap将检查相同的key是否已存在于同一存储桶中。
  3. 在Java 7中,HashMap在列表中维护同一存储桶的所有键。 因此,在插入密钥之前,它将遍历列表以检查是否存在相同的密钥。 这就是为什么有一个FOR循环的原因。

因此,在一般情况下,其时间复杂度:O(1),在最坏的情况下,其时间复杂度是O(N)

vkrishna17 answered 2020-06-30T00:10:05Z
translate from https://stackoverflow.com:/questions/48988291/why-does-the-get-method-of-hashmap-have-a-for-loop