HashMap源码分析

// 其实很简单，主要看length
// &运算，就算h全部为1，&之后都是看length有1的部分
// 那么最大只能是length，所以范围限定在了length里，比 % 运算快多了
// -1为了符合数组0开始
// 这也是扩容为2次幂的原因，配套取模运算
h & (length-1)

1---0001
2---0010
4---0100
8---1000

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

// 总之返回一个大于但最接近number的二次幂
private static int roundUpToPowerOf2(int number) {
    
    // assert number >= 0 : "number must be non-negative";
    return number >= MAXIMUM_CAPACITY 
        
        // -1保证本身不是2次幂，左移保证大于大于当前2次幂，而小于下一个2次幂
        ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

// 返回小于等于的2次幂
public static int highestOneBit(int i) {
    // 多次右移再异或保证最高位的1后面全是1
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    
    // 这里保证除了最高位1以为，其余全部变成0了
    return i - (i >>> 1);
}

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

    // 和最大容量比咯，选择小的。。。
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    
    // 创建哈希表的桶子
    table = new Entry[capacity];
    
    // 是否再哈希
    initHashSeedAsNeeded(capacity);
}

// 正常来说都不用
final boolean initHashSeedAsNeeded(int capacity) {
    
    // 哈希种子，默认0，返回false
    boolean currentAltHashing = hashSeed != 0;
    
    boolean useAltHashing = sun.misc.VM.isBooted() &&
        
        	// 最关键在这里，这里要容量允许的最大值时才为true
        	// Holder里面从JVM环境配置拿看有没有设置自定义的最大容量
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    
    //						false			false
    boolean switching = currentAltHashing ^ useAltHashing;
    
    // false,意思不用再hash
    if (switching) {
        hashSeed = useAltHashing ? sun.misc.Hashing.randomHashSeed(this) : 0;
    }
    return switching;
}

// 注意：根据Key来获取hash值的
final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    // 根据Key的哈希值再和哈希散列
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

static int indexFor(int h, int length) {
    // 取模，必须确保2次幂
    return h & (length-1);
}

public V get(Object key) {
    
    // 当然首先判断是不是空，空就调用专门对NULL的方法，1.7有专门分开
    if (key == null) return getForNullKey();
    
    // 否则调用正常流程
    Entry<K,V> entry = getEntry(key);

    // Entry是从Tree里面继承的，K/V结构
    return null == entry ? null : entry.getValue();
}

// 看看NULL的实现
private V getForNullKey() {
    
    // 如果空表，返回null把
    if (size == 0) {
        return null;
    }
    
    // null 是固定放在0号下标的
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

// 正常流程
final Entry<K,V> getEntry(Object key) {
    
    // 当然也有非空判断
    if (size == 0) {
        return null;
    }

    // 这里的null可能是直接调用，不用通过get的把
    // 比如containsKey:return getEntry(key) != null;
    int hash = (key == null) ? 0 : hash(key);
    
    // 流程才是重点
    // 1.根据Key的哈希值获取桶子下标，然后遍历该桶子上的元素进行判断
    // 2.判断流程：
    // 	2.1 判断元素的哈希值
    // 	2.2 再判断Key是否地址相同（比如String有常量池），或者值相同
    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;
}

// 也是注意流程
// 1.根据Key获取桶下标进行遍历，有相同的就替换
// 2.没有相同则插入
// 	2.2
public V put(K key, V value) {
    
    // 体现懒加载，添加元素才去看看初始化没
    if (table == EMPTY_TABLE) {
        // 前面函数有说明，扩容表
        // 看这里传进入的是阀值，也就是第一次赋值时传进去的容量大小
        inflateTable(threshold);
    }
    
    // 看来为空都有特殊对待
    if (key == null) return putForNullKey(value);
    
    // 获取hash值，以及映射对应的获取桶子下标
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    
    // 链表遍历咯，看是否有相同的，相同则替换
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        
        // 步骤都差不多
        // 第一步比hash，第二步比key地址，第三步比key值
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            
            // 如果已经存在值了，那么替换，返回旧值
            V oldValue = e.value;
            e.value = value;
            
            // 这里是空，主要给LinkedHashMap记录访问顺序的
            e.recordAccess(this);
            
            // 返回旧值
            return oldValue;
        }
    }
 
    // 快速失败机制
    modCount++;
    
    // 没有重复的值，那么就插入
    addEntry(hash, key, value, i);
    return null;
}

