Java学习--HashMap详解(构造函数)

Java/ 集合 Java 集合 Map
创建时间:
字数:2.6k 阅读:
  1. Java学习–HashMap详解(构造函数)
    1. 负载因子(loadFactor)
    2. 无参构造函数
    3. 仅设置初始容量的构造函数
    4. 设置初始容量和负载因子的构造函数
      1. tableSizeFor 方法
        1. >>> 含义
    5. 以Map进行初始化的构造函数
    6. 总结

Java学习–HashMap详解(构造函数)

在JDK的使用过程当中，我们经常要用到的莫过于集合类型了。而在集合类型当中，我们更加注重的是Map这个集合。因此，在接下来的一段时间内，我主要讲解Map中的经典实现(HashMap)的源码分析、出现并发的情况、以及与ConcurrentHashMap的区别。因为本文章不知道读的人的水平如何，因此，我尽量采用通俗易懂+图文结合的方式，来讲解HashMap的源码，在这个系列的最后，我们我们会列出来关于不同的JDK的版本对于HashMap的一个改动。

本次我们主要讲解的HashMap是在JDK1.8版本的。

Java版本信息

接下来，我们在这篇文章主要讲解的是HashMap的构造函数。

在HashMap中，HashMap一共有四个构造函数，接下来，我们逐一进行讲解。

负载因子(loadFactor)

首先，在讲解无参构造函数之前，我们先来讲解下为什么在JDK的官方源码中，将HashMap的负载因子设置为0.75。

首先，我们知道，在计算机的运行过程中，我们主要注重的是两个问题，一个是希望我们的程序尽可能的运行的快。另一个，我们希望我们程序在运行的过程中，尽可能的少消耗我们的内存。这个就是计算机中评判一个程序经常用到的两个维度，时间复杂度和空间复杂度。在实际的程序运行过程中，我们不可能同时将这两个标准都优化到极致，因此在很多的程序，对于这两个标准，会根据实际的业务需求，采用以下三种方案进行开发：

  • 牺牲程序的时间复杂度，尽可能的降低程序的空间复杂度
  • 牺牲程序的空间复杂度，尽可能的降低程序的时间复杂度
  • 综合考虑程序的时间复杂度和空间复杂度，在这两者中，选择一个折中平衡点

而在JDK的HashMap中，就是采用了第三种方案，经过了无数的证明与总结，人们发现，当负载因子为0.75的时候，此时程序的效率最高。因此，在JDK的源码中，将HashMap的默认负载因子设置成了0.75。

上面我们讲解了这么多，又是负载因子，又是时间复杂度，又是空间复杂度的。那么在HashMap中，这些含义到时是干什么用的呢？其实，我们都知道，对于HashMap而言，他就是一个集合。那么对于集合，一定要提供两个功能 –> “读取”和“存储”。 既然要存储和读取，那么我们关心的其实就是两个问题:

  • 是否足够快
  • 是否省内存

对于JDK而言，在保证效率的同时，势必要进行内存的无休止消耗。因此在两者之间做了一个权衡，也就是所谓的0.75的存在了。而这个数值的存在，也是在大量的试验下的出的一个最优解。

