第四章 HashMap 在 Java 中的工作原理

---

最常见的面试问题是HashMap在java中的工作原理，“ HashMap的get和put方法是如何在内部工作的”。在这里，我试图用一个简单的例子来解释内部功能。 HashMap 是java中最常用的Collection之一。我们将先从例子开始，而不是通过理论，以便您更好地理解，然后我们将看到get()和put()函数在java中是如何工作的。

让我们举一个非常简单的例子。我有一个 Country 类，我们将使用 Country 类对象作为键，并将其 大写名称 （字符串）作为值。下面的示例将帮助您理解，这些键值对将如何存储在 hashmap 中。

1.Country.java

package org.arpit.java2blog;
public class Country {

    String name;
    long population;

    public Country(String name, long population) {
        super();
        this.name = name;
        this.population = population;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public long getPopulation() {
        return population;
    }
    public void setPopulation(long population) {
        this.population = population;
    }

    // If length of name in country object is even then return 31(any random number) and if odd then return 95(any random number).
    // This is not a good practice to generate hashcode as below method but I am doing so to give better and easy understanding of hashmap.
    @Override
    public int hashCode() {
        if(this.name.length()%2==0)
            return 31;
        else
            return 95;
    }
    @Override
    public boolean equals(Object obj) {

        Country other = (Country) obj;
        if (name.equalsIgnoreCase((other.name)))
            return true;
        return false;
    }

}

2. HashMapStructure.java（主班）

import java.util.HashMap;
import java.util.Iterator;

public class HashMapStructure {

    /**
     * @author Arpit Mandliya
     */
    public static void main(String[] args) {

        Country india=new Country("India",1000);
        Country japan=new Country("Japan",10000);

        Country france=new Country("France",2000);
        Country russia=new Country("Russia",20000);

        HashMap<Country, String> countryCapitalMap=new HashMap<Country,String>();
        countryCapitalMap.put(india,"Delhi");
        countryCapitalMap.put(japan,"Tokyo");
        countryCapitalMap.put(france,"Paris");
        countryCapitalMap.put(russia,"Moscow");

        Iterator countryCapitalIter=countryCapitalMap.keySet().iterator();//put debug point at this line
        while(countryCapitalIter.hasNext())
        {
            Country countryObj=countryCapitalIter.next();
            String capital=countryCapitalMap.get(countryObj);
            System.out.println(countryObj.getName()+"----"+capital);
        }
    }

}

现在将调试点放在第 24 行，然后右键单击 project->debug as-> java application。程序将在第 24 行停止执行，然后右键单击 countryCapitalMap 然后选择 watch。您将能够看到如下结构。

现在从上图中，您可以观察到以下几点

1. 1. 有一个 名为 table 的Entry [ ] 数组，大小为 16。
   2. 该表存储Entry 类的对象。HashMap 类有一个名为 Entry的内部类 。此条目具有键值作为实例变量。让我们看看入口类Entry Structure的结构。

static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//More code goes here
}

1. 每当我们尝试将任何键值对放入 hashmap 时，Entry 类对象都会被实例化为键值，并且该对象将存储在上面提到的 Entry [ ]（表）中。现在您一定想知道，上面创建的 Entry 对象将存储在哪里（在表中的确切位置）。答案是，通过调用 Hascode() 方法为键计算哈希码。此哈希码用于计算上述 Entry[] 表的索引。
2. 现在，如果您在上图中的数组索引 10 处看到，它有一个名为 HashMap $ Entry的 Entry 对象 。
3. 我们在Hashmap中放置了 4 个键值，但它似乎只有 2 个！！！！这是因为如果两个对象具有相同的哈希码，它们将存储在相同的索引中。现在问题来了怎么办？它以LinkedList的形式 （逻辑上）存储对象 。

那么如何计算上述国家键值对的哈希码。

Hashcode for Japan = 95 as its length is odd.
Hashcode for India =95 as its length is odd
HashCode for Russia=31 as its length is even.
HashCode for France=31 as its length is even.

下图将清楚地解释 LinkedList 的概念。

以现在如果你对 Hashmap 结构有很好的了解，让我们来看看put和get方法。

---

放

