集约型编程——你知道HashMap初始化大小应该怎么设置吗

- 日理万妓 2021-06-22 15:37 277阅读 0赞

集约型编程就是在考虑代码正确、保证效率的前提下，使用更少的内存，更少的cpu等资源。

### **问题引入：** ###

我们来看下面一段代码，引入我们今天的话题：

@Test
    	public void generateParam() {
    		HashMap<String, String> paramMap = new HashMap<>(3);
    		paramMap.put("name", "xiaoMing");
    		paramMap.put("age", "18");
    		paramMap.put("address", "XX市XX路XX街道");
    	}

这是同事的一段类似代码，构建一个map类型的，长度为**已知固定长度3个**的方法入参。

从代码中可以看出，同事给hashMap的初始大小为3，问：在put 3个键值对的过程中，hashMap会扩容吗？

想一下，再看下面答案：

提示一下：HashMap的默认加载因子是0.75。

答案是**不会**。

原因是在初始化map的过程中，如果给定初始化长度，HashMap会初始化成向上取离它本身最近的2的指数幂。如：initialSize是3，向上取离它本身最近的2的指数幂是2^2,就是4。如果initialSize是5，2^2比5小，往上取，所以是2^3=8，初始化成长度为8的数组。

这个逻辑在jdk6和jdk8写法上有点差异，但结果是一样的。以jdk6为例（jdk6比较直观）：

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);
    
            // Find a power of 2 >= initialCapacity
            // 这里的capacity就是从initialCapacity往上取最接近的2的指数幂
            // threshold 为capacity * loadFactor
            int capacity = 1;
            while (capacity < initialCapacity)
                capacity <<= 1;
    
            this.loadFactor = loadFactor;
            threshold = (int)(capacity * loadFactor);
            table = new Entry[capacity];
            init();
        }

上面是初始化的过程，下面请看HashMap扩容的阀值：

void addEntry(int hash, K key, V value, int bucketIndex) {
    	Entry<K,V> e = table[bucketIndex];
            table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
            //当size>=threshold时就进行扩容，size++是在比较完之后加的（不清楚的可以看看i++和++i的区别）
            if (size++ >= threshold)
                resize(2 * table.length);
        }

所以我们来看一下一开始的例子代码的执行过程：

首先initialCapacity=3，初始化的时候会自动向上取最近的2的指数幂，为4，而threshold 为capacity \* loadFactor，当loadFactor使用默认值0.75时，threshold=3，所以当第三个元素put之后，在size++>=threshold表达式中，size为2（比较结束之后才变为3），而2>=3为false，所以不会扩容。

回头看来，3算是一个凑巧的数字了，在初始化时自动初始化成4了，你可以试试put7个参数，而创建HashMap的initialCapacity设为7，此时就会扩容了，因为7，向上取2指数幂是8，默认的threshold为6<7,所以会扩容了。

### **总结：** ###

1、Map初始化如果要指定初始化大小，initialCapacity应为2的指数幂，避免自动调整。（就如上例中的3，初始化时会自动转为4）。

2、初始化时，在知道map的最终大小的前提下，要使得threshold>=n（n为固定的数据量 且threshold=capacity \* loadFactor），而不是initialCapacity>=n

### **拓展阅读：** ###

前面举的是jdk6的例子，下面我们来看一下jdk8的代码：

下面来看一下tableSizeFor的算法：

/**
         * Returns a power of two size for the given target capacity.
         */
        // 从注释中我们就可以看出，下面的位运算就是向上取最近的2指数幂
        static final int tableSizeFor(int cap) {
            int n = cap - 1; // 解决刚好是2的指数幂的情况，如果刚好的2的指数幂，会使得无法与其他数统一处理 
            n |= n >>> 1; // 位的或运算，1|0=1，有一个1就等于1。  |= 或等，就与 n = n | n>>>1等价
            n |= n >>> 2; // >>>三个大于号是逻辑右移，正数不影响，负数最高位补0，但试了一个，在这里逻辑右移>>>和算数右移>>对结果没影响
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }

这个算法少一句都不行，设计得很巧妙，替换了jdk6中的while循环。我们来举个例子：

如果cap的大小为18，二进制为10010。

10010 | 01001 = 11011（n）

11011 | 00110 = 11111

11111 | 00001 = 11111

11111 | 00000 = 11111

至此，我们发现该算法实现了整数级别（32位），将从第一个1开始，后面的0都变成1。

再看看这句：

int n = cap - 1; // 解决刚好是2的指数幂的情况，如果刚好的2的指数幂，会使得无法与其他数统一处理

tableSizeFor方法得到的不是最终的threshold，在put方法还会初始化，看下面代码的注释部分：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node<K,V>[] tab; Node<K,V> p; int n, i;
            if ((tab = table) == null || (n = tab.length) == 0)
                // 关注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; K k;
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    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) {
                            p.next = newNode(hash, key, value, null);
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                if (e != null) { // existing mapping for key
                    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() {
            Node<K,V>[] oldTab = table;
            int oldCap = (oldTab == null) ? 0 : oldTab.length;
            // 前面算出来的threshold，就是2的指数幂
            int oldThr = threshold;
            int newCap, newThr = 0;
            if (oldCap > 0) {
                if (oldCap >= MAXIMUM_CAPACITY) {
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // double threshold
            }
            else if (oldThr > 0) // initial capacity was placed in threshold
                newCap = oldThr;
            else {               // zero initial threshold signifies using defaults
                newCap = DEFAULT_INITIAL_CAPACITY;
                // 这里就是新的threshold，和jdk6的结果是一样的
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            //以下略

我们可以看到，在put第一个元素的时候，进行了threshold的再一次初始化。

然后扩容的条件由：size++>=threshold 变成 ++size > threshold，这两句是等价的，是复习++i和i++的好例子。

所以，关于这个初始化大小的问题，jdk6和jdk8还是基本一样的。

有什么问题欢迎评论探讨！

码字不易，喜欢的话就点个赞吧。orz