HashMap在Java中是如何工作的

你们中的大多数人都会同意HashMap，今天是采访中最喜欢讨论的话题。有时我与同事进行类似的讨论，这确实很有帮助。下面我就和大家进行这样的讨论。 我假设如果您对 HashMap 的内部结构和工作原理感兴趣，那么您已经熟悉HashMap的基础知识，因此我将跳过这一部分。但如果您对此不熟悉，我建议您访问Java Docs站点。在我们继续之前，我强烈建议您查看我的上一篇文章：在 Java 中使用 hashCode 和 equals 方法。 本文内容：

1. 唯一可能的答案。
2. 什么是哈希。
3. 关于班级的一些情况Entry。
4. .是什么意思put()？
5. 该方法如何运作get()。
6. 笔记

唯一可能的答案

如果有人让我解释一下“ HashMap 是如何工作的？” ”，我简单回答：“根据Hashing的原理。” 简单得不能再简单了。要理解这一点并获得扩展答案，您需要确保您了解哈希的基础知识。正确的？

什么是哈希

最简单形式的哈希是一种在将任何公式/算法应用于其属性后将任何变量/对象转换为唯一代码的方法。真正的哈希函数必须遵循以下规则：无论何时，哈希函数应用于相同或相等的对象时都必须返回相同的哈希代码。换句话说，两个相同的对象必须依次返回相同的哈希码。 您可以在这里阅读更多相关信息： Working with hashCode and equals method in Java

关于入门级的一些知识

根据定义，映射是“成对存储值和键的对象”。很简单，对吧？那么，HashMap 中一定存在某种机制来存储成对的 Values 和 Keys 吗？回答 - 是的。HashMap有一个内部类Entry，如下所示：

static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//остальной code тут…
}

当然，该类Entry有一个作为属性存储的键和值。键被标记为final，我们还看到两个附加字段：next和hash。随着文章的进展，我们将尝试理解这些字段的用途。

Java put() 方法的作用是什么？

在我们深入研究该方法的实现之前put()，了解类的实例Entry存储在数组中非常重要。HashMap 类将该变量定义为：

/**
* Размер таблицы, изменяется при необходимости. Длина всегда должна быть
* кратна двум!
*/
    transient Entry[] table;

现在看一下该方法的实现代码put()：

/**
* Связывает определенное meaning с определенным ключом в этой карте(map).
* Если карта перед этим содержала meaning для данного ключа, это meaning
* заменится на новое.
*
* @param key
*            ключ с которым указанное meaning должно быть связано.
* @param value
*            meaning которое должно быть связано с ключом.
* @return вернет предыдущее meaning связанное с key, or null
*         если не было значений связанных с key. (Вернет null
*         так же, если перед этим key был связан со meaningм null)
*/
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;
}

让我们一步一步来弄清楚：

• 首先，我们检查密钥是否存在。如果键不存在 ( null)，则该值将放置在表中的位置 0 处，因为该值的哈希码为null, это – всегда 0。


• 下一步，使用调用 方法获取的密钥的哈希码来计算哈希值hashCode()。该散列值用于计算对象在数组中放置的位置Entry。JDK设计者假设编写得不好的函数hashCode()可能会返回过高或过低的哈希值。为了解决这个问题，他们引入了另一个hash()函数，将一个对象的哈希值传入其中，使哈希值与数组的大小相匹配。


• 现在调用该函数indexFor(hash, table.length)来计算放置对象的确切位置Entry。


• 这是主要部分开始的地方。现在，根据我们知道两个不相等的对象可以具有相等的哈希码，我们提出一个问题：两个不同的对象会被放置在 [bucket] 数组中的相同位置吗？答案是LinkedList。如果您还记得的话，该类Entry有一个属性“ next”。该属性始终指向链中的下一个对象。这正是行为LinkedList。

因此，对象Entry以 形式存储LinkedList。当一个对象Entry被放置在一个特定的位置时，HashMap 会检查该位置是否已经有一个条目。如果没有条目，则将对象放置在该位置。然而，如果该位置已经有一个对象，则检查下一个属性。如果它返回null并且当前对象Entry成为LinkedList. 如果下一个变量不存在null，则对下一个变量重复该过程，直到找到为止null。如果我们放置另一个具有不同值但具有与之前相同的键的对象会怎么样？从逻辑上讲，这应该会导致旧值被替换。这是怎么发生的？一般来说，确定一个对象的位置后Entry，在遍历LinkedList到计算出的位置的同时，HashMap会调用每个对象的关键compare方法Entry。所有这些Entry对象LinkedList可能具有相似的哈希码，但该方法equals()将检查真正的相似性。这只会替换Entry. 因此，HashMap保证了所有键的唯一性。

Java get() 方法如何工作？

现在我们已经了解了键值对是如何存储在HashMap. 下一个大问题是：当对象从 HashMap 传递到方法时会发生什么get()？一个物体的价值是如何决定的？我们应该已经知道答案了，因为方法中确定键唯一性的方式与put()方法应用的逻辑相同get()。一旦HashMap它确定了作为参数传入的对象的键，它就会简单地返回相应的值Entry。如果没有找到匹配项，该方法get()将返回null。我们看一下代码：

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

上面的代码与put()到目前为止的方法类似if (e.hash == hash && ((k = e.key) == key || key.equals(k)))，之后只是返回对象的值。

笔记

• 要存储在对象中的数据结构Entry是一个具有名称table和类型的数组Entry。
• 数组中的每个单独位置称为存储桶，因为它可以包含LinkedList对象的第一个元素Entry。
• hashCode()需要密钥来计算对象的位置Entry。
• equals()key用于检查map( map)中key的唯一性。
• hashCode()和equals()Values 不用于方法get()和set()中HashMap。
• 具有值的键的哈希码null始终为0。并且这样的对象Entry将始终存储在数组的零位置。

我希望我在这篇文章中正确地表达了我的想法。如果您发现错误或有疑问，请在评论中留下。 快乐学习！