一、HashMap的继承关系

简易类图

HashMap实现Map接口，同时继承了AbstractMap.
Map接口定义了 get put contains 等方法
AbstractMap则实现了一些各种类型的Map都通用的方法。

二、HashMap实现原理

2.1、数据结构

static final Entry<?,?>[] EMPTY_TABLE = {};
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

数据是存储在一个Entry的数组中的，然后Entry是定义成：

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
}

Entry 是一个链表的结构，存有下一个节点的引用。
所以HashMap的数据结构，就是数组+链表。

结构图.png

三、HashMap实现细节

3.1、初始化

 public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: "+ initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
        this.loadFactor = loadFactor;
        threshold = initialCapacity;
        init();
    }

• initialCapacity用来表示初始设置的容量是多大，如果不传的话，则默认为16，最大是2的30次方。
• loadFactor 作为负载因子，当size>容量*loadFactor 时就需要扩容。
• init() 方法是为子类提供的钩子方法，可以在初始化完成，同时还没有对象放进去的时候，完成一些工作。

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

1. 如果是空的Map的话，需要先进行inflate，主要做的是把Entry数组的大小设置为大于初始capacity的最小的2的次方值。
2. 然后如果key为null，则去数组的第0位的链表里去找，找不到则新建一个key为null的Entry。所以可以看出HashMap支持key value 为 null。
3. key不为null,则用一个复杂的算法去计算key的Hash值，然后对数组的大小取模，得到该key对应在数组位置的下表。
4. 遍历这个位置上的链表，找到相同的key,更新value值，并返回旧的value。
5. 如果没有找到相同的key,则新增一个Entry。

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

如果size>阈值 （容量*负载因子）并且这个key所在的位置已经有对象，则进行扩容,容量是之前的两倍。
扩容后把要新增的对象重新计算一下位置，添加到该位置的链表头上。

扩容

 void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

如果之前的容量已经是最大容量了，那么只把阈值调整为最大整数。
否则新建一个容量是之前两倍的数组，把旧数组的对象映射到新的数组上，更新阈值。

3.3 get

final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }
        int hash = (key == null) ? 0 : hash(key);
        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 != null && key.equals(k))))
                return e;
        }
        return null;
    }

get方法比较简单，得到Hash值，计算出在数组中的下标，然后遍历链表。

四、HashMap使用注意

4.1、Key的选取

HashMap的key如果选择是自己定义的对象，要保证对象的HashCode不会变化，如果变化了，有可能导致Put进去的对象，没法get出来。
尽量选择 不可变的对象 最为Key,比如String。

4.2、预估容量

HashMap在初始化时，可以设置容量值，如果预计这个Map的容量很大的话，可以事先设置一个大的容量，避免频繁的扩容,rehash。