HashMap源码分析

import java.util.Map;
import java.util.Objects;

public class HashMap<K, V> {

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    static final int MAXIMUM_CAPACITY = 1 << 30;

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    static final int TREEIFY_THRESHOLD = 8;

    static final int UNTREEIFY_THRESHOLD = 6;

    static final int MIN_TREEIFY_CAPACITY = 64;

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

        Node<K, V> next;

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

        public K getKey() {
            return key;
        }

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

    }


    static final int hash(Object key) {
        int h;
        return key == null ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }


    //   6
    //   ob 0000 0000 0000 0000 0000 0000 0000 0110  -  1
    //   ob 0000 0000 0000 0000 0000 0000 0000 0101  >>>1
    //   ob 0000 0000 0000 0000 0000 0000 0000 0010  |
    //   ob 0000 0000 0000 0000 0000 0000 0000 0111

    //   ob 0000 0000 0000 0000 0000 0000 0000 0001  >>>2

    //   ob 0000 0000 0000 0000 0000 0000 0000 0111  + 1

    //   ob 0000 0000 0000 0000 0000 0000 0000 1000  = 8
    static final int tableSizeFor(int capacity) {
        int n = capacity - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }


    transient Node<K, V>[] table;

    transient int size;

    transient int modCount;

    int threshold;

    final float loadFactor;

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


    public HashMap(int initCapacity) {
        this(initCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }


    public int size() {
        return this.size;
    }


    public boolean isEmpty() {
        return this.size == 0;
    }

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    private V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {

        Node<K, V>[] tab;
        Node<K, V> p;
        int n, i;

        //如果table还没有初始化
        if ((tab = table) == null || (n = tab.length) == 0) {
            n = (tab = resize()).length;
        }
        //如果table[index] == null，此位置还没有元素
        if ((p = tab[i = (n - 1) & hash]) == null) {
            tab[i] = newNode(hash, key, value, null);
        } else {
            //如果不为空，那么该index处产生了hash冲突
            Node<K, V> e;
            K k;
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
                //hash 以及 key都相等
                e = p;
            } else if (p instanceof TreeNode) {
                //如果该位置是treeNode 则插入treeNode
                e = ((TreeNode) p).putTreeVal(this, tab, hash, key, value);
            } else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        //下一个链表节点为null的话，新增一个链表节点
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) {
                            //该条链表是否需要树化
                            treeifyBin(tab, hash);
                        }
                        break;
                    }
                    //判断是否与下一个节点hash相等以及是否是同一个key
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                        break;
                    }
                    //将p重新赋值为下一个节点 进入下一次循环
                    p = e;
                }
            }
            if (e != null) {
                V oldValue = e.value;
                if(!onlyIfAbsent || oldValue == null){
                    e.value = value;
                }
                //子类去实现
                afterNodeAccess(e);
                return oldValue;
            }
        }

        ++modCount;
        if (++size > threshold) {
            resize();
        }
        return null;
    }

    //树化操作
    private void treeifyBin(Node<K, V>[] tab, int hash) {

    }

    private Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {
        return new Node<>(hash, key, value, next);
    }

    private Node<K, V>[] resize() {
        return new Node[0];
    }


    static final class TreeNode<K, V> extends Node<K, V> {
        Node<K, V> before, after;

        TreeNode<K, V> parent;

        TreeNode<K, V> left;
        TreeNode<K, V> right;
        TreeNode<K, V> prev;
        boolean red;

        TreeNode(int hash, K key, V val, Node<K, V> next) {
            super(hash, key, val, next);
        }

        public Node<K, V> putTreeVal(HashMap<K, V> map, Node<K, V>[] tab, int h, K k, V v) {


            return null;
        }
    }


    void afterNodeAccess(Node<K,V> p) { }


}