9-HashMap底层结构和源码分析

9-HashMap底层结构和源码分析

1-HashMap底层结构说明

  1. HashMap 底层维护的是数组 + 链表 + 红黑树,(jdk 7 版本的 HashMap 底层实现(数组 + 链表),jdk 8 版本底层实现(数组 + 链表 + 红黑树) )。
  2. 数组中存放的是 HashMap 的内部类 Node (实现 Map.Entry<K,V>)数据结点。
  3. 扩容机制
    1. HashMap 底层维护了 Node 类型数组 table ,默认为 null 。
    2. 当创建对象时,将加载因子(loadfactor)初始化为 0.75。
    3. 当添加 Key-Value 时,通过 Key 的哈希值得到在 table 中的索引。然后判断该索引处是否有元素,如果没有元素直接添加。如果该索引处有元素,继续判断该元素的 Key 是否和准备加入的 Key 相等,如果相等,则直接替换 Value ;若果不想等需要判断是树结构还是链表结构,做出相应的处理。如果添加时发现容量不够,则需要扩容。
    4. 首次添加,则需要扩容 table 为 16,临界值 threshold 为 12.
    5. 以后扩容,则为原来容量的2倍,临界值也是一样。
    6. 在 Java 8 中,若一条链表的元素个数超过 TREEIFY_THRESHOLD (默认链表树化的门槛或阈值为 8 ),并且 表 table 的容量 => MIN_TREEIFY_CAPACITY(默认表树化的门槛或阈值为 64),就会进行树化(红黑树)。
  4. HashMap 添加元素底层源码流程分析

  1. HashMap 底层源码分析
// 添加元素的核心方法有 hash、putval、resize、treeifyBin、putTreeVal

