java基础（HashMap理解）

HashMap其原理是底层是一个table数组+链表，数组的每一项是一个链表头。当然不同的jar包对应的HashMap源码还是有点出入的，以下以安卓的为准。

而存入数组中的元素是Entry，Entry可以理解为一个封装了key和value的对象，我们存进入的其实是一个Entry对象，里面包含了key和value值。

image.png

分析一下put方法：

   public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
         return putForNullKey(value);
        int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
        int i = indexFor(hash, table.length);
        for (HashMapEntry<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;
}

new一个HashMap时候，其实并没有创建一片内存地址，只有在put时候才会去判断table是否为空，如果为空才创建。

 if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }


 private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);

    // Android-changed: Replace usage of Math.min() here because this method is
    // called from the <clinit> of runtime, at which point the native libraries
    // needed by Float.* might not be loaded.
    float thresholdFloat = capacity * loadFactor;
    if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
        thresholdFloat = MAXIMUM_CAPACITY + 1;
    }

    threshold = (int) thresholdFloat;
    table = new HashMapEntry[capacity];
}

put方法里面先判断key值是否为空，如果是空的话，直接返回空值。

if (key == null)
return putForNullKey(value);

如果key不为空的话，通过key计算获取到hash值
然后通过hash值获取到数组中相应的索引，这里要注意一下，如果put多个的话，数组角标i的值是有可能一样的，因为数组存的每一项其实也是一个链表头，如果当期数组已经有put进entry对象的话，那么就通过链表插入值，采用的是头插法。

int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);

获取到数组角标后，通过角标去for循环遍历这个角标下的链表，如果是当前key是之前已经有插入的相同的key，那么就把新值插入之前相同的key中，然后把旧的value return回来

for (HashMapEntry<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;
      }
}

如果key是新的key的话，就新增一个entry，当前的hash值，数值角标，key，value值存进去

ddEntry(hash, key, value, i);

分析一下get方法：

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);
    return null == entry ? null : entry.getValue();
}


final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
    int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
    for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

通过get方法可以看出，调用了getEntry方法，通过key获取到entry对象，如果对象为空，只返回空值，如果对象不为空，则返回相应的value值。

Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();

重点要看下getEntry方法，通过源码可以看通过key获取到了hash值，然后通过for循环遍历相应数组角标下的链表，判断key值一样，并且hash值一样的话，就返回相应的entry对象。

 int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
    for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }

而且遍历是从链表头开始遍历的，这也说明了越后面的put进去的值被找到的时间越短。

关于扩容问题

从源码中可以看出在put里面的addEntry方法进行判断，当数组不为空或者put数量（size）大于16个时候，就会进行扩容，扩容了一倍。

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

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