// 所以这里存在的就是为了减少运算？？
// 直接从0下标遍历，麻烦
private V putForNullKey(V value) {
    
    // 区别在于直接从0下标遍历，因为NULL只存0下标
    // 也是先遍历，看有没有存在替换，没有就插入
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    
    // 少不了的套路，快速失败
    modCount++;
    
    // 这里才是真正的插入方法
    addEntry(0, null, value, 0);
    return null;
}

// 这里还是添加Entry的判断（判断条件也挺重要的）
void addEntry(int hash, K key, V value, int bucketIndex) {
    
    // 判断阀值，且该桶子上不为空
    // 为空就不扩容，为了节省了一次扩容消耗？？？
    // 这里是1.7的特点，目标下标为空可以直接插入，不进行扩容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        
        // 扩容后面讲，知道这里2倍就是了
        // 扩容完，当然还要记得插入元素
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    // 正真的头插入过程
    createEntry(hash, key, value, bucketIndex);
}

// 1.7 使用头插法，并发会出现死循环，1.8 使用尾插法
// 下面是头插法的流程，慢慢看，可能有点难懂
void createEntry(int hash, K key, V value, int bucketIndex) {
   
    // 先获取桶子指定下标桶的元素
    Entry<K,V> e = table[bucketIndex];
    
    // 然后将桶子上的元素换成将要插入的元素
    // 被顶掉的元素放入，插入元素的next属性上就OK了
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    
    // 最后别忘实际存放的元素数量+1
    size++;
}

// 扩容理由：
// 桶子不够，哈希冲突过多
// 链表过长，影响get遍历效率

// 注意流程：
// 1.建新表，两倍大小
// 2.数据转移
// 	2.1 遍历桶子的同时，遍历桶子上的链表
//	2.2 然后逐个拆分链表元素，再移动新旧表上。（1.8是拼接新旧拼接好后才移动的）
// 3.新表替旧表
void resize(int newCapacity) {
    
    // 旧桶
    Entry[] oldTable = table;
    
    // 旧容量
    int oldCapacity = oldTable.length;
    
    // 如果已经最大了，那么设置阀值，然后什么都不做直接返回
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    // 创建一个新桶，2倍大小的
    Entry[] newTable = new Entry[newCapacity];
    
    // 数据转移，第二个参数新容量决定是否再哈希
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    
    // 新表替旧表
    table = newTable;
    
    // 设置新阀值，其实可以直接*2的
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

void transfer(Entry[] newTable, boolean rehash) {
    
    // 取出新桶容量
    int newCapacity = newTable.length;
    
    // 遍历旧桶
    for (Entry<K,V> e : table) {
        
        // 遍历每个桶子上的链表
        while(null != e) {
            
            // 这里获取了当前遍历的e(Entry)，以及e后一个Entry，就是遍历链表
            Entry<K,V> next = e.next;
            
            // 判断需不需要再哈希
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            
            // 在同一个桶子上，证明hash取模容量之后相同，只是下标相同，不一定hash相同
            // 如果容量变化了，那么取模之后这些同链表的元素就会拆分
            // 这里扩容完：
            // 问题一：链表因为头插法，倒序了
            // 问题二：多线程添加元素扩容，死锁。线程1元素丢失，线程2死循环
            
            // 下面是头插法
            // 获取新下标，因为桶长变了
            int i = indexFor(e.hash, newCapacity);
            
            // 这步和下一步共同组成移到桶子上方，然后再下移
            e.next = newTable[i];
            
            // 然后再往下移动
            newTable[i] = e;
            
            // 这个操作和上面合起来相当于：e = e.next，
            e = next;
        }
    }
}

// 旧哈希值两个线程共有
// 对于新表，两个线程各自会创建一个新表
// 转移到新表的时候，头插法混乱，线程1还没移动完成，线程2就开始移动，二者的链表会形成环，从而死循环

// 有内部类Segment，继承了ReentranLock，且是个小的HashMap，那么每个分段扩容不同大小也就不同了

// 内有两数组，Segment[]、Entry[]

// Segment[]：实现了分段锁机制，往数组插入防止并发要用到CAS

// Entry[]：是我们真正存放元素的

// 意思就是Segment数组里面有个Entry数组，要往Entry放元素，得先获取Segment的锁

// 并发级别，默认16
// 就是总共有多少个锁，分多少段（Segment）,继承ReentrantLock
static final int DEFAULT_CONCURRENCY_LEVEL = 16;

// 最多分段
static final int MAX_SEGMENTS = 1 << 16; // slightly conservative

public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
    
    // 参数校验
    if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
        throw new IllegalArgumentException();
    if (concurrencyLevel > MAX_SEGMENTS) concurrencyLevel = MAX_SEGMENTS;
    
    // Find power-of-two sizes best matching arguments
    int sshift = 0;
    int ssize = 1;
    
    // 找大于等于并发级别的2次幂最小值
    while (ssize < concurrencyLevel) {
        
        // 记录并发级别的二进制位数
        ++sshift;
        ssize <<= 1;
    }
    
    // 这里保留并发级别相关的位数，后面左移用到了
    this.segmentShift = 32 - sshift;
    
    // 这个用来取模找Segment数组下标
    this.segmentMask = ssize - 1;
    
    if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY;
    
    // 这里看每个Segment存多少个
    int c = initialCapacity / ssize;
    
    // 除法的向上取整
    if (c * ssize < initialCapacity) ++c;
    
    // cap最小默认为2，这里是Segment里的HashMap用的容量大小，当然需要2次幂了
    int cap = MIN_SEGMENT_TABLE_CAPACITY;
    while (cap < c) cap <<= 1;
    
    // create segments and segments[0]
    // 创建一个S0的分段，不用每次都计算分段内HashMap的大小了
    Segment<K,V> s0 =
        
        // 加载因子，阀值，table建好放进去给你了
        new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
                         (HashEntry<K,V>[])new HashEntry[cap]);
    Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
    
    // 意思是结构复制
    UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
    this.segments = ss;
}

