HashMap源码

HashMap源码阅读记录

先说说1.7

1.7的时候主要存在几个问题

  • key的hash值计算方式很复杂
  • 在扩容的时候,因为使用的是尾插法,所以在多线程对这个变量进行操作的时候会产生一个环,导致死循环
  • 最大的问题就是hash冲突问题,当一个桶里元素过多的时候,就相当于一个很长的链表,查询的时候需要从头到尾遍历一遍,时间复杂度是O(n)。

在1.8的优化

  • hash计算方式,是通过key的hashcode的高16位与hashcode进行异或运算

    /**
     * Computes key.hashCode() and spreads (XORs) higher bits of hash
     * to lower.  Because the table uses power-of-two masking, sets of
     * hashes that vary only in bits above the current mask will
     * always collide. (Among known examples are sets of Float keys
     * holding consecutive whole numbers in small tables.)  So we
     * apply a transform that spreads the impact of higher bits
     * downward. There is a tradeoff between speed, utility, and
     * quality of bit-spreading. Because many common sets of hashes
     * are already reasonably distributed (so don't benefit from
     * spreading), and because we use trees to handle large sets of
     * collisions in bins, we just XOR some shifted bits in the
     * cheapest possible way to reduce systematic lossage, as well as
     * to incorporate impact of the highest bits that would otherwise
     * never be used in index calculations because of table bounds.
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
  • 使用了尾插法,解决了死循环的问题
  • 计算初始容量的方式发生改变,1.7的时候是通过对1进行左移运算,直到找到比入参容量大的一个2的n次幂的数。1.8的时候,用了一种更优雅的方式,就是通过5个移位运算,得到一个低位全是1的值,最后得到一个初始容量。

    /**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        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;
    }

  • 最重要的就是使用了数组+链表+红黑树。在数组长度大于64并且链表的长度大于8的时候会转换成一个红黑树。这样他的查询效率得到提升,以前是O(n),红黑树是O(logn)

讲一下put方法,插入的流程

HashMap源码

  1. 首先通过key的hashcode来计算hash值
  2. 这个时候看map是否为空,如果为空的话就会先进行一次resize扩容,这时候他的初始容量大小是16
  3. 通过hash值和hashmap长度-1进行与运算得到桶的索引下标
  4. 找到桶的位置后,观察这个桶的头节点是否为空,如果是空的话就直接放进去,因为hashmapkey是不允许相同的,所以,如果不为空就检查头节点的key是否与入参的key相同,如果相同的话就直接覆盖value,如果不同就遍历这个链表,如果发现相同的key也进行覆盖,否则通过尾插法插入到链表的最后。
  5. 当链表的长度大于8并且数组的长度大于64的时候,会转变为红黑树

扩容的过程 resize

上一篇:JAVA编程思想笔记 第二章 一切都是对象


下一篇:Codeforces 1208F - Bits And Pieces (SOSdp)