// hash
// 根据传入的 Key 对象生成对应的 hash 值
// 若为 null ,则 hash = 0
// 若不为 null ,则先获取 Key 对象的 hashcode 值然后按位异或 hashcode 值的逻辑右移 16 位
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

    // resize
    // 扩容
    final Node<K,V>[] resize() {
        // 获取当前表
        Node<K,V>[] oldTab = table;
        // 获取当前表容量
        // 若当前表为空,说明当前表可能是刚初始化的表,则表的容量也为 0 
        // 若当前表不为空,当前表的容量为 oldTab.length
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 获取当前扩容警戒值
        int oldThr = threshold;
        // 初始化当前表扩容后的新容量、新扩容警戒值
        int newCap, newThr = 0;
        // 判断当前表的容量,若是满足此种情况,说明已经扩过容了,不是初始化状态了
        // 嵌套条件判断
        // (1) 当前表达到或超出最大默认容量,仅需改变当前扩容警戒值,然后返回当前表
        // (2) 按当前表的容量扩容二倍给新表且小于默认最大容量,同时还满足当前表大于默认初始容量(16),
        // 	   则新扩容警戒值变为原来的 2 倍,等待之后进行扩容即可
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        // 判断当前扩容警戒值,满足这一条件说明是通过 HashMap(int) 或者 HashMap(int,float) 初始化的 HashMap
        // 将原本在初始化的 threshold 的值(这就是指定的初始化容量)赋给 newCap 
        // 此时,处理完 newCap 等待后续处理 newThr ,在等待扩容就行了
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        // 此为 HashMap()初始化的 HashSet 进行首次扩容
        // 等待扩容即可
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 此判断是为了处理通过 HashMap(int) 或者 HashMap(int,float) 初始化的 HashMap
        // 的 newThr ,完毕之后等待扩容即可
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        // 将扩容后的扩容警戒值赋给实际对象的扩容警戒值
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        // 根据 newCap 进行扩容
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        // 将扩容后的新表赋给实际对象的表
        table = newTab;
        // 将原有表的数据全部复制到当前新表(上一步已替换)
        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;
                        }
                    }
                }
            }
        }
        return newTab;
    }
    
    // putval
    // 存储数据
    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. 获取当前表,并确认是否为空,说明当前表可能为刚初始化的 HashMap (HashSet)
        // 2. 获取当前表的长度,并确认是否为空,说明当前表可能执行过 clear 方法
        // 满足任一条件后,进行容量处理,并获取处理后的表的长度
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 根据 hash 值计算索引值,并获取索引上的数据元素,然后判断是否为空
        // 若为空,直接将该数据元素插入该索引
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        // 若不为空,开始进行数据比对
        else {
            Node<K,V> e; K k;
            // 先与索引上的数据结点进行比对
            // 以下是相同的数据元素,会直接赋给 e ,然后返回旧值,代表元素重复
            // 从 hash 和 key 或者 equals(可自定义) 来进行判断
            // 相同元素的 hash 值是相同的,所以这个要注意有个哈希值控制方法
            // 不同对象的哈希值一定是不同的,但 String 对象除外,之前介绍过
            // 而且可以通过重写 equals 和 hashCode 来达到对于同一类的对象如何
            // 为相同的可以进行控制
            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 {
                // binCount 是统计链表的元素个数,不包括索引上的数据结点
                for (int binCount = 0; ; ++binCount) {
                    // 查看 p 是否有下一个结点
                    // 若为 null 的话,直接插入元素即可
                    // 然后再来判断链表元素个数是否达到树化条件
                    // 结束循环,之后处理 e 
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // p 的下一个结点不为 null 
                    // 进行元素比对,和之前的方式一样
                    // 元素一致的话就结束循环,之后处理 e 
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 判断 e 是否存在值
            // 若有的话,则说明有重复元素
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 每一次修改都会统计
        ++modCount;
        // 修改成功后就将大小 + 1
        // 然后查看大小是否达到警戒扩容值
        // 这个警戒扩容值是针对存储了多少元素的,不是仅对于表中存储的
        // 数据个数进行是否扩容的,还包括其链表或者红黑树的数据元素的
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        // 返回 null 意味着成功插入
        return null;
    }

// treeifyBin 树化(红黑树)
// 树化需要满足链表个数(8)和表的容量(>= 64)
// 当满足链表个数的话,表容量不满足,就先进行表容量的扩容
// 还有一个重要点就是当红黑树的个数小于等于 6 的话,红黑树又会转成链表,此过程称为剪枝
// 关于剪枝仅是提一下
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }
  1. HashMap 扩容机制实践练习
package map;

import java.util.HashMap;

public class HashMapIncrement {

    @SuppressWarnings({"all"})
    public static void main(String[] args) {

        HashMap hashMap = new HashMap();

        // HashMap ,使用不同的数字(hash 一般也不相同)
        // 所以存储的位置都在内部数组表上,仅模拟内部数组表的扩容
        /*for (int i = 1 ; i <= 100 ; i ++ ) {
            hashMap.put(i,i);
        }*/

        // 使用同一类,并重写 hashCode 方法,使其生成固定的 hash 值
        // 这样就让所有数据放置在同一索引上,仅模拟链表树化
        for (int i = 1; i <= 12 ; i ++) {
            hashMap.put(new Pet01(i),i);
        }
        // 当链表中个数达到 8 (不包括头结点),而此时内部数组表的容量并未达到默认树化的容量 64,需要先进行给内部数组表扩容一次为 32
        // 然后在继续给链表添加元素,又会触发树化,但是内部数组表并未达到要求,只能继续扩容为 64
        // 再次添加元素,又会触发树化,此时内部数组表达到要求,会将该链表进行树化,由 Node 结点变换为 TreeNode 结点
        // 还有个注意点就是在扩容过程中,链表的头结点的索引又发生了改变

        // 注意:给 HashMap 中添加元素时,无论会被添加到哪一个位置(索引上、链表上、红黑树上),在 putVal 中在结尾进行元素个数的增加,
        // 然后与扩容警戒值进行比较是否需要扩容(扩内部数组表)
        // 虽然超过扩容警戒值会进行内部数组表表的扩容,但是扩容警戒值是针对所有元素,包括索引上、链表上、红黑树上的

    }
}

class Pet01 {

    private int n ;

    public Pet01(int n) {
        this.n = n;
    }


    @Override
    public int hashCode() {
        return 100;
    }
}

热门相关:我真的是正派   宠妻入骨:神秘老公有点坏   隐婚101天:唐少宠妻成瘾   巨星小甜妻:前夫,请出局   脑洞大爆炸