public V put(K key, V value) {
    Segment<K,V> s;
    if (value == null) throw new NullPointerException();
    int hash = hash(key);
    
    // 根据hash值，获取Segment数组的下标
    int j = (hash >>> segmentShift) & segmentMask;
    
    // 获取对应下标的数组元素，判断是否为空
    if ((s = (Segment<K,V>)UNSAFE.getObject(segments, (j << SSHIFT) + SBASE)) == null)
        // 为空创建小HashMap咯
        s = ensureSegment(j);
    
    return s.put(key, hash, value, false);
}

private Segment<K,V> ensureSegment(int k) {
    
    // 又来一次判断？？
    final Segment<K,V>[] ss = this.segments;
    long u = (k << SSHIFT) + SBASE; // raw offset
    Segment<K,V> seg;
    
    // 看看有没有其他线程已经生成新的了，UNSAF安全类
    if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
        
        // 从原型获取
        Segment<K,V> proto = ss[0]; // use segment 0 as prototype
        int cap = proto.table.length;
        float lf = proto.loadFactor;
        int threshold = (int)(cap * lf);
        HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
        
        // 又判断是不是空，再次检查
        if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
            
            // new了一个Segment对象
            Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
            
            // 判空才自旋CAS添加第一层数组元素
            while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
                
                // 根据CAS操作交换的
                if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
                    break;
            }
        }
    }
    
    // 这里不管是否自己创建的，都会返回一个Segment对象，前面有多次获取最新。。。
    return seg;
}

// Segment插入当然使用继承的ReentranLock
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    
    // Seg对象的put方法会有锁，tryLock不阻塞的，和Lock比
    // tryLock失败，可以用后面的获取锁方法
    HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
    V oldValue;
    
    try {
        
        // 获取该Seg对应的table
        HashEntry<K,V>[] tab = table;
        int index = (tab.length - 1) & hash;
        
        // 获取对应的table下标，返回第一个Entry,后面剧情应该是遍历是否重复，然后头插法
        HashEntry<K,V> first = entryAt(tab, index);
        for (HashEntry<K,V> e = first;;) {
            if (e != null) {
                K k;
                if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
                    oldValue = e.value;
                    if (!onlyIfAbsent) {
                        e.value = value;
                        ++modCount;
                    }
                    break;
                }
                e = e.next;
            }
            else {
                if (node != null)
                    node.setNext(first);
                
                // 头插法
                else
                    node = new HashEntry<K,V>(hash, key, value, first);
                
                // 小HashMap的实际大小
                int c = count + 1;
                
                // 内部扩容机制
                if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                    rehash(node);
                else
                    
                    // 这个set内部用Unsafe方法，否则改的是线程的，不是内存的，可能还是有冲突
                    setEntryAt(tab, index, node);
                ++modCount;
                count = c;
                oldValue = null;
                break;
            }
        }
    } finally {
        unlock();
    }
    return oldValue;
}

