JAVA-HashMap实现原理

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
{

    /**
     * 初始化容量-16
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

    
    static final int MAXIMUM_CAPACITY = 1 << 30;

   
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 一个空的Entry数组
     */
    static final Entry<?,?>[] EMPTY_TABLE = {};

    /**
     * 存储元素的数组，自动扩容
     */
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
　　

 　　/**
    * 键值对
    */
　　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;
        }
    
　　/** * 1.初始化方法 */
　　public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

　　/** * 2.初始化方法 */
　　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();
    }

}

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{

    private static final long serialVersionUID = 3801124242820219131L;

    /**
     * 双重链表的一个第一个元素
     */
    private transient Entry<K,V> header;
　　/** * 3.初始化方法 */
    @Override
    void init() {
        header = new Entry<>(-1, null, null, null);
        header.before = header.after = header;
    }

 　　/**
     * LinkedHashMap 中的entry继承了hashMap中的entry
     */
    private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        Entry<K,V> before, after;
　　　　　/** * 4.初始化方法 */
        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }

}

　　public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
　　　　　　　/**如果这是一个空的table，就进行初始化*/
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
　　　　　/**通过hash算法获取hash值*/
        int hash = hash(key);
　　　　　　/**根据hash值获取在数组中的位置*/
        int i = indexFor(hash, table.length);
　　　　/**获取数组在 i 位置上的链表，并进行循环*/
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
　　　　　　　/**如果hash值相等，并且value值相等，value值会进行覆盖，返回之前的value*/
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
　　　　// 如果在i位置的entry为null，或者value的值不相同，执行addEctity()方法
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

　　void addEntry(int hash, K key, V value, int bucketIndex) {
　　　　// 如果当前数组已经饱和，并且当前位置的entry不是null，数组进行扩容
    　　if ((size >= threshold) && (null != table[bucketIndex])) {
        　　// 扩容操作，原数组需要重新计算在新数组中的位置，并放进去，这里会产生性能损耗
　　　　　　　// 如果我们能已知元素个数，就可以在创建的时候进行生命即可。
　　　　　　　resize(2 * table.length);
        　　hash = (null != key) ? hash(key) : 0;
        　　bucketIndex = indexFor(hash, table.length);
    　　}
　　　　// 创建新的Entry
    　　createEntry(hash, key, value, bucketIndex);
　　}
　　
　　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);
　　}
　　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++;
　　}

　　Entry(int h, K k, V v, Entry<K,V> n) {
    　　value = v;
    　　next = n;
    　　key = k;
    　　hash = h;
　　}

 1 final int hash(Object k) {
 2     　　int h = hashSeed;
 3     　　if (0 != h && k instanceof String) {
 4         　　return sun.misc.Hashing.stringHash32((String) k);
 5     　　}
 6 
 7     　　h ^= k.hashCode();
 8     　　h ^= (h >>> 20) ^ (h >>> 12);
 9     　　return h ^ (h >>> 7) ^ (h >>> 4);
10 　　}