HashMap 源码分析：jkd7 与 jdk8 的区别

尚硅谷JavaSE笔记合集

一、HashMap简介

• 数组初始容量为16
• 扩容为原来的2倍
• 内部存储结构：数组+链表+红黑树(jdk8)，查询速度快
• 添加键值：7上8下
• key和value可以为null

注意：添加到集合中的元素不要再进行key的修改

二、 jdk8 与 jdk7中的不同

1. new HashMap():数组创建为懒汉式，首次调用put()时才创建
2. jdk 8底层的数组是：Node[],而非Entry[]
3. 在jdk8中底层存储结构为：数组+链表+红黑树。
   • 形成链表时，七上八下
   • 链表长度=8 且 数组容量>=64 时，链表转换为红黑树
4. jdk8扩容判断在节点添加完成后进行。jdk7扩容判断是在节点插入之前进行的

三、JDK7源码分析

• 饿汉式创建数组

3.1 相关面试题

1. HashMap什么时候进行扩容呢？

   • 元素个数大于阈值 且 bucket != null
   • 扩容是非常消耗性能的，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

2. 添加元素的流程：

   • 先判断bucket是否为空，为空就直接添加。
   • 不为空就遍历链表，判断key是否存在
   • key存在分为两种情况：
     1. 数组下标为0的链表中存储key=null，覆盖
     2. 对应链表中存在 hash值相同且equals为true的key，覆盖
   • key不存在，添加成功

3.2 源码中的名词

• Entry[]：数据存储的数组
• Capacity：数组容量
• bucket：桶，数组中存放元素的位置。即Entry[i]
• threshold：阈值(容量*加载因子)
• Entry：key-value 节点
• DEFAULT_INITIAL_CAPACITY : 数组默认容量，16
• DEFAULT_LOAD_FACTOR：默认加载因子：0.75

static class Entry<K,V> implements Map.Entry<K,V> {
   final K key;
   V value;
   Entry<K,V> next;
   int hash;
}

3.3 源码解析