private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
    
    // 获取table上对应的Entry
    HashEntry<K,V> first = entryForHash(this, hash);
    HashEntry<K,V> e = first;
    HashEntry<K,V> node = null;
    
    // 重试次数
    int retries = -1; 
    
    while (!tryLock()) {
        HashEntry<K,V> f; // to recheck first below
        
        // 先遍历判断要不要new一个Entry
        if (retries < 0) {
            if (e == null) {
                if (node == null) // speculatively create node
                    node = new HashEntry<K,V>(hash, key, value, null);
                retries = 0;
            }
            else if (key.equals(e.key))
                retries = 0;
            else
                e = e.next;
        }
        
        // 超过重试次数，直接lock（）即可能被阻塞
        else if (++retries > MAX_SCAN_RETRIES) {
            lock();
            break;
        }
        
        // 判断获取的头部，和最新的头部是否相同。这里就是判断别人获取锁时，有否改变结构。
        else if ((retries & 1) == 0 && (f = entryForHash(this, hash)) != first) {
            e = first = f; // re-traverse if entry changed
            retries = -1;
        }
    }
    return node;
}

private void rehash(HashEntry<K,V> node) {

    HashEntry<K,V>[] oldTable = table;
    int oldCapacity = oldTable.length;
    int newCapacity = oldCapacity << 1;
    threshold = (int)(newCapacity * loadFactor);
    HashEntry<K,V>[] newTable = (HashEntry<K,V>[]) new HashEntry[newCapacity];
    int sizeMask = newCapacity - 1;
    
    // 遍历转移咯
    for (int i = 0; i < oldCapacity ; i++) {
        HashEntry<K,V> e = oldTable[i];
        if (e != null) {
            HashEntry<K,V> next = e.next;
            
            // 直接获取了新下标，不用判断是否重哈希
            int idx = e.hash & sizeMask;
            
            // 只有一个元素直接放进桶子
            if (next == null)
                newTable[idx] = e;
            
            // 
            else { // Reuse consecutive sequence at same slot
                HashEntry<K,V> lastRun = e;
                int lastIdx = idx;
                
                // 这个循环为了：记录最后下标相同的元素，转移就一起转移过去了
                // 只是最后的，前面的和后面的就被覆盖了，即没有记录到
                for (HashEntry<K,V> last = next;last != null;last = last.next) {
                    int k = last.hash & sizeMask;
                    if (k != lastIdx) {
                        lastIdx = k;
                        lastRun = last;
                    }
                }
                newTable[lastIdx] = lastRun;
                // Clone remaining nodes
                for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
                    V v = p.value;
                    int h = p.hash;
                    int k = h & sizeMask;
                    HashEntry<K,V> n = newTable[k];
                    newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
                }
            }
        }
    }
    
    // 秉持1.7先扩容再插入元素
    int nodeIndex = node.hash & sizeMask; // add the new node
    node.setNext(newTable[nodeIndex]);
    newTable[nodeIndex] = node;
    table = newTable;
}

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

// 最大容量2^30
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认加载因子0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 转化红黑树界限8
static final int TREEIFY_THRESHOLD = 8;

// 转化成链表界限6，二者不同是为了不要在界限内一直转换
static final int UNTREEIFY_THRESHOLD = 6;

// 当链表需要转换成红黑树时，先先判断数组长度是否<64，是的话不转换红黑树，先扩容
static final int MIN_TREEIFY_CAPACITY = 64;

// Node实现了Entry，之前用的是Entry
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;
    }
}

// 根据key生成， >>>无符号舍弃右边16位，即取高16位
// 因为一般桶长度都在2字节下，
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// n = tab.length
// 一般桶长度都小于2^16即小于65536，即低16位才有效
// 这样与哈希异或的话，只能用到了低16位的
// 那么上面hash自身与自身的高16位异或，就利用到了高16位，更随机
tab[(n - 1) & hash]
// 返回桶下标

