hashMap源码分析

先分析hashMap的put方法：当执行put操作时会调用底层的putVal方法，以下是这个方法的分析

执行Put方法时会先判断当前哈希表是否为空，为空则先扩容，然后计算出hash值对应的索引，判断索引位置上的节点是否为空，空则插入这个新节点。否则便要判断节点上的key是不是和原先的key相同，相同则进行更新key操作，key不同的话便是出现哈希冲突了，这时便要看当前数据结构是红黑树还是链表了，链表和红黑树都有不同的对hash冲突的处理方法。

1. 红黑树处理哈希冲突的方式是通过在树中插入新的节点，并根据键的比较结果找到合适的位置进行插入

2. 链表处理哈希冲突的方式相对简单，当发生哈希冲突时，新节点会被插入到哈希表对应桶的链表的末尾。

 /**
     *它接收了四个参数：hash表示键的哈希值，key表示键，value表示值，onlyIfAbsent表示仅在键不存
     * 在时才插入。
     * @return 
     */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; // 声明哈希表数组
    Node<K,V> p; // 声明节点
    int n, i; // 声明数组长度和索引变量
    if ((tab = table) == null || (n = tab.length) == 0) // 判断哈希表是否为空，如果为空则进行扩容
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null) // 根据哈希值计算索引，如果索引位置为空，则在该位置插入新节点
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; // 声明临时节点
        K k; // 声明临时键
        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) {
                if ((e = p.next) == null) { // 如果下一个节点为空，则在链表尾部插入新节点
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // 如果链表长度超过树化阈值，则进行树化操作
                        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); // 调用节点访问后的处理方法
            return oldValue; // 返回旧值
        }
    }
    ++modCount; // 更新修改计数
    if (++size > threshold) // 更新大小并检查是否需要进行扩容
        resize();
    afterNodeInsertion(evict); // 调用节点插入后的处理方法
    return null; // 返回null，表示插入操作完成
}

 然后是对应的扩容方法resize()：

当put时会判断当前元素个数是否大于阈值常量（threshold）* 负载因子常量（loadfactor），大于则将阈值 *2，也就是底层代码中的resize方法进行扩容，负载因子常量默认值为0.75F，所以一般在百分之七十五时便会触发扩容。resize方法会创建一个新的更大的数组，将原有的元素重新计算哈希位置放到新数组中。因为hashmap的大小受限于数组的最大容量，所以阈值的最大值为二的三十次方。然后数据结构，当链表长度达到一定阈值会将链表转化为红黑树