JAVA HashMap 原理

2022/2/3 1:13:36

本文主要是介绍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 原理的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程