// 1.8大于输入参数且最近的2的整数次幂的数，而1.7是小于等于的
// 或，右移运算
// 这样做为了让二进制中，最高位的1后面全置为1，后面加1转换为从1开始计数，不是从0开始了
static final int tableSizeFor(int cap) {
    int n = cap - 1; // 防止已经是2次幂的情况
    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 Set<Map.Entry<K,V>> entrySet;

// 实际存储元素多少
transient int size;

// 记录　hashMap 发生结构性变化的次数
// 调用迭代器的时候，将modCount赋值给迭代器内部
// 如果修改了结构，modCount就会+1
// 那么迭代器迭代一次，就会判断内部的expectedModCount 和 HashMap的是否相同，不同则抛出异常
// 调用Iterator的remove方法即可，内部就是重新赋值迭代器内部的modCount而已
transient int modCount;

// 值等于table.length * loadFactor, size 超过这个值时进行　resize()扩容
int threshold;

// 加载因子
final float loadFactor;

public HashMap(int initialCapacity, float loadFactor) {
    
    // 小于0当然抛出异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    
    // 不能最大2^30
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    
    // 加载因子异常
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    
    // 构造函数只是赋值，没有初始化表，懒加载
    this.loadFactor = loadFactor;
    
    // 前面的2次幂用处，这里就设置了阀值，用于后面的扩容，其实就是赋值容量给阀值
    this.threshold = tableSizeFor(initialCapacity);
    
    // 没有了那个LinkedHashMap的访问顺序初始化函数
}

// 给了初始化大小，加载因子
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}


// 就给了加载因子
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}

public int size() {
    return size;
}

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

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

