HashMap中put()方法实现原理

突然想解剖HashMap实现原理，Map链表的作者源码如何实现？也可以丰富一下自己的编程思想，也想让读者看见如何观看别人源码的思路和方法。所以心血来潮的我，就来解析HashMap底层原理！

送给读者的话：一个合格的程序员一定要学会观看别人代码。这样子自己的开发也会很多思路和方法。希望国内软件开发越来越好。

首先看类

代码语言：javascript复制

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
{
    .....
}
复制代码

可以看出类继承了AbstractMap抽象泛型类，实现了Map泛型接口和Cloneable、Serializable接口

AbstractMap抽象泛型类

代码语言：javascript复制

public abstract class AbstractMap<K,V> implements Map<K,V> {
    ....
}
复制代码

看出AbstractMap抽象类实现了Map泛型接口

注意：如果抽象类继承了泛型接口，要么改写抽象类为抽象泛型类，要么删除泛型接口中的泛型定义

接着看Map泛型接口

代码语言：javascript复制

import java.util.Collection;
import java.util.Set;

public interface Map<K,V> {

    int size();

    boolean isEmpty();

    boolean containsKey(Object key);

    boolean containsValue(Object value);

    V get(Object key);

    V put(K key, V value);

    V remove(Object key);

    void putAll(Map<? extends K, ? extends V> m);

    void clear();

    Set<K> keySet();

    Collection<V> values();

    Set<Map.Entry<K, V>> entrySet();

    interface Entry<K,V> {

        K getKey();

        V getValue();

        V setValue(V value);

        boolean equals(Object o);

        int hashCode();
    }

    boolean equals(Object o);

    int hashCode();

}
复制代码

可以看出Map泛型接口定义了一些链表的操作，在作者的注释中看见了这样子一句话which was a totally abstract class rather than an interface.（是一个完全抽象的类，而不是接口）那么可以理解作者用这个Map接口为开发链表做了建模，并且在接口中抽象了Entry泛型实体容器，Entry容器用来存储值，将所有的要存入Map链表中的值都看成一个Entry，在抽象类AbstractMap中实现了操作链表的方法，只是初步形成抽象链表Map，并不是实际Map。 AbstractMap抽象类中put方法（之后都以解析put方法为例）

代码语言：javascript复制

 public V put(K key, V value) {
        throw new UnsupportedOperationException();
    }
复制代码

在作者对put方法只是声明了一个UnsupportedOperationException异常，作者对异常解释：@throws UnsupportedOperationException if the put operation is not supported by this map（如果put方法的操作不受这个Map的支持）那么就会抛出该异常。

这里可以看出一个注释是一个良好的编程习惯。

然后最关键的HashMap类

代码语言：javascript复制

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
{
    ......
}
复制代码

参照JDK官方文档说明：

Cloneable类：

一个类实现Cloneable接口，以指示Object.clone()方法，该方法对于该类的实例进行现场复制是合法的。在不实现Cloneable接口的实例上调用对象的克隆方法导致抛出异常CloneNotSupportedException 。按照惯例，实现此接口的类应使用公共方法覆盖Object.clone （受保护）。有关覆盖此方法的详细信息，请参阅Object.clone() 。

注意，此接口不包含clone方法。因此，只能通过实现该接口的事实来克隆对象是不可能的。即使克隆方法被反射地调用，也不能保证它成功。

Serializable类：

类的序列化由实现java.io.Serializable接口的类启用。不实现此接口的类将不会使任何状态序列化或反序列化。可序列化类的所有子类型都是可序列化的。序列化接口没有方法或字段，仅用于标识可串行化的语义。

为了允许序列化不可序列化的子类型，子类型可能承担保存和恢复超类型的公共，受保护和（如果可访问）包字段的状态的责任。子类型可以承担此责任，只有当它扩展的类具有可访问的无参数构造函数来初始化类的状态。如果不是这样，声明一个类Serializable是一个错误。错误将在运行时检测到。

在反序列化期间，非可序列化类的字段将使用该类的public或protected no-arg构造函数进行初始化。对于可序列化的子类，必须可以访问no-arg构造函数。可序列化子类的字段将从流中恢复。

在序列化和反序列化过程中需要特殊处理的类必须采用精确签名的特殊方法。

官方文档中可以看出Map链表的作者使用Cloneable重写里面的方法，使其容器中的Key与传输过来的Key相等并且找到链表中的value。

序列化：

当两个进程在进行远程通信时，彼此可以发送各种类型的数据。java培训无论是何种类型的数据，都会以二进制序列的形式在网络上传送。发送方需要把这个对象转换为字节序列，才能在网络上传送；接收方则需要把字节序列再恢复为对象。

把对象转换为字节序列的过程称为对象的序列化。

把字节序列恢复为对象的过程称为对象的反序列化。

AbstractMap中put方法

代码语言：javascript复制

...
static final Entry<?,?>[] EMPTY_TABLE = {};

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
...
public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    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;
}
复制代码

定义了一个常量Entry枚举类型的泛型数组（HashMap容器）。

所有的存储和获取key/value都是在EMPTY_TABLE中获取

static final Entry[] EMPTY_TABLE = {};

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

进入put方法，执行了一次判断：如果还未初始化，则进行一次初始化。

代码语言：javascript复制

 if (table == EMPTY_TABLE) {
            inflateTable(threshold);
 }
复制代码

看下列代码可以看出，如果key的值为空，则把把value值放到第一个位置

代码语言：javascript复制

    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    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;
复制代码

将Key放入第一个位置方法

代码语言：javascript复制

private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
复制代码

如果Key不为空，将Key转换为hash值，然后根据上一步的hashcode值，以及数组的长度，确定出该key所处的下标值，for循环遍历Entry数组。首先会判断这个数组里面所有的元素是的hash和key的地址是否一样，如果hash和key地址一样，那么再去判断key值是否一样，如果key值也一样，则会覆盖原先key的value。

代码语言：javascript复制

 /**
     * This method is invoked whenever the value in an entry is
     * overwritten by an invocation of put(k,v) for a key k that's already
     * in the HashMap.
     */
    void recordAccess(HashMap<K,V> m) {
    }
复制代码

This method is invoked whenever the value in an entry is overwritten by an invocation of put(k,v) for a key k that's already in the HashMap. 翻译：每当条目中的值被put（k，v）的调用覆盖到HashMap中的键k时，就会调用该方法。

如果不一样，则在Entry数组中插入一个链表。此方法就是在Entry容器中添加一个链表

代码语言：javascript复制

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

hashmap

0 人点赞