开发者

Java基础篇之HashMap指定初始值

开发者 https://www.devze.com 2023-12-10 10:18 出处:网络 作者: 程序员小李_
目录HashMap为什么要指定初始大小?怎么保证不会扩容呢?扩展:负载因子与实际元素数据之间的计算0.125跟默认负载因子0.75有什么关系呢?怎么设置默认负载因子为0.125呢?如果你无法修改哈希表实现的源代码总结HashM
目录
  • HashMap为什么要指定初始大小?
  • 怎么保证不会扩容呢?
  • 扩展:
    • 负载因子与实际元素数据之间的计算
    • 0.125跟默认负载因子0.75有什么关系呢?
    • 怎么设置默认负载因子为0.125呢?
    • 如果你无法修改哈希表实现的源代码
  • 总结

    HashMap为什么要指定初始大小?

    在Java中,HashMap是一种基于哈希表实现的键值对存储结构。哈希表是一种典型的散列表,它通过哈希函数将任意长度的键值对映射到一个固定长度的数组中,然后使用链表或红黑树等数据结构来解决哈希冲突。

    HashMap中,指定初始大小的作用是为了减少哈希冲突,提高存储效率和查询效率。当哈希表大小不足时,HashMap会自动扩容,但这个过程比较耗时,因为需要重新计算键值对的哈希值,重新分配内存空间,重新插入键值对等。如果预估好数据规模,指定初始大小可以避免不必要的扩容,提高程序的性能。

    另外,python指定初始大小还可以控制哈希表的负载因子。负载因子是哈希表中键值对数量与哈希表大小的比值,通常情况下,负载因子的值在0.75左右可以达到较好的性能和空间利用率。如果负载因子过高,会导致哈希冲突增多,查询效率降低;如果负载因子过低,会导致哈希表空间浪费,存储效率降低。因此,指定初始大小可以控制负载因子的值,达到平衡空间和时间的效果。

    总之,指定初始大小可以优化HashMap的空间利用率、时间复杂度和性能表现,是一种比较常见的优化策略。

    使用默认负载因子0.75时,需要put(),3个元素,需指定初始大小为4

    如果使用默认的负载因子0.75,在put 3个元素时,设置初始大小为4是刚好合适的,不需要自动扩容,且能够达到较好的效率。但是,如果要put 5个元素,初始大小为4可能就不够了,会触发自动扩容,导致效率降低。

    具体来说,当初始大小为4时,哈希表的容量为4,而负载因子为0.75,表示当哈希表中元素数量达到容量的 0.75 倍即 3 个时,就会触发自动扩容。因此,当你要put 5个元素时,会触发一次自动扩容。

    为了避免自动扩容,需要将初始大小设置得更大。一种常用的方法是,将初始大小设置为大于等于要put 的元素数量的最小的2的幂次方。例如,如果要put 5个元素,可以将初始大小设置为8,这样可以避免触发自动扩容,提高效率。

    当然,如果你希望在put 5个元素时也不触发自动扩容,并且能够达到最大化的效率,可以根据实际情况调整初始大小和负载因子。具体的值需要根据实际场景进行调整,以达到最优的性能。

    怎么保证不编程客栈会扩容呢?

    可以将初始大小设置为大于等于要put的元素数量的最小的2的幂次方,以确保在使用默认负载因子的情况下,不会在插入元素时触发扩容。例如如果需要put()5个元素,即2的5次方 = 32

    那为什么要设置这么大而不是设置8?

    当我们将初始大小设置为8时,如果要put 5个元素,那么在使用默认负载因子0.75的情况下,哈希表会在第四个元素插入时就触发扩容,这是因为当前的容量为8,而put第四个元素时,已经有3个元素占用了哈希表中的位置,此时负载因子已经达到了0.375(即3/8),超过了默认负载因子0.75的一半,因此需要进行扩容。

    而当我们将初始大小设置为32时,即使要put 5个元素,也不会触发扩容,因为当前的容量为32,而put第五个元素时,已经有4个元素占用了哈希表中的位置,此时负载因子为0.125(即4/32),远远低于默认负载因子0.75,不需要进行扩容。

    因此,为了避免不必要的扩容操作,我们可以将初始大小设置为大于等于要put的元素数量的最小的2的幂次方,以确保在使用默认负载因子的情况下,不会在插入元素时触发扩容。当然,如果我们知道要put的元素数量是多少,也可以直接将初始大小设置为该数量,以避免不必要的空间浪费。

    知道要put的元素数量是多少,也可以直接将初始大小设置为该数量,这样如果默认负载因子0.75岂不是又要开始触发扩容?还是有消耗呢?比起空间浪费,这种要怎么衡量呢?

    确实,如果我们知道要put的元素数量是多少,也可以直接将初始大小设置为该数量。javascript在这种情况下,如果使用默认负载因子0.75,当哈希表中的元素数量达到容量的 0.75 倍时,就会触发扩容,从而浪费一些空间。但是,这里需要注意的是,在初始大小等于元素数量的情况下,扩容所需的代价通常比较小,因为仍然有足够的空间php可以容纳元素。

    如果我们比较在初始大小等于元素数量和初始大小为2的幂次方时的空间浪费和时间代价,通常情况下,后者会更少。因为在初始大小为2的幂次方时,哈希表的容量通常都比较大,可以容纳更多的元素,从而减少扩容的次数,提高效率。而在初始大小等于元素数量时,哈希表的容量通常比较小,可能需要进行多次扩容,导致效率降低。

    当然,这并不是说初始大小等于元素数量就一定不好,或者初始大小为2的幂次方就一定好。具体的选择需要根据实际情况来衡量,综合考虑空间和时间的代价,以达到最优的性能。

    为什么,在初始大小等于元素数量的情况下,扩容所需的代价通常比较小?

    在初始大小等于元素数量的情况下,如果使用默认负载因子0.75,当哈希表中的元素数量达到容量的 0.75 倍时,就会触发扩容。此时,需要重新计算哈希值并将元素重新插入到新的更大的哈希表中,这个过程需要花费一定的时间,但是由于初始容量等于元素数量,因此扩容时所需的空间通常比较小,因此空间代价相对较小。

    在初始大小为2的幂次方时,哈希表的容量通常都比较大,可以容纳更多的元素,从而减少扩容的次数,提高效率。但是,如果元素数量远小于容量,会导致空间浪费。此外,由于需要将元素重新哈希并重新插入,因此扩容时所需的时间会相对较长,因此时间代价相对较高。

    因此,在选择初始大小时,需要综合考虑空间和时间的代价,以达到最优的性能。如果我们知道要put的元素数量是多少,也可以直接将初始大小设置为该数量,但是需要注意元素数量和容量之间的平衡,避免空间浪费和过多的扩容操作。

    假设需要put()4个元素,指定其初始大小为4,它会经过一次扩容,那么它会扩容到多大呢?

    在这个情况下,哈希表的初始大小为4,需要存储4个元素。因为默认负载因子为0.75,所以在哈希表中存储4个元素时,会有一个扩容操作。扩容操作会将哈希表的容量翻倍,然后将已有的元素重新分配到新的容量中,以充分利用空间。因此,哈希表在扩容后的容量为8。

    具体而言,哈希表的js扩容触发条件是:当哈希表中的元素数量达到容量的0.75时,就会触发扩容操作。在这个情况下,初始大小为4,容量为4,因此当存储第3个元素时,哈希表的元素数量为3,容量为4,还有一个空位。但是,当存储第4个元素时,哈希表的元素数量就达到了容量的0.75,也就是3个元素的75%。因此,哈希表触发了一次扩容操作,容量翻倍,变为8。然后,已有的3个元素会重新分配到新的容量中,以充分利用空间。

    哈希表在扩容时会将容量翻倍,因此在这个情况下,哈希表的容量从4扩容到了8,扩容了两倍。哈希表的扩容操作是为了保证哈希表中的负载因子不超过预设的值,以提高哈希表的性能和空间利用率。在Java中,HashMap类的默认负载因子是0.75,也就是当哈希表中的元素数量达到容量的0.75时,就会触发扩容操作,容量翻倍。

    扩展:

    负载因子与实际元素数据之间的计算

    负载因子是指哈希表中已经被占用的元素数量与容量的比值。例如,当哈希表容量为32,其中已经有4个元素被占用时,负载因子就是4/32=0.125。

    如果要使用负载因子为0.125,可以通过以下公式计算哈希表的容量:

    容量 = 元素数量 / 负载因子

    例如,如果要存储32个元素,使用负载因子为0.125,那么哈希表的容量就应该是:

    容量 = 32 / 0.125 = 256

    因此,可以将哈希表的初始大小设置为256,并使用负载因子为0.125,这样可以在不触发扩容的情况下存储32个元素,同时尽可能地减少空间浪费。

    0.125跟默认负载因子0.75有什么关系呢?

    默认负载因子0.75和负载因子0.125都是用于计算哈希表容量的参数,但是它们的取值不同,因此对哈希表的容量和扩容行为也有影响。

    默认负载因子0.75表示当哈希表中的元素数量达到容量的0.75倍时,就会触发扩容。这个值是经验值,根据哈希表的设计和使用场景来确定的。如果哈希表中元素数量较少,就会浪费空间;如果元素数量较多,就会引起频繁的扩容操作,影响性能。

    而负载因子0.125表示哈希表中已经被占用的元素数量与容量的比值为0.125。如果使用这个负载因子,就需要根据元素数量计算出合适的容量,以尽可能地减少空间浪费。如果哈希表中元素数量达到容量的0.125倍时,就需要扩容。这个负载因子比默认负载因子小,因此扩容的频率会相对较低,但是需要更大的容量,因此会占用更多的内存。

    总之,负载因子是一个用于计算哈希表容量和扩容触发条件的参数,需要根据实际需求来选择合适的值。默认负载因子0.75适用于大多数情况,如果需要更严格的空间控制,可以选择更小的负载因子。

    怎么设置默认负载因子为0.125呢?

    默认负载因子是哈希表实现中的一个参数,通常是在实现代码中预先定义好的。如果要将默认负载因子从0.75修改为0.125,需要修改哈希表实现的源代码。

    具体而言,需要找到哈希表实现中关于负载因子的定义,并将其修改为0.125。例如,在Java中,可以使用HashMap类来实现哈希表,而HashMap类中关于负载因子的定义如下:

    /**
     * The load factor for the hash table.
     *
     * @serial
     */
    final float loadFactor;
    

    其中,loadFactor是一个final类型的float变量,用于表示哈希表的负载因子。默认情况下,loadFactor的值为0.75。

    要将负载因子修改为0.125,可以将HashMap类中的loadFactor定义修改为如下所示:

    /**
     * The load factor for the hash table.
     *
     * @serial
     */
    final float loadFactor = 0.125f;
    

    修改后,HashMap类中的所有哈希表实例都会使用负载因子0.125来计算容量和扩容触发条件。当然,这也可能会对HashMap的性能产生一定的影响,因此需要根据实际情况来选择合适的负载因子。

    如果你无法修改哈希表实现的源代码

    那么就无法直接修改默认负载因子。但是,你仍然可以创建自定义的哈希表实现,并在其中使用自己定义的负载因子。

    例如,在Java中,你可以创建一个自定义的哈希表类,继承自HashMap,并在其中重写loadFactor字段,将其修改为0.125。示例代码如下:

    public class MyHashMap<K,V> extends HashMap<K,V> {
        private static final long serialVersionUID = 1L;
        public static final float LOAD_FACTOR = 0.125f;
        public MyHashMap() {
            super();
        }
        public MyHashMap(int initialCapacity) {
            super(initialCapacity);
        }
        public MyHashMap(int initialCapacity, float loadFactor) {
            super(initialCapacity, loadFactor);
        }
        @Override
        public float getLoadFactor() {
            return LOAD_FACTOR;
        }
    }

    在这个自定义的哈希表类中,我们定义了一个常量LOAD_FACTOR,用于表示负载因子的值。然后,在构造函数中,我们可以调用父类的构造函数,并传入LOAD_FACTOR作为负载因子的值。同时,我们还重写了getLoadFactor方法,返回LOAD_FACTOR,以确保哈希表中的负载因子始终为0.125。

    使用这个自定义的哈希表类时,就可以使用负载因子0.125来计算容量和扩容触发条件了。例如,可以创建一个容量为64的哈希表,存储32个元素,代码如下:

    MyHashMap<String, Integer> map = new MyHashMap<>(64);
    for (int i = 0; i < 32; i++) {
        map.put("key" + i, i);
    }
    

    这个哈希表的负载因子为0.125,可以充分利用空间,同时扩容的频率也会相对较低。

    总结

    到此这篇关于Java基础篇之HashMap指定初始值的文章就介绍到这了,更多相关Java HashMap指定初始值内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)!

    0

    精彩评论

    暂无评论...
    验证码 换一张
    取 消

    关注公众号