public V get(Object key) {
    Node<K,V> e;
    
    // 这里返回节点的.value
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

// 这里返回节点
final Node<K,V> getNode(int hash, Object key) {
    
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    
    // 桶不为空，桶大于0，获取桶下标
    if((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null){
        
        // 总是先对比桶上第一个元素，地址相同，或者内容相同（为了省去equal而先对比地址？）
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        
        // 循环遍历链表，第一个元素都是被放弃遍历的吗。。。。
        if ((e = first.next) != null) {
            
            // 查看是否红黑树（难点，重点，考点）
            if (first instanceof TreeNode)
                
                // 强转，然后.getTreeNode方法
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            
            // 这里非红黑树就是链表了，遍历咯，找到就返回，没找到null
            do {
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

public V put(K key, V value) {
    
    // 第三个参数：onlyIfAbsent，第四个：访问顺序用的
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    
    // tab存放表，p存放节点，n表示桶长，i表示哈希值
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 空表时resize
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // 对应桶上为空，直接放桶上
    // tab[i = (n - 1) & hash]，相当于 hash % n
    // 但一般是取最大的素数来取模的
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    
    // 这里就是发生哈希冲突
    else {
        Node<K,V> e; K k;
        
        // 首先判断是否第一个元素，是的话赋值给e，直接进入替换值的阶段，跳过下面两个步骤
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        
        // 进入红黑树处理阶段
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        
        // 链表处理阶段
        else {
            
            // 链表遍历
            for (int binCount = 0; ; ++binCount) {
                
                // 遍历到一个空的，那就尾部插入，这里和1.7的头插法不同
                // 一旦插入成功，那么退出这个循环
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    
                    // 是先插入元素再转换红黑树的
                    // 链长超过8，（那么实际上已经有9个了）转换红黑树，转换过程跳过，后面单独抽出来讲
                    // 特别注意，如果数组长度小于64，不会树化，是直接扩容
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                
                // 这里发现有个重复的元素
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                
                // 节点移动，这里差点看不懂了
                p = e;
            }
        }
        
        // existing mapping for key
        if (e != null) { 
            
            // 旧值
            V oldValue = e.value;
            
            // 新值替换旧值，返回旧值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    
    // put新元素，除了替换属于结构改动
    // 需要快速失败
    ++modCount;
    
    // 桶长超过了 实际元素大小 * 加载因子
    // 再散列
    if (++size > threshold)
        resize();
    
    // LinkedHashMap使用的，这里为空函数
    afterNodeInsertion(evict);
    
    // 原来没有覆盖旧值是返回null
    return null;
}

// 进行树化
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    
    // 表空，数组长度小于64进行扩容，不树化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    
    // 当前选择的桶子不为空
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        
        // 遍历链表，转化成树节点
        do {
            
            // 双向链表prev,next,辅助性属性
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        
        // 树化，节点内部有树化功能
        // 这个树化是从头节点开始，即第一个节点当成根节点，然后根节点还没树化的链表遍历，一个个插入树中
        // 这个过程穿插着平衡
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;

    // next是Node的属性

final Node<K,V>[] resize() {
    
    // 获取旧表
    Node<K,V>[] oldTab = table;
    
    // 获取旧表容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    
    // 旧，新阀值
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    // 旧容量大于0，表示初始化过了
    if (oldCap > 0) {
        
        //如果已经最大容量了，设置阀值整型最大，不必要进行再散列了
        // 返回旧表？
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        
        // 扩容是2倍，和ArrayList的1.5别搞错了
        // 阀值当然也变成2倍了
        else if((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >=DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    
    // 这里和上面对比，说明空表，但旧阀值大于0，说明调用了非空构造函数
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    
    // 这里是容量和阀值都为0，即调用默认构造函数的结果，即要初始化
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    
    // 建立新表
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        
        // 遍历旧数组每一个数组，桶子不为空才转移
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                
                // 只有一个元素，直接插入
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                
                // 如果是树
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    
                    // 遍历链表
                    do {
                        next = e.next;
                        
                        // 哈希值 & 旧容量，原位置
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        
                        // 相对二倍的位置
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    
                    // 这个转移效率高了，容易看懂
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

// 红黑树转移
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this;
    // Relink into lo and hi lists, preserving order
    TreeNode<K,V> loHead = null, loTail = null;
    TreeNode<K,V> hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    
    // 和链表差不多，都是遍历，然后记录拆分位置
    for (TreeNode<K,V> e = b, next; e != null; e = next) {
        next = (TreeNode<K,V>)e.next;
        e.next = null;
        
        // 分别组装新旧位置的部分
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }

    // 然后将这两部分转移过去，如果数量不超过‘6’，那么反树化
    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)
            
            // 对这个组装好的部分，进行反树化
            tab[index] = loHead.untreeify(map);
        else {
            
            // 整个树都移动过去
            tab[index] = loHead;
            
            // 如果另一个位置不为空，即有转移到另一个位置的元素
            // 这样的话，低位就要树化；如果高位为空，整个树都转移过去了，不用再树化，本来就是一个树
            if (hiHead != null)
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

// 是普通的1.8哈希表

// 不同在于，每次修改结构会锁住 链表的头，红黑树的根

// Synchronized(Node / Root)

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        
        // 初始化表
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        
        // 第一个是否为空，Unsafe类直接获取内存值
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            
            // no lock when adding to empty bin
            // CAS操作
            if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))
                break;                  
        }
        
        // MOVDE = -1，表示整个数组在扩容
        else if ((fh = f.hash) == MOVED)
            // 表示当前线程也去帮忙扩容
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            
            // 居然用了synchronized，锁住了头节点,意外
            synchronized (f) {
                
                // 若加锁时，另外线程删除了这个节点，锁没了
                // 那么会再次循环，然后获取最新的头节点
                if (tabAt(tab, i) == f) {
                    
                    // 遍历链表
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                              value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            
            // 树化内部有锁
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    
    // 这里才是真正的扩容，上面的helpTransfer表示帮助扩容
    addCount(1L, binCount);
    return null;
}

private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0)
            // 有可能一直竞争到时间片？？？ 不太可能把
            Thread.yield(); // lost initialization race; just spin
        
        // CAS改变了sc转台
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

private final void addCount(long x, int check) {
    CounterCell[] as; long b, s;
    
    // 逻辑 ||,两个条件有条件执不执行
    if ((as = counterCells) != null || !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        CounterCell a; long v; int m;
        boolean uncontended = true;
        if (as == null || (m = as.length - 1) < 0 ||
            (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
            !(uncontended =
              U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
            fullAddCount(x, uncontended);
            return;
        }
        if (check <= 1)
            return;
        s = sumCount();
    }
    if (check >= 0) {
        Node<K,V>[] tab, nt; int n, sc;
        while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
               (n = tab.length) < MAXIMUM_CAPACITY) {
            int rs = resizeStamp(n);
            if (sc < 0) {
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                    transferIndex <= 0)
                    break;
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                    transfer(tab, nt);
            }
            else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                         (rs << RESIZE_STAMP_SHIFT) + 2))
                transfer(tab, null);
            s = sumCount();
        }
    }
}

public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 :
            (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
            (int)n);
}

final long sumCount() {
    CounterCell[] as = counterCells; CounterCell a;
    long sum = baseCount;
    if (as != null) {
        for (int i = 0; i < as.length; ++i) {
            if ((a = as[i]) != null)
                sum += a.value;
        }
    }
    return sum;
}