HashMap是如何工作的

了解HashMap如何内部使用Java语言工作。我假设,如果您对的内部工作HashMap感兴趣,那么您已经了解的基础知识HashMap。但是,如果您不熟悉该概念,请遵循官方的Java文档。在这里,我们将讨论hashmap内部实现分析

目录

    1.单一陈述答案
    2.什么是哈希?
    3。 HashMap中的Entry类
    4。 put()方法如何在内部工作?
    5。 get()方法如何在内部工作
    6.关键说明
    7。 [Update] Java 8中的改进

1.单句答案

如果有人要我描述“ HashMap如何工作?”,我只是回答:“ 基于散列原理 ”。就这么简单。现在,在回答它之前,必须非常确定至少了解哈希的基础知识。对??

2.什么是哈希?

散列是最简单的形式,是一种在其属性上应用任何公式/算法后为任何变量/对象分配唯一代码的方法。

真正的哈希函数必须遵循此规则–

“哈希函数每次将函数应用于相同或相等的对象时,都应返回相同的哈希码。换句话说,两个相等的对象必须一致地产生相同的哈希码。”

Java中的所有对象都继承了hashCode()Object类中定义的函数的默认实现。该函数通常通过将对象的内部地址转换为整数来生成哈希码,从而为所有不同的对象生成不同的哈希码。

阅读更多:在Java中使用hashCode和equals方法

3。 HashMap中的入口类

根据定义,映射为:“将键映射为值的对象”。很容易..对吗?

因此,必须有某种机制HashMap来存储此键值对。答案是肯定的。HashMap有一个嵌套的静态类Entry,如下所示:

入门班
static class Entry<K ,V> implements Map.Entry<K, V>
{
    final K key;
    V value;
    Entry<K ,V> next;
    final int hash;
    ...//More code goes here
}

当然,Entry类已将keyvalue映射存储为属性。key已标记为,final并且还有两个字段:nexthash

在前进的过程中,我们将尝试了解这些领域的需求。

4。 HashMap.put()方法如何在内部工作

在进行put()方法的实现之前,了解Entry类的实例存储在数组中非常重要。HashMap类将此变量定义为:

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

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

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

4.1。put()方法的作用

让我们记下hashmap中put方法的内部工作。

  1. 首先,key检查对象null。如果keynull,则将value存储在table[0]适当位置。因为的哈希码null始终为0。
  2. 然后,在下一步中,通过调用密钥的hashCode()方法使用密钥的哈希码来计算哈希值。该哈希值用于计算数组中用于存储Entry对象的索引。JDK设计人员很好地假设可能有一些编写不佳的hashCode()函数可以返回非常高或很低的哈希码值。为了解决此问题,他们引入了另一个hash()函数,并将对象的哈希码传递给该hash()函数,以使哈希值处于数组索引大小的范围内。
  3. 现在indexFor(hash, table.length)调用函数来计算用于存储Entry对象的精确索引位置。

4.2。如何解决冲突

这是主要部分。现在,我们知道两个不相等的对象可以具有相同的哈希码值,如何将两个不同的对象存储在称为bucket的相同数组位置中。

答案是LinkedList。如果您还记得,Entryclass有一个attribute "next"。此属性始终指向链中的下一个对象。这正是的行为LinkedList

  1. 因此,在发生碰撞的情况下,Entry对象以链接列表形式存储。当一个Entry对象需要存储在特定的索引中时,HashMap检查是否已经有一个条目?如果尚无条目,则将条目对象存储在此位置。如果已经有一个对象位于计算索引上,next则检查其属性。如果为null,则当前条目对象成为链表中的下一个节点。如果next变量不是null,则遵循步骤直到next被评估为null
  2. 如果我们添加另一个value具有与之前输入相同的键的对象该怎么办。从逻辑上讲,它应该替换旧值。怎么做的?好了,在确定Entry对象的索引位置之后,在对计算得出的索引进行Linkedist迭代时,为每个入口对象HashMapkey对象上调用equals方法。链表中的所有这些条目对象将具有相似的哈希码,但equals()方法将测试是否为真。如果key.equals(k)为true,则将两个键都视为同一key对象。这将导致value仅替换入口对象内部的对象。这样,HashMap可以确保keys的唯一性

5。 HashMap.get()方法在内部如何工作?

现在我们知道键值对如何存储在中HashMap。下一个大问题是:在get()方法中传递对象时会发生什么HashMap?如何确定价值对象?

回答我们已经应该知道方法中确定键唯一性的put()方法,同样的逻辑也应用于get()方法中。当哈希图标识出作为参数传递的键对象的完全匹配时,它仅返回存储在当前Entry对象中的值对象。

如果未找到匹配项,则get()方法返回null

get()方法
/**
* Returns the value to which the specified key is mapped, or {@code null}
* if this map contains no mapping for the key.
*
* <p>
* 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.)
*
* </p><p>
* 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<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)))此简单的value对象返回的方法相同。

6.关于HashMap内部工作的主要说明

  1. 存储入口对象的数据结构是一个名为tabletype 的数组Entry
  2. 数组中的特定索引位置称为存储桶,因为它可以保存条目对象的链表的第一个元素。
  3. 重点对象的hashCode()需要计算输入对象的索引位置。
  4. 关键对象的equals()方法用于维护地图中关键点的唯一性。
  5. 值对象hashCode()equals()方法在HashMap中的未使用get()put()方法。
  6. null键的哈希码始终为零,并且此类输入对象始终存储在中的零索引中Entry[]

7。 [更新] Java 8中的HashMap改进

作为JEP 180的工作的一部分,通过使用平衡树而不是链接列表来存储地图条目,HashMap对象的性能得到了改善,其中键中存在很多冲突。基本思想是,一旦哈希存储桶中的项目数超过某个阈值,该存储桶就会从使用条目的链接列表切换到平衡树。在哈希冲突较高的情况下,这会将最坏情况的性能从提高O(n)O(log n)

基本上,当存储桶变得太大时(当前:TREEIFY_THRESHOLD = 8),HashMap用树形图的临时实现动态替换它。这样一来,我们不必感到悲观的O(n),而可以获得更好的O(log n)。

可以遍历和使用TreeNodes的bin(元素或节点),但在填充过多时,还支持更快的查找。但是,由于正常使用中的绝大多数垃圾桶没有人口过多,因此在使用表方法的过程中,可能会延迟检查是否存在树木垃圾桶。

树箱(即,其元素均为TreeNode的箱)主要通过hashCode进行排序,但在绑定的情况下,如果两个元素的名称相同class C implements Comparable<C>,则使用其compareTo()方法进行排序。

由于TreeNode的大小约为常规节点的两倍,因此仅在垃圾箱包含足够的节点时才使用它们。并且当它们变得太小(由于删除或调整大小)时,它们将转换回普通箱(当前:UNTREEIFY_THRESHOLD = 6)。在使用具有良好分布的用户hashCode的用法中,很少使用树箱。

因此,现在我们知道了HashMap在Java 8中如何在内部工作

我希望我已通过本文正确传达了我的想法。如果您发现有任何不同或需要任何帮助,请发表评论。

saigon has written 1445 articles

Leave a Reply