JDK1.7的HashMap的put(key, value)源码剖析

HashMap的put操作源码解析

HashMap的put操作源码解析

1、官方文档

1.1、继承结构

java.lang.Object

  java.util.AbstractMap<K,V>

      java.util.HashMap<K,V>

1.2、类型参数：

K - 此映射所维护的键的类型

V - 所映射值的类型

2、put(key, value)

HashMap是一种以键——值对的形式来存储数据的数据结构。HashMap允许使用 null 值和 null 键，它并不能保证你存放数据和取出的顺序是一致的。

接下来就以下面的代码来看一下put是怎么将数据存放到map中的。

public class HashMapTest {

    public static void main(String[] args) {

        Map<String, Object> map = new HashMap<String, Object>();

        map.put(null, "map-value");

        map.put(map-key", "map-value");

        System.out.println(map);

    }

}

2.1、重点源码部分截取

在map.put()这里打个断点F5(我用的eclipse)跟踪进去。我们就会进到put方法中：

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;

}

这里的EMPTY_TABLE是HashMap的一个静态常量，是一个Entry数组，默认值是空数组，table是HashMap的一个属性且其默认值就是EMPTY_TABLE，这个table也就是我们数据存放的地方，至此为止可以知道，HashMap其实是一个数组，但它又不是一个纯粹的数组。下面会进行解释。

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

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

而这个Entry其实是HashMap的一个内部类，定义如下(仅截取部分代码)，记住这个类，记住这个构造方法：它在new Entry的时候接收了一个Entry对象，并将自己的next指向了传入的Entry对象形成一个链表，其自身是表头。

static class Entry<K,V> implements Map.Entry<K,V> {

        final K key;

        V value;

        Entry<K,V> next;

        int hash;

        Entry(int h, K k, V v, Entry<K,V> n) {

            value = v;

            next = n;

            key = k;

            hash = h;

        }

}

从上面我们可以看出来这个Entry其实是一个链表，它存放了 key 和 value 并且还有一个指向下一个节点的引用 Entry next，剩下的这个 hash 就是 key 的哈希值。

现在我们可以捋一捋HashMap的结构了。首先HashMap是一个Entry数组，而这个Entry是一个单向链表，我们大致可以将其结构画成如下图所示：

JDK1.7的HashMap的put(key, value)源码剖析-LMLPHP

2.2、put(key, value)源码分析

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;

}

因为我们在实例化HashMap的时候使用的是无参构造方法，所以第一次 put 数据的时候table为空

if (table == EMPTY_TABLE) {

    inflateTable(threshold);

}

上面这段代码会被执行，inflateTable(threshold) 会将table初始化为一个长度为16的Entry数组。

它会对我们的key进行空判断，如果是空就会执行下面的代码：

if (key == null)

        return putForNullKey(value);

putForNullKey(value) 的实现如下：

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;

        }

    }

    modCount++;

    addEntry(0, null, value, 0);

    return null;

}

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

}

void createEntry(int hash, K key, V value, int bucketIndex) {

    Entry<K,V> e = table[bucketIndex];

    table[bucketIndex] = new Entry<>(hash, key, value, e);

    size++;

}

2.2.1 、`key`为`null`的情况

从上面可以看出来，如果key为null的话，它会从table中取出下标为0也就是第一个元素，没忘记的话我们应该还知道它一个Entry，是一个链表，如果这个元素不是null，那么就会遍历这个链表，并判断当前这个Entry节点对象的key是不是null。

如果是null(key相同了)：使用oldValue来存放当前这个Entry节点对象的value，然后将我们新的值(map-value)赋给当前节点，再将原值oldValue返回回去。
如果遍历完链表的所有节点都没有找到key为null的节点就会调用addEntry(0, null, value, 0)，这个方法前面的if(){***}这块代码是判断当前table是否要进行扩容。这里只做简单讲述。

size是当前table存放的Entry链表的个数，拿我上面画的那个HapshMap结构来看就是4。

如果我们实例化HashMap的时候没有给大小那么：threshold = loadFactor(负载因子默认为0.75f) * DEFAULT_INITIAL_CAPACITY(HashMap默认大小也就是table长度为16)，所以threshold = 12。

如果我们给了大小为initialCapacity，那么负载因子还是默认的0.75f，但是threshold不需要算了，值就是initialCapacity。如果我们同时给了HashMap的大小initialCapacity和负载因子loadFactor，那么HashMap就使用我们给定的负载因子值作为新的负载因子，给定的HashMap大小作为threshold。ok第一个条件结束。

null != table[bucketIndex]就很好理解了，就是我当前这个节点要存放的位置是空的。

满足上面两个条件，HashMap就会进行扩容，扩容后的大小为扩容前的2倍，然后对key重新计算它的hash值以及数组下标。
继续put内容，从上面源码我们可以知道key为null的情况下它的hash值是0，至于bucketIndex的计算是这样的h & (length-1)，也是将hash值与table的长度按位相与值也是。至此也就是确定了key为null的这个节点将存放在table的第一个位置上。然后就会调用createEntry(0, null, "map-value", 0);
在createEntry(int hash, K key, V value, int bucketIndex)这个方法里首先拿到table中下标为bucketIndex的链表的表头：Entry<K,V> e = table[bucketIndex];然后再用Entry对象的构造方法new一个Entry将我们的hash值，key，value，链表的表头作为参数传入：table[bucketIndex] = new Entry<>(hash, key, value, e);就这样我们的这个新节点就放在了原来的表头的前面作为新的表头了。没看懂的再回到上面看一下Entry的构造方法，我有重点标注的。

2.2.2、 `key`不为`null`的情况

源码依旧拿下来

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;

}

首先说一下hash值：对于相同的key它们的hash值是相同的。但是hash值相同，它们的key却不一定是相同的，这就是哈希碰撞。
key不为null的话它会根据key算出这个key对就的hash值以及它的bucketIndex，然后拿到table中下标为bucketIndex的这个Entry链表，然后遍历这个链表，判断当前节点的hash其实也就是当前节点的key的hash是否等于我们传入的map-key的hash，然后判断当前节点的key是否与我们传入的key相同。

如果以上条件都满足了，那么就是key相同了，就会跟Key为null的分析中的第一条一样将新值覆盖旧值，并将旧值返回回去。

如果遍历完这个链表以上条件没有得到满足，那么就会跟key为null的分析中的第四条一样，获得table下标为i的链表的表头e，然后将我们的map-key, map-value, hash以及表头e作为参数new一个新的Entry对象并将它的next指向原来的表头e，它也就变成了新的表头了。

3、完结

最怕你的能力配不上你的野心。

table