文章9-HashMap底层结构和源码分析分享给大家，欢迎收藏Java资料网，专注分享技术知识

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 添加元素底层源码流程分析

5. 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);
        }
    }

6. 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;
    }
}

文章来源:https://www.cnblogs.com/Yao-happy/p/18299445
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！