Java教程

HashMap源码分析

本文主要是介绍HashMap源码分析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

HashMap

  • HashMap的内部包含了一个Node类型的数组table,Node是静态内部类,实现类Map.Entry接口,有四个主要属性:key、value、next、hash。也就是说table数组的每个位置看做是一个桶,一个桶可以存储一个单向链表。HashMap 使用拉链法来解决冲突,同一个链表中存放哈希值和散列桶取模运算结果相同的节点。

  • 初始容量:默认是16,也可以使用带参的构造函数指定初始值,但是会被调整成大于这个值的最小的2的次幂,这是为了在确定数组索引位置,哈希取模的时候方便使用位运算替代取模运算

    • 使用tableSizeFor(int cap)函数获得大于cap的最小的2次幂      

static final int tableSizeFor(int cap) {
    int n = cap - 1;//大于或者等于
    n |= n >>> 1;//以下5个右移,位或操作是为了把最高位1的后面都变成1,最后结果加1就得到了大于这个数的最小2次幂
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

 

  • 哈希函数:将哈希值与右移16位后的结果进行异或操作,合并高位的影响,否则由于数组长度的限制,哈希值的高位永远不会在计算索引时使用到。另外考虑到Null值的存在,如果key为Null,hash的结果直接返回0.

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    • 计算索引:哈希值与table数组的大小取模,转换为位运算就是:哈希值与数组长度减1进行位与运算,因为数组长度始终是2的次幂,减一之后的结果再与哈希值进行位与运算和取模的结果是一样的。位运算效率更高。

  • 红黑树在JDK8及以后的版本中,HashMap引入了红黑树,底层的数据结构变成了数组+链表或数组+红黑树。HashMap桶中添加元素时,若链表个数超过8,链表会转换成红黑树。 主要是为了寻找一种时间和空间的平衡

    • 是根据概率统计而选择的,和hashcode碰撞次数的泊松分布有关,在负载因子0.75(HashMap默认)的情况下,单个hash槽内元素个数为8的概率小于百万分之一,大于等于8转红黑树,小于等于6才转链表。红黑树中的TreeNode是链表中的Node所占空间的2倍,虽然红黑树的查找效率为O(logN),要优于链表的O(N),但是当链表长度比较小的时候,即使全部遍历,时间复杂度也相差不大。所以,要寻找一种时间和空间的平衡,即在链表长度达到一个阈值之后再转换为红黑树。链表中元素个数为8时的概率已经非常小,所以在选择链表元素个数时选择了8.

  • put操作:

    1. 根据Key的哈希值计算在数组中的索引,如果索引位置上是空的(此时没有冲突),就在这个位置新建一个链表节点。

    2. 如果发生冲突,接下来的思路就是已经存在的节点是否是相同的key,相同就替换,已经存在的没有相同的Key,就使用尾插法在链表结尾插入新的节点,如果是红黑树就在红黑树中进行。

    3. 维护modCount++,并判断++size是否超过threshold,是否需要扩容。

      扩容:

      • 计算新的容量,新容量是旧容量的2倍

      • 根据扩容后的容量新建一个Node数组,并且把table的引用指向新的数组。把旧数组的元素转移到新表,元素在新表中的位置有两种可能:

        1. 如果(e.hash & oldCap) == 0,原位置 j

        2. 如果(e.hash & oldCap) != 0,新位置 j+oldCap

          oldCap=16 0000 0000 0001 0000

          hash=5 0000 0000 0000 0101 旧索引是:5

          &运算 0000 0000 0000 0000 ==0 ——>新索引=5, newCap=32

          oldCap=16 0000 0000 0001 0000

          hash=17 0000 0000 0001 0001 旧索引是:1

          &运算 0000 0000 0001 0000 !=0——> 新索引=17, newCap=32

      • 对旧数组的同一个位置上的链表进行转移时,维护两个链表,一条是在新数组的相同索引位置,另一条的索引是原索引基础上加上旧的容量,采用尾插法插入节点

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 { // 维护连个链表,低位链表的索引与原索引相同,高位链表的索引在原索引基础上加上旧的容量
                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) {//原位置j
                        if (loTail == null)
                            loHead = e;
                        else
                            loTail.next = e;//尾插法
                        loTail = e;
                    }
                    else {//原索引+旧容量:j+oldCap
                        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;//高位链表
                }
            }
        }
    }
}

 

  • get操作:

    1. 根据哈希值和数组长度得到索引,如果数组在该索引的位置是非空的,再进行后续操作,否则直接返回null

    2. 判断该位置的第一个节点哈希值是否相等,equals是否为真,如果判断为真就直接返回这个节点,否则进行下一步

    3. 判断下一个节点是否存在,判断节点类型是否是红黑树,如果是红黑树就在红黑树中查找,否则就在不断循环链表的下一个节点进行查找。

这篇关于HashMap源码分析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!