无参构造函数

    /**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

我们首先来看下我们的最最常用的无参构造函数。该函数仅仅只是设置了程序的默认负载因子，也就是上文提到的0.75。并没有去进行Array的初始化操作。

仅设置初始容量的构造函数

    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param  initialCapacity the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative.
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

在这里，我们发现，它调用了另外的一个构造函数，至于在这个构造函数值的操作，不要着急，我们在下个构造函数中进行操作。我们发现，当我们使用这个构造函数的时候，我们可以指定默认的Array的大小，只不过这个大小会进行清洗，让它变成最接近于2n，且该值要大于等于我们设置的默认Array的大小，至于是怎么进行操作的，在此先卖个关子，在下面我们会进行着重讲解。同时，我们发现，在默认的情况下，此时默认的负载因子为0.75。

设置初始容量和负载因子的构造函数

    /**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

接下来，是我们最最重要的一个构造函数了。这个构造函数我们可以同时指定Array的大小和负载因子的比例。只不过，在这里要强调一点的是，默认情况下，我们可以改变Array的大小，但是对于负载因子，除了特殊的情况外，我们一般用默认值即可。

接下在，我们看下上面的代码，我们发现，Array的最大的大小为2<<30(static final int MAXIMUM_CAPACITY = 1 << 30;)。要解释为什么是230呢？通过代码我们可以发现：

  • 因为int是4个字节，代表了32位，又因为第一位代表的是+/-。所以，只能是230了。
  • 同时，为什么要使用int，而不是使用byte、short、long等类型呢？其实，这个是为了系统的性能考虑，做的一个折中的处理。

接下来，就是最重要的一步。对于我们传入的初始Array大小initialCapacity，此时会传入tableSizeFor方法中，并且将返回的结果返回给threshold。通过这里，我们发现，HashMap并没有使用我们直接传入的初始容量，而是在进行一系列的运算后，才最终确定我们最终的Array的大小的。

tableSizeFor 方法

接下来，我们看下tableSizeFor这个方法的源码。

    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;
    }

在讲解上面的代码之前，我们要知道>>>方法的含义

>>> 含义

>>>表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0

接下来，我们说下，n | n -1的含义。在这里|是或的含义。我们举个例子:

1001 | 0101 = 1101

接下来，我们看下，在HashMap中，是如果将一个数洗成一个2n的。

此时，我们假设cap为7944525。此时对应的二进制为0111 1001 0011 1001 0100 1101。接下来，我们手动进行计算：

n = 0111 1001 0011 1001 0100 1101            最原始值
n >>> 1 = 0011 1100 1001 1100 1010 0110
此时我们计算 n | n >>> 1 的结果为：
n | n >>> 1 = 0111 1101 1011 1101 1100 1111
此时我们的n 也就变成了 0111 1101 1011 1101 1100 1111
接下来，我们计算 n >>> 2
此时 n >>> 2 的结果为: 0001 1111 0110 1111 0111 0011
此时 n | n >>> 2 的结果为：0111 1111 1111 1111 1111 1111
接下来，以此类推，我们通过每次的运算结果与 最原始值 进行观察，我们发现，这样做的目的，是为了让 最原始值中的1的后X位于1进行或，就可以得到结果：
最后，我们用我们得出的结论与上面的结果进行验证：
n = 0111 1001 0011 1001 0100 1101
n | n >>> 1 = 0111 1101 1011 1101 1100 1111
n | n >>> 2 = 0111 1111 1111 1111 1111 1111
n | n >>> 4 = 0111 1111 1111 1111 1111 1111
n | n >>> 8 = 0111 1111 1111 1111 1111 1111
n | n >>>16 = 0111 1111 1111 1111 1111 1111

此时，我们得到 n+1 = 8388608。也就是223。

接下来，我们以cap=14669进行举例，我们直接以上面的结论进行计算：

n = 0011 1001 0100 1101
n | n >>> 1 = 0011 1101 1110 1111
n | n >>> 2 = 0011 1111 1111 1111
n | n >>> 4 = 0011 1111 1111 1111
n | n >>> 8 = 0011 1111 1111 1111
n | n >>>16 = 0011 1111 1111 1111

此时n+1=16384。也就是214。通过上面的两个例子，我们发现，当HashMap拿到一个值后，首先对值进行减1操作，然后将值进行清洗，让2进制的值，从又开始遇到的第一个1开始，后面都清洗成1。最后在将减去的1加回去，变成2n。

HashMap正是通过这样的做法，保证了我们的Array的数组大小为2n。至于为什么一定要是2n，这个在后续的文章中会进行讲解的。

以Map进行初始化的构造函数

    /**
     * Constructs a new <tt>HashMap</tt> with the same mappings as the
     * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
     * default load factor (0.75) and an initial capacity sufficient to
     * hold the mappings in the specified <tt>Map</tt>.
     *
     * @param   m the map whose mappings are to be placed in this map
     * @throws  NullPointerException if the specified map is null
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

对于这个构造函数，在实际的工作中，我们用到的不多，在putMapEntries中，主要是进行了resize()操作与putVal()操作，这个会在后续的文章中进行讲解。至于代码中其他的部分，十分的简单，都是利用了本文所讲解的内容，在这里不再进行额外的赘述。

总结

对于HashMap的构造函数，我们知道了以下几点信息

  • HashMap提供了四种构造函数，至于他们之前的原理，请参考上面的文章
  • 对于负载因子为什么是0.75,在上文中进行了讲解。
  • 对于HashMap中Array的最大容量为1<<30，我们也进行了讲解
  • 对于HashMap中，是如果将一个随意的初始容量洗成2n，在上面的文章中进行了讲解。

学无止境，只有不断的学习，才能配得上更好的自己。

转载请注明来源，欢迎指出任何有错误或不够清晰的表达。可以邮件至 gouqiangshen@126.com

赏

文章标题:Java学习--HashMap详解(构造函数)

文章字数:2.6k

本文作者:BiggerShen

发布时间:2020-02-18, 15:52:55

最后更新:2024-01-16, 03:51:15

原始链接:https://shengouqiang.cn/Java/JDK/HashMap/JDKHashMapLearnDay01/

版权声明: 转载请保留原文链接及作者。

京ICP备19032600号 京ICP备19032600号-1

目录
×

喜欢就点赞,疼爱就打赏