数组 + 链表 + 红黑树

允许null键/值

public class HashMap  extends AbstractMap  implements Map , 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;
    
    // 当桶(bucket)上的结点数大于这个值时转成红黑树
    static final int TREEIFY_THRESHOLD = 8; 
    
    // 当桶(bucket)上的结点数小于这个值时树转链表
    static final int UNTREEIFY_THRESHOLD = 6;
    
    // 桶中结构转化为红黑树对应的数组的最小大小，如果当前容量小于它，不会将链表转化为红黑树，而是用resize()代替
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    // 存储元素的数组，总是2的幂
    transient Node<k,v>[] table; 
    
    // 存放具体元素的集
    transient Set<map.entry<k,v>> entrySet;
    
    // 元素个数，注意不等于数组长度
    transient int size;
    // 修改次数
    transient int modCount;   
    // 临界值 当实际节点个数超过临界值(容量*填充因子)时，会进行扩容
    int threshold;
    // 填充因子
    final float loadFactor;
    




直接使用key的hashcode()作为hash很容易发生碰撞
综合考虑性能 和散列效果  把高16bit和低16bit进行异或

resize

Initializes or doubles table size. 
because we are using power-of-two expansion, the elements from each bin must either stay at same index, or move with a power of two offset in the new table.
2倍扩容 元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置

扩容时，不需要重新计算hash， hash值高位新增的那个bit是1还是0，是0的话索引不变，是1的话索引变成“原索引+oldCap”, 
直接拆分原链表为高低链表相比先保存数据再寻址追加效率更好。



put大致过程

对key的hashCode()做hash，然后再计算桶的index;
如果没碰撞直接放到桶bucket里；

如果碰撞了，以链表的形式存在buckets里；单链表尾部插入，扩容时保持元素原有顺序避免环

如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，把链表转换成红黑树（若数组容量小于MIN_TREEIFY_CAPACITY，不进行转换而是进行resize操作）
如果节点已经存在则替换old value 
如果表中实际元素个数超过阈值(超过load factor*current capacity)，resize




桶为空 写入不加锁 

no lock when adding to empty bin

else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
}

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                        Node<K,V> c, Node<K,V> v) {
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
    
  
桶的第一个节点 hash值为 MOVED

static final int MOVED     = -1; // hash for forwarding nodes
static final int TREEBIN   = -2; // hash for roots of trees
static final int RESERVED  = -3; // hash for transient reservations
    
else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
            
Helps transfer if a resize is in progress.

正常节点 synchronized 加锁处理
synchronized (f)
桶的第一个节点作为锁对象

链表末尾插入数据 或 红黑树插入数据

 if (binCount != 0) {
                // 当链表长度 超过 8时，转化成红黑树
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
}
            
  



Java8中hash计算 key hashCode  高16位异或低16位 ，保证高低bit都参与hash计算，且不会有太大的开销。
数组大小n总是2的整数次幂，使用位运算计算下标( hash & n-1)
分配内存统一放在resize()中，包括创建后首次put时初始化数组和存放元素个数超过阈值时扩容。
当链表长度>=8， 执行treeifyBin，当桶数量达到64时，将链表转为红黑树，否则，执行resize()。

判断Node是否符合，首先判断哈希值，key是否相等，同一个对象用＝＝比，否则用equals()