让我们看看 put 方法的实现：

/**
         * Associates the specified value with the specified key in this map. If the
         * map previously contained a mapping for the key, the old value is
         * replaced.
         *
         * @param key
         *            key with which the specified value is to be associated
         * @param value
         *            value to be associated with the specified key
         * @return the previous value associated with <tt>key</tt>, or <tt>null</tt>
         *         if there was no mapping for <tt>key</tt>. (A <tt>null</tt> return
         *         can also indicate that the map previously associated
         *         <tt>null</tt> with <tt>key</tt>.)
         */
        public V put(K key, V value) {
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key.hashCode());
            int i = indexFor(hash, table.length);
            for (Entry 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;
                }
            }

            modCount++;
            addEntry(hash, key, value, i);
            return null;
        }

现在让我们一步一步理解上面的代码

1. 检查关键对象是否为空。如果 key 为 null，那么它将存储在 表[ 0 ] 中，因为 null 的哈希码始终为 0。

2. 调用关键对象的hashcode()方法并计算哈希码。此哈希码用于查找用于存储 Entry 对象的数组的索引。有时可能会发生这种情况，这个哈希码函数写得不好，所以 JDK 设计者放置了另一个名为 hash() 的函数，它以上面计算的哈希值作为参数。

3. indexFor ( hash , table .length ) 用于计算表数组中的精确索引，用于存储 Entry 对象。

4. 正如我们在示例中看到的，如果两个关键对象具有相同的哈希码（称为

   冲突

   ），那么它将以链表的形式存储。所以在这里，我们将遍历链表。

   • 如果在我们刚刚计算的那个索引处不存在任何元素，那么它将直接将我们的 Entry 对象放在那个索引处。
   • 如果该索引处存在元素，那么它将迭代直到它获得 Entry -> next 为 null。
   • 如果我们再次放置相同的键怎么办，逻辑上它应该替换旧值。是的，它会这样做。在迭代时，它将通过调用 equals ( ) 方法( key.equals(k) ) 来检查键是否相等，如果此方法返回 true，则它将值对象替换为当前 Entry 的值对象。
   • 如果它没有找到重复键，那么当前 Entry 对象将成为链表中的第一个节点，并且当前 Entry -> next 将成为该索引上现有的第一个节点。

---

得到

让我们看看 get now 的实现：

/**
     * Returns the value to which the specified key is mapped, or {@code null}
     * if this map contains no mapping for the key.
     *
     *
     * More formally, if this map contains a mapping from a key {@code k} to a
     * value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise it returns
     * {@code null}. (There can be at most one such mapping.)
     *
     *
     * A return value of {@code null} does not <i>necessarily</i> indicate that
     * the map contains no mapping for the key; it's also possible that the map
     * explicitly maps the key to {@code null}. The {@link #containsKey
     * containsKey} operation may be used to distinguish these two cases.
     *
     * @see #put(Object, Object)
     */
    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        for (Entry 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;
    }

当您了解 hashmap 的 put 功能时。所以理解 get 功能非常简单。如果您传递任何键以从哈希映射中获取值对象。

1. 检查关键对象是否为空。如果 key 为 null，则返回表[ 0 ]中的 Object 的值 。
2. 调用关键对象的hashcode()方法并计算哈希码。
3. indexFor(hash,table.length) 用于使用生成的哈希码计算表数组中的精确索引，以获取 Entry 对象。
4. 在获取到表数组的索引后，它将遍历linkedlist并通过调用equals()方法检查键是否相等，如果返回true则返回Entry对象的值，否则返回null。

要记住的要点

• HashMap有一个名为 Entry的内部类 ，用于存储键值对。
• 上面的 Entry 对象存储在称为 table 的 Entry 中
• 表的索引在逻辑上称为桶，它存储 LinkedList的第一个元素 。
• Key 对象的hashcode () 用于查找该 Entry 对象的桶。
• 如果两个 key object 具有相同的 hashcode ，它们将进入同一个表数组的桶中。
• 键对象的 equals ( ) 方法用于保证键对象的唯一性。
• 值对象的 equals() 和 hashcode() 方法根本没有使用

---

原文链接：https://codingdict.com/

---