[数据结构与算法]HashMap的put方法在JDK1.7和JDK1.8区别

JDK1.7中HashMap是由 数组 加 链表 实现的
JDK1.8中HashMap是由 数组 加 链表 加 红黑树 实现的

1. 调用put方法

通过put传进来的key，再经过哈希算法得到hashcode，hashcode通过与运算进行数组减1，得出数组下标。

2. 如果此时数组下标位置元素为空

则将key和value封装为Entry对象（JDK1.7中是Entry对象，JDK1.8中是Node对象）并放入当前数组下标的位置，从而key和value存到了HashMap中。

3. 如果此时数组下标位置元素不为空

则要分情况讨论

3.1 如果是JDK1.7

先判断是否需要 扩容 ，
如果要扩容就进行扩容，先扩容后，再把key和value插到链表中去；
如果不用扩容就生成Entry对象，并使用 头插法 添加到当前位置的链表中。

public V put(K key, V value) {
        //当第一次调用put方法时才对table进行初始化
        if (table == EMPTY_TABLE) {
            //创建table
            inflateTable(threshold);
        }
        //由此可见，jdk1.7版本下的HashMap支持Key为null的键值对
        //如果要put元素的key为null，则直接将该元素存储到table[0]链表中
        if (key == null)
            return putForNullKey(value);
        //根据key散列出hash值，里面使用了位运算
        int hash = hash(key);
        //根据hashCode和table.length使用位运算计算出数组的下标值，确保每一个数组下标都要被计算出来
        int i = indexFor(hash, table.length);
        //如果table[i]不等于null
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
          	// 如果 hashCode相等，并且key相等，或者key.equals(k),意思是存在这么一个key,则更新value
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                // 记录e的value
                V oldValue = e.value;
                // value的替换
                e.value = value;
                e.recordAccess(this);
                // 返回记录的value
                return oldValue;
            }
        }
	    //方法执行到此处时，说明原链表中不存在与插入元素key相同的元素，那么，就需要创建一个Entry并插入
        //向HashMap添加一个元素时，modCount需要自增
        modCount++;
        //添加Entry
        addEntry(hash, key, value, i);
        return null;
    }



	void addEntry(int hash, K key, V value, int bucketIndex) {
        //jdk1.7版本HashMap的扩容条件：(size >= threshold) && (null != table[bucketIndex])
        //扩容条件：1、当前HashMap中Entry个数 >= threshold 2、要插入位置的链表不为空
        //jdk1.7和1.8中HashMap的扩容条件有一些差异，需要注意!!!
        if ((size >= threshold) && (null != table[bucketIndex])) {//是否需要扩容
            //扩容，新数组的长度为原数组的2倍
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            //扩容后需要重新计算index
            bucketIndex = indexFor(hash, table.length);
        }
		
        createEntry(hash, key, value, bucketIndex);//再插入
    }



// 头插法
	void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e); //key和value封装为Entry对象
        size++;
    }


    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

3.2 如果是JDK1.8

先判断当前位置上的Node的类型，观察使红黑树Node，还是链表Node

3.2.1 如果是红黑树Node

则将key和value封装为一个红黑树Node并添加到红黑树中去，在这个过程中是需要遍历红黑树，并且判断红黑树中是否存在当前key，如果存在则更新value。

3.2.2 如果是链表Node

则将key和value封装为一个链表Node并通过 尾插法 插入到链表的最后位置去，因为是尾插法，所以需要遍历链表，在遍历链表的过程中会判断是否存在当前的key，如果存在则更新value。
当遍历完链表后不存在当前的key，将新链表Node插入到链表中，插入到链表后，会看当前链表的节点个数，如果大于等于8，那么则会将该链表转成红黑树。
将key和value封装为Node插入到链表或红黑树中后，再判断是否需要进行扩容，如果需要就扩容，如果不需要就介绍PUT方法。

    public V put(K key, V value) {
    	//hash(key)生成一个hashcode
        return putVal(hash(key), key, value, false, true); 
    }



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




final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 步骤1：tab为空则创建
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 步骤2：计算index，并对null做处理 
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            // 步骤3：节点key存在，直接覆盖value
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 步骤4：判断该链为红黑树
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 步骤5：该链为链表
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //链表长度大于8转换为红黑树进行处理
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // key已经存在直接覆盖value
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
           // 步骤6：超过最大容量 就扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

// 第31行treeifyBin方法部分代码
final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        // static final int MIN_TREEIFY_CAPACITY = 64;
        // 如果大于8但是数组容量小于64，就进行扩容
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
    
    }