HashMap源码解析(JDK1.8)

得意时要看淡,失意时要看开。不论得意失意,切莫大意;不论成功失败,切莫止步。志得意满时,需要的是淡然,给自己留一条退路;失意落魄时,需要的是泰然,给自己觅一条出路HashMap源码解析(JDK1.8),希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

一、关键属性

1.静态属性

/**
* HashMap的默认初始容量
* 1 << 4相当于2的4次方,即16,因为位运算效率高,所以如此写
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

/**
* HashMap的最大容量
* 1 << 30相当于2的30次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
* 默认负载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
* 链表转红黑树的阈值
* 当链表长度达到8时,转化为红黑树
*/
static final int TREEIFY_THRESHOLD = 8;

/**
* 红黑树转链表的阈值
* 当红黑树的节点数达到6时,退化为链表
*/
static final int UNTREEIFY_THRESHOLD = 6;

/**
* 最小树形化容量
* 当数组容量达到64时,转化为红黑树
*/
static final int MIN_TREEIFY_CAPACITY = 64;

2.非静态属性

/**
* 存放数据的数组
*/
transient Node<K,V>[] table;

/**
* 存放元素的个数
*/
transient int size;

/*
* modCount:记录当前集合被修改的次数
* (1)添加
* (2)删除
* 这两个操作都会影响元素的个数。
* 
* 当我们使用迭代器或foreach遍历时,如果你在foreach遍历时,自动调用迭代器的迭代方法,
* 此时在遍历过程中调用了集合的add,remove方法时,modCount就会改变,
* 而迭代器记录的modCount是开始迭代之前的,如果两个不一致,就会报异常,
* 说明有两个线路(线程)同时操作集合。这种操作有风险,为了保证结果的正确性,
* 避免这样的情况发生,一旦发现modCount与expectedModCount不一致,立即保错。
* 
* 此类的 iterator 和 listIterator 方法返回的迭代器是快速失败的:
* 在创建迭代器之后,除非通过迭代器自身的 remove 或 add 方法从结构上对列表进行修改,
* 否则在任何时间以任何方式对列表进行修改,
* 迭代器都会抛出 ConcurrentModificationException。
* 因此,面对并发的修改,迭代器很快就会完全失败,
* 而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
*/
transient int modCount;

/**
* 阈值
* 初始容量默认为16,为table分配内存空间后,threshold一般为capacity*loadFactory
* HashMap在进行扩容时需要参考threshold
* 初始化时阈值等于容量,当放入第一个元素后,重新计算阈值,新的阈值=容量*负载因子
*/
int threshold;

/**
* 负载因子,代表着table的填充程度
* 加载因子越大,填满的元素越多
*   好处:空间利用率高了;
*   坏处:冲突的机会加大了,链表长度会越来越长,查找效率降低;
* 加载因子越小,填满的元素越少
*   好处:冲突的机会减小了;
*   坏处:空间浪费多了,表中的数据将过于稀疏(很多空间还没用,就开始扩容了);
* 所以就是时间和空间之间的抉择;不过一般我们用默认的0.75f就好了;
*/
final float loadFactor;

二、hash方法

/**
* 如果key是空的话,就放在table下标是0的位置上,所以HashMap是允许key是空的
* h = key.hashCode() 是key对象的hashCode
* h >>> 16 是把h无符号右移16位
* 相当于key的hashCode无符号右移16位之后再与自己异或
* 我们知道这么做的目的是为了让低16位更有散列性,但是为什么不用“与运算”,“或运算”呢?
*/
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}


        0 1 1 0
        0 1 0 1
---------------
与      0 1 0 0     两个都是1,结果是1,其他情况是0
或      0 1 1 1     有1结果就是1,其余是0
异或    0 0 1 1     两个相同,结果是0,不相同结果是1

可以看出来,“与运算”结果更倾向于0,“或运算”结果更倾向于1,只有“异或运算”0和1的概率是一样的,所以异或运算的散列效果更好
总的来说,“与运算”的结果趋向于得到小的值,“或运算”的结果趋向于得到大的值,异或运算的结果大小值比较均匀分散

三、tableSizeFor方法

