Java集合框架之HashMap的底层原理及源码分析

最近一直都在研究Java源码发现自己很多不足也学到很多知识，今天是为了把HashMap给自己总结一下，参考了很多大佬写的文章也自己总结了很多话，如果有错误的地方，望海涵。

（一）走进HashMap

HashMap是最常用的集合之一，是基于哈希表的Map接口实现的。与HashTab的主要区别是不支持同步和允许保存null键和null值。

同时HashMap也是线程不安全的集合，所以当在多线程环境下可能会导致数据不一致的问题，所以HashMap中也运用了modCount统计修改的次数，防止在迭代过程中用户修改数据引起数据不一致的问题。

以前版本的HashMap采用的是数组+链表的形式，而在JDK1.8中 HashMap的实现原理运用了数组+链表+红黑树的结构，当链表长度大于8的时候，HashMap会自动的将链表转换成红黑树从而快速的拿取值，大大的缩短的查找的时间。

JDK1.8中也将HashMap的原有Entry<K,V> 换成了Node<K,V>名字,转换红黑树也采用了ThreeNode的方式。

（二）HashMap的结构

Java集合框架之HashMap的底层原理及源码分析

上面这张很经典的图片我们更能直观的看出哈希表是由数组+链表构成的，在一个长度为16的数组中，每个元素存储的是一个链表的头结点。一般情况下通过元素的哈希值对数组的长度进行取模的。比如上述的哈希表，12%16 = 12,28%16=12,108%16=12 140%16 = 12 所以12 、28、108、140都存储在数组下表为12的位置。

例如我们熟知的哈希冲突也是如此。如果我们对于某个元素进行哈希运算的时候，得到一个存储地址，当我们进行插入的时候，发现这个位置已经被其他元素所占用了，这就是所谓的哈希冲突，也称作哈希碰撞。好的哈希函数会尽可能的保证计算简单和散列地址分布均匀，但是，我们需要清除的是，数组是一块连续固定长度的内存空间，再好的哈希函数也难免不发生小概率的哈希冲突。解决哈希冲突的版本有很多，例如：开放地址发（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法。而HashMap采用的就是链地址法，也就是数组+链表的方式

（三）HashMap的原理

1.局部变量

//默认的初始化容量 必须是2的幂次方 默认16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    //最大存储容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //加载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //默认转换链表的最大长度 如果超过长度则转换成红黑树
    static final int TREEIFY_THRESHOLD = 8;
    //如果红黑树的长度小于这个长度 则将红黑树转换成链表
    static final int UNTREEIFY_THRESHOLD = 6;
    //最大阀值
    static final int MIN_TREEIFY_CAPACITY = 64;
    //Node节点数
    transient int size;
    //执行快速失败原则 修改的次数
    transient int modCount;
    //临界因子  =capacity * loadFactor
    int threshold;
    //Hash表的加载因子
    final float loadFactor;
    //初始化的节点表
    transient Node<K, V>[] table;
    //构建Set集合键
    transient Set<Map.Entry<K, V>> entrySet;

2.构造方法

