集约型编程就是在考虑代码正确、保证效率的前提下,使用更少的内存,更少的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); }
所以我们来看一下一开始的例子代码的执行过程:
讯享网 @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街道"); }
首先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的代码:
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; // 计算threshold this.threshold = tableSizeFor(initialCapacity); }
下面来看一下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
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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/77117.html