hashmap原理

数据结构:数组-链表-红黑树
2^n-1=1111

/**
 * 1） 计算方便,hash&(length-1)==hash%length获取地址,但位运算效率 > 取模运算效率
 * 2） 2^n-1 正好二进制位全是n个1,与hash值做与运算,index结果完全取决于hash值的最后几位。数据分散的就比较均匀,减少碰撞的几率
 *     比如3&(8-1)=3 2&(8-1)=2 不碰撞| 3&(9-1)=0 2&(9-1)=0 碰撞
 * 3） 扩容时不需要像JDK1.7的实现那样重新计算hash。只需要看原来的hash值与新容量2^n-1做位运算左边新增的那个bit是1还是0就好了,
 *     是0的话索引没变，是1的话索引变成"原索引+oldCap"
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 2^4
//加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表转成红黑树的阈值(链表长度)
static final int TREEIFY_THRESHOLD = 8;
//链表转成红黑树的阈值(table长度)  只有大于阈值，table中的链表长度过长才会进行树化,否则只会扩容
static final int MIN_TREEIFY_CAPACITY = 64;
//当前HashMap包含的键值对数量
transient int size;
//capacity*loadFactor
int threshold;
//数组
transient Node<K, V>[] table;

static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    HashMap.Node<K, V> next;

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

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    HashMap.Node<K, V>[] tab;
    HashMap.Node<K, V> p;
    int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;//默认容量初始化。16
    if ((p = tab[i = (n - 1) & hash]) == null)//hash%length获取地址
        tab[i] = newNode(hash, key, value, null);//新增node
    else {//hash碰撞
        HashMap.Node<K, V> e;
        K k;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))//与根node.key一致
            e = p;//替换
        else if (p instanceof java.util.HashMap.TreeNode)//红黑树
            e = ((java.util.HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {//遍历单向链表
                if ((e = p.next) == null) {//找链表的尾部添加节点
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // >8 && table.length<64
                        treeifyBin(tab, hash);//替换成红黑树
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))//替换
                    break;
                p = e;
            }
        }
        if (e != null) { //替换元素
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);//move node to last
            return oldValue;
        }
    }
    //如果当前HashMap的容量超过threshold则进行扩容,<<1
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}