/**
     * 指定参数构造一个HashMap的构造器
     *
     * @param initialCapacity 初始化容量
     * @param loadFactor      加载因子 用于扩容阀值
     */
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                    initialCapacity);
        //如果初始化容量>与最大存储容量 则初始化容量就等于最大容量
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                    loadFactor);
        this.loadFactor = loadFactor;
        //调用静态方法 计算出临届大小
        this.threshold = tableSizeFor(initialCapacity);
    }

    //如果只传入容量 则按照默认的负载因子0.75
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 默认容量构造一个HashMap 初始化容量为16
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    /**
     * 根据传递进来的Map 构造一个新的HashMap集合
     *
     * @param m
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

我们可以看出在HashMap的初始化中临届大小threshold 调用了tableSizeFor方法来实现，我们看看具体的原理

/**
     * 主要功能是返回一个比给定整数大且最接近的2的幂次方整数，如给定10，返回2的4次方16.
     * HashMap中非常巧妙的运算方法
     *
     * @param cap
     * @return
     */
    static final int tableSizeFor(int cap) {
        //先减去1,然后将最高位1不断右移进行或操作, 最终得到最高位之后全都是1, 最后再加上1, 便得到新容量2^n.
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

改方法的作用是返回一个接近cap容量的2的幂次方整数。

3.HashMap中的键值对的描述

//Node是单向链表 实现Map.Entry接口
    static class Node<K, V> implements Map.Entry<K, V> {
        final int hash; //Hash值
        final K key;//Key值
        V value;//Value值
        Node<K, V> next; //链式结构的下一个节点

        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final String toString() {
            return key + "=" + value;
        }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
                if (Objects.equals(key, e.getKey()) &&
                        Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

3.HashMap中取的操作

/**
     * 实现了Map.get方法 根据Hash值和Key值拿到Node元素
     *
     * @param hash  哈希值
     * @param key   键
     * @return
     */
    final Node<K, V> getNode(int hash, Object key) {
        Node<K, V>[] tab; //初始化一个node数组
        Node<K, V> first, e;//初始化头结点 和是否具有e的几点
        int n;//数组的长度
        K k;//键
        /**
         * 1、hash取余数，为什么不用取模操作呢，而用tab[i = (n - 1) & hash]？
         它通过 (n - 1) & hash来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。
         当length总是2的n次方时， (n - 1) & hash运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。
         */
        if ((tab = table) != null && (n = tab.length) > 0 &&
                (first = tab[(n - 1) & hash]) != null) {
            //总是检查第一个索引位置的第一个Node是否相等 如果不相等则遍历这个索引的链式结构
            if (first.hash == hash && // 总是去检查第一个
                    ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //判断当前链式结构还是有下一个Node节点
            if ((e = first.next) != null) {
                //如果first节点是红黑树结构 则按照红黑树的方式来查找
                if (first instanceof TreeNode)
                    return ((TreeNode<K, V>) first).getTreeNode(hash, key);
                //否则不是红黑树的方式 则按照循环的方式遍历node结点
                do {
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

综上所述，getNode方法的含义就是通过哈希值去对数组的长度进行取模拿到索引，然后根据索引拿到Node[] tab数组中是否具有Node元素，如果有则判断是否相等，如果不相等说明该Node元素存储的可能是一个链表结构，我们需要对其进行判断是否具有下一个Node节点，通过Node.next判断是否具有下一个节点，如果有说明是一个链表，如果是链表我们还要判断是不是红黑树结构，如果是则按照红黑苏的方式拿取，如果不是则进行循环遍历判断，如果无说明该key值在HashMap中不存在node节点。

4.HashMap存的操作

/**
     * 向HashMap存入元素
     *
     * @param key
     * @param value
     * @return
     */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

我们可以看出HashMap内部调用了一个自定义通用的put方法

/**
     * Implements Map.put and related methods
     *
     * @param hash         hash for key
     * @param key          the key
     * @param value        the value to put
     * @param onlyIfAbsent 如果为true  加入你put进入的位置是存在Node节点的则不更改你原先的值
     * @param evict        如果为false代表这张表现在是处于构造的创建模式
     * @return 返回原有的值 如果没有这个key则返回null
     */
    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;
        //tab[i = (n - 1) & hash] 看看这个索引节点是否存在 如果不存在则是创建一个新的节点
        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 {
                //循环判断当前索引所在的链表区域是否具有相等的key
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //如果e不等null 代表存在key
            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;
    }

HashMap存的操作说白了就是先判断是不是有这个Node节点的存在，如果没有则创建一个新的节点，返回一个null，如果有的话则按照循环的方式对HashMaori中的原有值进行覆盖操作，然后返回旧的值。

5.HashMap中扩容操作

自己的语言不好说明，只能借鉴一下大佬们的帖子

jdk1.8 HashMap源码分析（resize函数网址：https://www.cnblogs.com/pzx-java/p/9135341.html

（四）参考文献

HashMap中一个精巧算法 tableSizeFor(int cap) https://www.cnblogs.com/don1911/p/7668101.html

HashMap实现原理及源码分析 https://www.cnblogs.com/chengxiao/p/6059914.html

Java集合框架之HashMap的底层原理及源码分析

继续阅读

java web解决表单重复提交问题

XML: Extensible Markup Language 可扩展标记语言

dom4j获取节点内容

Math类与Random类

GUI__【GUI概述】【布局】【Frame】【事件监听机制】【窗体事件】【按钮】【鼠标事件】【键盘事件】【Dialog对话框】【菜单】GUI概述：布局事件监听机制

2021-08-19 Java方法Java方法

几点有关java以及Python学习

记一次因MySQL编码问题导致的慢查询排查

2021-09-22 Java常用类Java常用类

《JAVA编程思想》第四版学习需要我记住的something –持有对象

《JAVA编程思想》第四版学习需要我记住的something--多态

《JAVA编程思想》第四版学习需要我记住的something –复用类

JAVA语言发展介绍【尚学堂java300集视频学习笔记】Java发展简史Java的核心优势Java各版本的含义Java的特性和优势Java应用程序的运行机制JVM、JRE和JDK区别

JSch的使用与加载.ppk文件的注意事项JSch的使用与加载.ppk文件的注意事项

马士兵_JAVA自学之路

Spring整合JMS(二)——三种消息监听器一、消息监听器MessageListener