//一.调用有参构造器
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//二.创建容量16的数组，计算出阈值12
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)		//MAXIMUM_CAPACITY = 1 << 30
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +loadFactor);
    int capacity = 1;
    //容量总是2的倍数
    while (capacity < initialCapacity)
        capacity <<= 1;
    this.loadFactor = loadFactor;
    //计算阈值：16*0.75=12
    threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    init();
}
//三.存放key-value
public V put(K key, V value) {
	//3.1 判断：key为null
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key); //计算key的hash值
    int i = indexFor(hash, table.length);//通过hash值计算索引位置
    //3.2 判断：hash值相同 && ==或equals为true
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            //覆盖
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    //3.3 
    //情况一：bucket为null：添加成功
    //情况二：hash值不同：添加成功
    //情况三：hash值相同，==或equals为false：添加成功
    addEntry(hash, key, value, i);
    return null;
}
	//3.1 判断：key为null
    private V putForNullKey(V value) {
        //3.1.1 集合中存在：table[0]链表存在key为null的节点，覆盖
        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++;
        //3.1.2 集合中不存在：添加成功
        addEntry(0, null, value, 0);
        return null;
    }
	    //3.1.2
	    //3.3
	    //情况一：bucket为null：添加成功
        //情况二：hash值不同：添加成功
        //情况三：hash值相同，==或equals为false：添加成功
        void addEntry(int hash, K key, V value, int bucketIndex) {
            //3.1.2.1 判断是否需要扩容：（元素个数>阈值 && table[0] != null ）
            if ((size >= threshold) && (null != table[bucketIndex])) {
                //扩容：原来的2倍
                resize(2 * table.length);
                hash = (null != key) ? hash(key) : 0;
                //扩容后重写计算索引下标
                bucketIndex = indexFor(hash, table.length);
            }
            //3.1.2.2 创建节点(key的hash值,key,value,数组索引)
            createEntry(hash, key, value, bucketIndex);
        }
			//3.1.2.1 扩容（最消耗性能）：原来的2倍
    		void resize(int newCapacity) {
                //(1)保存旧的数组
    		    Entry[] oldTable = table;
                //(2)保存旧的容量
    		    int oldCapacity = oldTable.length;
                //(3)旧容量是否==1 << 30：如果是，将阈值设置为整型最大值。返回
    		    if (oldCapacity == MAXIMUM_CAPACITY) {
    		        threshold = Integer.MAX_VALUE;
    		        return;
    		    }
                //(4)创建新容量的空数组
    		    Entry[] newTable = new Entry[newCapacity];
    		    boolean oldAltHashing = useAltHashing;
    		    useAltHashing |= sun.misc.VM.isBooted() &&
    		            (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    		    boolean rehash = oldAltHashing ^ useAltHashing;
                //(5)将元素转移到新数组
    		    transfer(newTable, rehash);
                //(6)保存新数组
    		    table = newTable;
                //(7)计算新阈值
    		    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    		}
				//(5)将元素转移到新数组
    			void transfer(Entry[] newTable, boolean rehash) {
                    //获取新阈值
    			    int newCapacity = newTable.length;
                    //遍历旧数组
    			    for (Entry<K,V> e : table) {
    			        while(null != e) {
                            //保存next指针
    			            Entry<K,V> next = e.next;
                            //是否重写计算hash值
    			            if (rehash) {
    			                e.hash = null == e.key ? 0 : hash(e.key);
    			            }
                            //计算新数组中的索引位置
    			            int i = indexFor(e.hash, newCapacity);
                            //next指向新数组对应索引位置的链表
    			            e.next = newTable[i];
                            //将元素放在新数组的bucket位置
    			            newTable[i] = e;
                            //循环旧数组链表下一元素
    			            e = next;
    			        }
    			    }
    			}
			//3.1.2.2 创建节点：新节点指向旧节点
    		void createEntry(int hash, K key, V value, int bucketIndex) {
    		    Entry<K,V> e = table[bucketIndex];
    		    table[bucketIndex] = new Entry<>(hash, key, value, e);
    		    size++;
    		}

四、JDK8源码分析

• 懒汉式创建数组
  

4.1 相关面试题

1. HashMap什么时候进行扩容和树形化呢？

   • 扩容：元素个数大于阈值（数组容量*0.75）
   • 树形化：链表元素个数=8 且 数组容量>=64
   • 扩容是非常消耗性能的，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

2. 添加元素的流程：

   • 第一次调用先初始数组
   • 先判断bucket是否为空，为空就直接添加。
   • 不为空就遍历链表，判断key是否存在
     1. key已经存在：覆盖
     2. key不存在，添加成功
   • 添加完成后：判断是否需要扩容

4.2 源码中的名词

• Node[]：数据存储的数组
• Capacity：数组容量
• bucket：桶，数组中存放元素的位置。即Node[i]
• threshold：阈值(容量*加载因子)
• Entry：key-value 节点
• DEFAULT_INITIAL_CAPACITY : 数组默认容量，16
• DEFAULT_LOAD_FACTOR：默认加载因子：0.75
• TREEIFY_THRESHOLD(链表长度大于该默认值，转化为红黑树)：8
• MIN_TREEIFY_CAPACITY(数组长度大于该默认值，链表转化为红黑树)：64

static class Node<K,V> implements Map.Entry<K,V> {
   final int hash;
   final K key;
   V value;
   Node<K,V> next;
}

4.3 源码解析

//一.加载因子赋值为0.75
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//二.存放key-value
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
//三.存放key-value
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //3.1 如果数组还未初始则进行默认初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //3.2 如果bucket为null则直接添加
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);	//添加成功
    //3.3 bucket不为null
    else {
        Node<K,V> e; K k;
        //3.3.1 如果bucket位存在key重复则进行覆盖 
        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);
        //3.3.2 bucket位不存在key重复
        else {
            for (int binCount = 0; ; ++binCount) {
                //(1) 链表中不存在key重复：尾指针指向新节点
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //如果7>=8-1 且 数组容量>=64：将链表转换为红黑树，即添加节点后链表元素个数=8
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                //(2) 链表中出现key重复
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //3.3.3 链表中出现key重复：覆盖
        if (e != null) { 
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //3.4 元素个数超过阈值
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
	//3.1 如果数组还未初始则进行默认初始化
	//3.4 元素个数超过阈值：扩容
	final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length; //保存旧容量
        int oldThr = threshold;	//保存旧阈值
        int newCap, newThr = 0; //定义容量和阈值
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //3.4.1 容量和阈值都扩大为原来的2倍
            //newCap=32,newThr=24
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1;
        }
        else if (oldThr > 0)
            newCap = oldThr;
        else {
            newCap = DEFAULT_INITIAL_CAPACITY;	//3.1.1 获取默认容量16
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);	//3.1.2 获取默认阈值16*0.75=12
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        //3.4.2 设置阈值
        threshold = newThr;	//3.1.3 设置阈值
        @SuppressWarnings({"rawtypes","unchecked"})
        //根据新的容量创建新数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        //保存新数组
        table = newTab;
        //3.4.3 将元素转移到新数组
        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;
                        }
                    }
                }
            }
        }
        //3.1.1 返回容量为16的空数组，设置阈值12
        return newTab;
    }