JAVA HashMap 原理

本文主要是介绍JAVA HashMap 原理，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

底层实现：数组+链表(链表长度大于8转换为红黑树)

HashMap 是存储键值对的集合，每个键值对存储在一个Node<K,V>。HashMap的主干是一个名为table的Node数组

每个键值对key的hash值对应数组下标，遇到hash冲突时，采用链地址法

JDK1.7:通过键值对Entry<K,V>中的next属性来把hash冲突的所有Entry连接起来，因此每次都要遍历链表才能得到所要找的键值对，增删改查操作的时间复杂度为O（n）

JDK1.8: 当链表长度大于8时，会将链表转化为一棵红黑树，增删改查操作的时间复杂度为O（log（n））。

 源码

键值对

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

key和hash属性为final的原因：在Java中，如果一个对象的属性值在业务逻辑上不需要改变，就将其声明为final，这样保证了安全性。

而且在这里若是让key或者hash发生改变，会导致该键值对无法被查找到

属性

默认初始化容量为 16，扩容容量必须是 2 的幂次方、最大容量为 1<< 30 、默认加载因子为 0.75。

transient int size;//实际键值对个数
int threshold;//阈值，超过到这个值后就要进行扩容
transient int modCount;//修改计数器，用于快速失败
final float loadFactor;//加载因子

threshold = table.length （默认值为16）* loadFactor（默认值为0.75） 这两个值可以在构造时自行输入。length值需要自己根据业务需求输入，输入合适的值能显著减少扩容次数 。

而loadFactor值在一般情况下0.75都是有不错的效率的。但是若是对时间效率要求很高，对空间效率要求很低，可以减小loadFactor值，反之增大loadFactor值，可以大于1。

modCount用于记录对象的改变结构的次数（不包含修改value的值的操作），这是用于在多线程情况下，当多个线程并发修改HashMap的结构时，多个线程都会去修改modCount这个成员变量，

而每个线程内部维护着一个局部变量的修改技术器，当线程做完修改操作后发现成员变量的modCount与局部变量不一致时，就抛出ConcurrentModificationException，这是fail-fast机制，

Java中如ArrayList等线程不安全的集合都有这个机制。
求key的hash值

（1）计算对象自己的hashCode()值
（2）计算上步得到的值高16位于低16位相与。否则在容器length较小时，无法发挥高位的作用，这样能使 得hash分布更加均匀，减少冲突。

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//第一步与第二步
    }

（3）定位操作，对上步计算得到hash值进行取模操作（这里用的是位运算，有个小技巧）

index = (n - 1) & hash//在这里等价于hash%n

HashMap规定length一定是2^N，N可为任意整数，如果自定义的length长度不为2的整数次幂，那么就会自动取成大于设定值的最接近的2^N的值。

在这个前提下，我们再来看这个二进制与运算。如在n=16的情况下，15的二进制码为 1111，不管是什么数，和11111做&操作，低五位不会变，而高位全部为0，即与hash%n的结果是一样的。

而且在计算机中，位运算的效率是最高的，因此这样会大大提升查询效率。

扩容

if (++size > threshold)//当完成put操作后，发现新的size大于了阈值
            resize();

newThr = oldThr << 1; // double threshold

每次扩容为之前的两倍：在扩容之后就要把具体键值对搬迁到新的table数组中。

put

    /**
     * 添加键值对到HashMap中
     *
     * @param hash         key所对应的哈希值
     * @param key          键值对中的键（key）
     * @param value        键值对中的值（value）
     * @param onlyIfAbsent 如果存在相同的值，是否替换已有的值，true表示替换，false表示不替换
     * @param evict        表是否在创建模式，如果为false，则表是在创建模式
     * @return 返回旧值或者null
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        HashMap.Node<K, V>[] tab;// 临时变量，用来临时存放链表数组
        HashMap.Node<K, V> p;
        int n, i;
        // 检查链表数组table是否为空，table为null或者table数组的长度为0都表示为空
        if ((tab = table) == null || (n = tab.length) == 0)
            // 如果为空则初始化，并扩容，然后返回新链表数组的长度，将长度赋值给变量n
            // resize()方法就是初始化并扩容，该方法具体请参考：
            n = (tab = resize()).length;
        // (n-1)&hash这条语句就是JDK1.7中HashMap源码中的indexFor()方法的功能，即得到该对象存放在数组中的具体位置（下标）
        // 判断该位置的元素是否为null，即是否存在元素，如果存在则表示已经发生哈希冲突，如果不存在，则添加元素结点
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 表示不存在元素的情况
            // 则新添加一个元素到链表数组的对应下标位置，该结点也是链表的链头
            tab[i] = newNode(hash, key, value, null);
        else {
            // 表示存在元素的情况
            // 则发生了哈希冲突，下面的代码则是尝试解决冲突问题
            HashMap.Node<K, V> e;
            K k;
            // 判断待添加元素的hash值和key值是否同已经存在（冲突）的元素的hash值和key值同时相等
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                // 如果相等，则表示两个元素相互重复了，那么使用变量e来临时存储这个重复元素
                e = p;
                // 如果不相等，表示没有重复，并且判断结点类型是否是红黑树类型
            else if (p instanceof HashMap.TreeNode)
                // 那么就将该键值对存储到红黑树中
                e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
                // 如果不相等，且结点类型不是红黑树类型，那么就是链表，即采用拉链法解决冲突
            else {
                // 遍历链表中所有结点，这是一个死循环，需要通过break跳出循环
                for (int binCount = 0; ; ++binCount) {
                    // 如果p的下一个结点为null，则p是链表中的最后一个结点
                    if ((e = p.next) == null) {
                        // 则将键值对添加到最后一个结点的后面
                        p.next = newNode(hash, key, value, null);
                        // 同时binCount也是一个计数器，统计该链表已经有几个元素了
                        // TREEIFY_THRESHOLD是常量，表示阈值，默认值为8
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // 但链表中元素个数超过了阈值，则将链表转换成红黑树
                            treeifyBin(tab, hash);
                        // 跳出循环
                        break;
                    }
                    // 判断待添加元素的hash值和key值是否同链表中已有元素的hash值和key值同时相等
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                        // 如果相等，则表示已经存在相同的键，跳出循环
                        break;
                    // 将下一个节点赋值给当前节点，继续往下遍历链表
                    p = e;
                }
            }
            // 如果e不为空，则表示已经存在重复的值，即存在hash值和key值同时相等的元素
            if (e != null) {
                // 保存旧值
                V oldValue = e.value;
                // 然后替换为新值
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // 此函数会将链表中最近使用的Node节点放到链表末端，因为未使用的节点下次使用的概率较低
                afterNodeAccess(e);
                // 返回旧值
                return oldValue;
            }
        }
        // 记录修改次数
        ++modCount;
        // 如果添加元素后，超过阈值
        if (++size > threshold)
            // 则对HashMap进行扩容
            resize();
        // 给LinkedHashMap使用
        afterNodeInsertion(evict);
        return null;
    }

这篇关于JAVA HashMap 原理的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！