HashMap 如何在 Java 中工作

r囧r小猫 2023-10-01 20:49 40阅读 0赞

HashMap 问题在求职面试中很常见。这里有一些关于 HashMaps 如何在 Java 内部工作的深入解释。

HashMap 如何在内部工作已成为几乎所有面试中的热门问题。几乎每个人都知道如何使用 HashMap 或[HashMap 和 Hashtable 之间的区别][HashMap _ Hashtable]。然而，当问题是“HashMap 如何在内部工作？”时，很多人都失败了。

这个问题的答案是它基于散列原理工作，但并不像听起来那么简单。散列是一种使用算法为变量或属性分配唯一代码以实现轻松检索的机制。真正的散列机制在应用于同一对象时应始终返回相同的 hashCode()。

然后是一个问题，“散列如何帮助存储和检索 HashMap 中的值？” 许多人会说该值将存储在存储桶中并使用密钥检索。如果你认为这就是它的工作原理，那你就大错特错了。为了证明这一点，让我们看一下 HashMap 类：

/**
         * The table, resized as necessary. Length MUST Always be a power of two.
         */
         transient Entry[] table;

那么 HashMap 中的 Entry\[\] 有什么用呢？HashMap 将对象存储为 Entry 实例，而不是键和值。

### 什么是入门级？ ###

HashMap 有一个称为Entry Class 的内部类，它保存键和值。还有一个叫做 next 的东西，你稍后会知道。

static class Entry<K,V> implements Map.Entry<K,V> 
     {
         final K key;
         V value;
         Entry<K,V> next;
         final int hash;
         ........
     }

您知道 HashMap 将 Entry 实例存储在数组中，而不是键值对。为了存储一个值，您将使用 HashMap 的 put() 方法。让我们深入研究一下，看看它是如何工作的。

### Put() 方法如何在内部工作？ ###

代码将如下所示：

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<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;
              }
         }
         modCount++;
         addEntry(hash, key, value, i);
         return null;
     }

首先，它检查给定的键是否为空。如果给定的键为空，它将存储在零位置，因为空的哈希码将为零。

`.hashCode()` 然后它通过调用 hashcode 方法将 hashcode 应用于键 。为了获得数组范围内的值， `hash(key.hashCode())` 调用了 ，它对哈希码执行一些移位操作。

该`indexFor()` 方法用于获取存储Entry 对象的确切位置。

然后是最重要的部分——如果两个不同的对象具有相同的哈希码（例如 Aa 和 BB 将具有相同的哈希码），它会存储在同一个桶中吗？为了处理这个问题，让我们考虑一下数据结构中的 LinkedList。它将有一个“next”属性，该属性将始终指向下一个对象，就像 Entry 类中的下一个属性指向下一个对象一样。使用具有相同哈希码的不同对象将彼此相邻放置。

在碰撞的情况下，HashMap 检查下一个属性的值。如果它为空，则在该位置插入 Entry 对象。如果下一个属性不为空，那么它将保持循环运行，直到下一个属性为空，然后将 Entry 对象存储在那里。

### HashMap中如何防止重复键？ ###

众所周知，HashMap 不允许有重复的键，即使我们插入不同值的同一个键时，也只会返回最新的值。

import java.util.HashMap;
    import java.util.Map;
    
    public class HashMapEg {
     public static void main(String[] args) {
      Map map = new HashMap();
      map.put(1, "sam");
      map.put(1, "Ian");
      map.put(1, "Scott");
      map.put(null, "asdf");
    
      System.out.println(map);
    
     }

对于上面的代码，您将获得输出 `{null=asdf, 1=Scott}`，作为值 `sam` ， `Ian` 并将替换为 `Scott`。 那么，这是怎么发生的呢？

LinkedList 中的所有条目对象都将具有相同的哈希码，但 HashMap 使用 `equals()` . 此方法检查相等性，因此如果 `key.equals(k)` 为真，它将替换 Entry 类中的值对象，而不是键。这样，它可以防止插入重复的密钥。

### Get() 方法如何在内部工作？ ###

该方法中应用的几乎相同的逻辑 put() 将用于检索该值。

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

1.  首先，它获取传递的关键对象的哈希码，并找到存储桶位置。
2.  如果找到正确的存储桶，则返回该值。
3.  如果未找到匹配项，则返回 null。

### 如果两个键具有相同的哈希码会发生什么？ ###

此处将使用相同的冲突解决机制。 `key.equals(k)` 将检查直到它为真，如果为真，则返回它的值。

希望这篇文章能澄清一下麻烦的HashMap内部机制。快乐学习！

想学习更多知识与技巧点赞三连，关注私信博主哟

[HashMap _ Hashtable]: https://link.zhihu.com/?target=http%3A//www.javainterviewpoint.com/differences-betwen-hashmap-hashtable/