/**
* 因为HashMap的容量必须是2的整数幂,这个方法是找到大于等于cap最大的2的整数幂
* 如cap等于10,返回16; cap是25,返回32
*
* 2的整数幂用2进制表示其实就是最高有效位为1,其余全是0
* 如8的2进制: 1000; 32的2进制: 100000
* 
* 所以对任意十进制数转换为2的整数幂,结果是这个数本身的最高有效位的前一位变成1,
* 最高有效位以及其后的位都变为0;
* 
* 所以思路就是先将最高有效位以及其后的位都变为1,然后再+1,就进位到前一位变成1,
* 其后所有的满2变0,所以关键是如何将最高有效位后面都变为1;
*/
static final int tableSizeFor(int cap) {
    //之所以在开始移位前先将容量-1,是为了避免给定容量已经是8,16这样2的幂时,
    //不减一直接移位会导致得到的结果比预期大,比如预期16得到应该是16,
    //直接移位的话会得到32。
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    //判断n小于0的话,就按1算,超过最大容量,按最大容量算,其他情况+1,因为一开始减了1
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

下面举例说明位移后或运算,X表示可能是0或者1
             1xxxxxxxxxxxxxxxxxxxxxxxxxxx
第一次右移    01xxxxxxxxxxxxxxxxxxxxxxxxxx
或运算之后    11xxxxxxxxxxxxxxxxxxxxxxxxxx
第二次右移    0011xxxxxxxxxxxxxxxxxxxxxxxx
或运算之后    1111xxxxxxxxxxxxxxxxxxxxxxxx
第三次右移    00001111xxxxxxxxxxxxxxxxxxxx
或运算之后    11111111xxxxxxxxxxxxxxxxxxxx
第四次右移    0000000011111111xxxxxxxxxxxx
或运算之后    1111111111111111xxxxxxxxxxxx
第五次右移    0000000000000000111111111111
或运算之后    1111111111111111111111111111

可以看到,不管x是多少完成5次“右移”和“或运算”之后,最高有效位及其后的位都变成了1,这时候只要加上1,就会得到2的整数幂,只不过在int值较小的时候,后面几次的位移是多余的

四、构造方法

public HashMap();

public HashMap(int initialCapacity);

public HashMap(int initialCapacity, float loadFactor);

//HashMap的实现中,通过threshold字段来判断HashMap的最大容量;
//threshold = capacity * loadFactor;

五、getNode方法

final Node<K,V> getNode(int hash, Object key) {
    //将哈希表赋值给tab
    Node<K,V>[] tab; 
    //通过hashCode和数组长度取模,找到对应下标数组的第一个节点
    Node<K,V> first;
    //当前节点的下一个节点
    Node<K,V> e; 
    //hash表长度
    int n; 
    //当前节点的key
    K k; 
    /**
    * 将哈希表赋值给tab然后判断是否为空
    * &&将哈希表的长度赋值给n判断是否大于0
    * &&通过hashCode和数组长度取模,找到对应下标数组的node赋值给fisrt然后判断不为空
    *
    * 因为n是2的整数幂,所以 (n-1) & hash 等同于 hash % n (即hash除以n的余数)
    */
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        /**
        * 拿到第一个结点(first)的hash值和key,跟传入的hash值和key作比较,如果相同返回first结点
        */
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        /**
        * 该索引下面存储多个节点的情况下:将first的下一个结点赋值给e,判断e是否为空
        */
        if ((e = first.next) != null) {
            //判断是链表还是红黑树
            if (first instanceof TreeNode)
                //如果是红黑树,调用红黑树的查找方法
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //如果是链表,遍历该节点下面的所有结点
            do {
                //判断当前节点的hash和key是否和传入的相同,相同就返回
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    //如果没找到,就返回null
    return null;
}

下面详细将一下取模方法为什么不用 hash % n,而用 (n - 1) & hash
假如n = 4, hash = 11
我们将n和hash转成2进制
11        1011     
4         0100
4-1       0011
11&(4-1)  0011  
11的二进制最高位的1代表的是十进制的8,而我们知道长度n一定是2的整数幂,那么高位一定可能整除低位,就像例子中的8一定可以整除4,那么可以将高位舍弃掉,取模相当于就是将低位取出来,而n是2的整数幂,减1之后刚好可以得到全是1的二进制数,而“与运算”的特性是&1得到自己,那就正好可以将低位的数取出来

六、putVal方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    //将哈希表赋值给tab
    Node<K,V>[] tab; 
    //用于赋值通过hashCode和数组长度取模之后找到的节点
    Node<K,V> p; 
    //hash表长度
    int n;
    //存放hashCode和数组长度取模后得到的数组下标
    int i;
    if ((tab = table) == null || (n = tab.length) == 0)
        //赋值tab和n,判断table如果是空的,调用resize方法初始化
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        //如果要插入的数据所在的位置为空
        //创建一个新的数据,这个数据没有下一条,并将数据放到当前这个位置
        tab[i] = newNode(hash, key, value, null);
    else {
        //如果要插入的数据所在的位置有内容
        //当前节点的下一个节点
        Node<K,V> e;
        //当前节点的key
        K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            //对比hash和key,如果都相同,就替换
            e = p;
        else if (p instanceof TreeNode)
            //如果是红黑树,调用红黑树的存入方法
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //如果不是红黑树,那只能是链表,遍历链表
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    //如果当前节点的下一个是空的,就代表没有后面的数据了
                    //创建一个新的node,放到当前节点的下一个节点
                    p.next = newNode(hash, key, value, null);
                    //判断链表长度是否超过了阈值,如果超过了,调用treeifyBin转红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                //如果当前遍历到的数据和要插入的数据的key是一样,跳出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                //如果值不一样,就将下一个节点赋值给当前节点,继续循环
                p = e;
            }
        }
        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;
}

七、resize方法

final Node<K,V>[] resize() {
    //旧的table
    Node<K,V>[] oldTab = table;
    //旧table的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //旧table的阈值
    int oldThr = threshold;
    //新table的长度和阈值
    int newCap, newThr = 0;
    //旧容量大于0 
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            //如果旧容量大于等于了允许的最大值,赋值为int最大值
            threshold = Integer.MAX_VALUE;
            //因为不会再扩容了,所以返回旧table
            return oldTab;
        }
        // << 1相当于扩容为原来的2倍,如果扩容后的容量比最大值小,且旧容量大于等于初始化容量
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            //新的阈值为旧的阈值的2倍
            newThr = oldThr << 1; 
    }
    //旧容量不大于0,说明旧table是空的,再判断旧的阈值大于0
    else if (oldThr > 0) 
        /**
        * 将旧阈值作为新容量,因为此时的阈值就是容量(初始化时阈值等于容量)
		* 所以直接将原阈值赋值给新容量
        */
        newCap = oldThr;
    else {
        /**
        * 如果原容量不大于0,并且原阈值也不大于0,说明调用的无参构造方法,还没有完全初始化
    	* 只有在put数据时才完成全部初始化
        */
        //默认容量作为新容量
        newCap = DEFAULT_INITIAL_CAPACITY;
        //默认容量*负载因子作为新阈值
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //原容量不大于0且旧阈值大于0
    if (newThr == 0) {
        //临时阈值 = 新容量 * 负载因子
        float ft = (float)newCap * loadFactor;
        //如果新容量和阈值都小于最大容量就用临时阈值作为新阈值,否则就用int最大值作为新阈值
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    //将新的阈值赋给threshold
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        //按照新的容量创建新的数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    //将新建的数组赋给table
    table = newTab;
    if (oldTab != null) {
        //旧的table里还有值,需要取出放到新的table中,遍历旧table
        for (int j = 0; j < oldCap; ++j) {
            //当前节点
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                //如果旧table中有值,先置为null,方便gc
                oldTab[j] = null;
                //如果下一个位置是空的,说明后面没有连着链表或红黑树,只有一个节点
                if (e.next == null)
                    //用hash和新table的长度取模获取在新table的数组下标,并赋值
                    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) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
/*
其实if 和else 中做的事情是一样的,本质上就是将不需要更新位置的节点加入到loHead为头节点的低位链表中,将需要更新位置的节点加入到hiHead为头结点的高位链表中。
我们看到有loHead和loTail两个Node,loHead为头节点,然后loTail是尾节点,在遍历的时候用来维护loHead,即每次循环,更新loHead的next。我们来举个例子,比如原来的链表是A->B->C->D->E。
我们这里把->假设成next关系,这五个Node中,只有C的hash & oldCap != 0 ,
然后这个代码执行过程就是:
第一次循环: 先拿到A,把A赋给loHead,然后loTail也是A
第二次循环: 此时e的为B,而且loTail != null,也就是进入上面的else分支,把loTail.next = B,此时loTail中即A->B,同样反应在loHead中也是A->B,然后把loTail = B
第三次循环: 此时e = C,由于C不满足 (e.hash & oldCap) == 0,进入到了我们下面的else分支,其实做的事情和当前分支的意思一样,只不过维护的是hiHead和hiTail。
第四次循环: 此时e的为D,loTail != null,进入上面的else分支,把loTail.next = D,此时loTail中即B->D,同样反应在loHead中也是A->B->D,然后把loTail = D
*/
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    //遍历结束,即把table[j]中所有的Node处理完
                    //如果loTail不为空
                    if (loTail != null) {
                        //此时把loTail的next置空,将低位链表构造完成
                        loTail.next = null;
                        //把loHead放在newTab数组的第j个位置上
                        //也就是这些节点保持在数组中的原位置不变
                        newTab[j] = loHead;
                    }
                    //同理,只不过hiHead中节点放的位置是j+oldCap
                    if (hiTail != null) {
                        hiTail.next = null;
                        //hiHead链表中的节点都是需要更新位置的节点
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    //最后返回newTab
    return newTab;
}

扩容的流程图如下:

HashMap源码解析(JDK1.8)

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/154523.html

(0)
飞熊的头像飞熊bm

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!