HashMap实现原理（JDK1.8）

如果突然被同行问起HashMap的实现原理，你会不会和我一样词穷。

下面是看完HashMap源码的一些感受和心得。

HashMap是实现了Map接口，而HashMap底层实际为链表+数组，可以看到源码中的Node<K,V>[] table，Node则是Map中的Entry集合的实现。transient修饰则是不参与Java中的序列化。

源码

HashMap源码部分

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
	
    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }
    
     /**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
    transient Node<K,V>[] table;

    /**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     */
    transient Set<Map.Entry<K,V>> entrySet;

}

看到HashMap是继承了一个抽象的Map类，实现了Map接口，Cloneable接口和Jdk序列化接口。

Cloneable接口

Cloneable接口其实只是一个空的接口，没有任何其他信息，通过实现了这个接口，程序就可以认为HashMap具备了clone，而实际其中的clone方法是存在了Object类中，而HashMap实现的clone方法，是因为继承了
AbstractMap。

AbstractMap

1
2
3
4
5
6
7
8
9
10
11
源码部分
public abstract class AbstractMap<K,V> implements Map<K,V> {
/**
 * Sole constructor.  (For invocation by subclass constructors, typically
 * implicit.)
 */
protected AbstractMap() {
}

public abstract Set<Entry<K,V>> entrySet();
}

首先看到AbstractMap，它也是实现了一个Map接口，但是是被声明成了抽象的类，这里就涉及到了抽象的概念，抽象类不能被实例化，但是他的子类被实例化后可以引用他的方法，继承了抽象类，一定需要实现抽象方法，普通方法可以不实现。可以看到该类中abstract只出现了一次，而且是修饰了Set接口。

Map接口

Map接口都知道是键值对，一个键对应一个值，看到Map接口注释时，做着进行了说明：

An object that maps keys to values.  A map cannot contain duplicate keys;
each key can map to at most one value.

意思大概是，
将键映射到值的对象。映射不能包含重复键；
每个键最多只能映射到一个值。

HashMap在初始化，在源码中的构造方法中，有一个默认的initialCapacity，HashMap根据初始容量来进行链表的大小初始化；

而且HashMap中没有出现synchronized来进行方法同步，所以HashMap和HashTable比起来运行速度更快。

且HashMap键可以为null，是因为HashMap在put的时候做了判断
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);