hashmap 和 arraylist

xiaoxiao2021-02-28  11

http://blog.csdn.net/jeffleo/article/details/54946424

思考1、假如我们要创建已知长度的集合List(ArrayList)or Map(HashMap),如何创建?通常Map<Integer,Object> map = new HashMap<>(1);List<String> list = new ArrayList<>(1);固定长度,减少扩容次数2、HashMap构造函数,除了初始化容量,还有其它参数吗?还有个扩容因子loadFactor

印象中以为ArrayList和HashMap都有loadFactor,其实只有HashMap中有,ArrayList中没有。那么他们是如何实现扩容的呢?

ArrayList

/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }

add()方法调用ensureCapacityInternal()方法。size表示元素数量,同list.size()方法

private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code // 是否扩容判断 if (minCapacity - elementData.length > 0) grow(minCapacity); }

最小容量 (minCapacity) = size + 1; 当最小容量大于存储数组长度时,触发扩容,so...数组存储满时再添加新元素触发扩容。

/** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1);//此处 if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }

新容量(newCapacity) = 原容量 + 原容量位运算左移1位 最后通过Arrays.copyOf方法完成复制扩容。 注:左移1位 = n/2 取整

总结: 1、扩容触发点,数组存储已满,再add()时触发 2、扩容量,大概是原来的一半,准确是 newCapacity = oldCapacity + (oldCapacity >> 1);

HashMap 错误理解,原印象扩容因子loadFactor,默认0.75,即假如当前容量是100时,元素数量达到75,即75%时触发扩容。扩容量是当前容量值最近2n次方。

正解: hashMap.put(key,value)会调用resize()方法

/** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ 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) n = (tab = resize()).length;//此处1 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { //此处省略... } ++modCount; if (++size > threshold) resize();//此处2 afterNodeInsertion(evict); return null; }

此处1:第一次put时初始化table,调用resize()方法 此处2:新增后元素数量大于threshold,调用resize()方法 threshold阈值,注释【The next size value at which to resize (capacity * load factor)】

final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { //此处1 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //此处2 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } //此处3 else if (oldThr > 0) //initial capacity was placed in threshold newCap = oldThr; //此处4 else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //此处5 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; //中间省略... }

新阈值和新容量计算稍复杂,仔细梳理每行代码,抛开容量最大值、超出int范围问题,代码解读 新阀值: 1、当原容量大于0 && 原容量右移1位后小于最大容量 && 原容量大于初始容量,新阈值等于原阈值右移1位,即新阈值 = 原阈值2 2、当原容量等于0 && 原阈值等于0,新阀值等于默认扩容因子(0.75) 默认初始化容量(16) 3、前两种都不满足时,新容量 * 扩容因子 新容量: 4、当原容量大于0,新容量等于原右移1位 5、当原容量等于0 && 原阈值大于0,新容量等于原阈值 6、当原容量等于0 && 原阈值等于0,新容量等于默认初始容量

场景: 1、new HashMap(),第一次put,原容量等于0,原阈值等于0,执行代码"此处4" 2、new HashMap(),第n(1< n <int最大值)次put时,原容量大于0,原阈值大于默认初始容量,执行代码"此处2" 3、new HashMap(initialCapacity),第一次put时,因设置初始容量,阀值会在构造函数初始化,阀值等于 比initialCapacity大于等于的最近2的n次方(假如设置初始容量3,比3大的最近的2的n次方是4),所以原容量等于0,原阈值大于0,执行代码"此处3",新阈值等于0 , 代码"此处5"也会执行。 4、new HashMap(initialCapacity),如果table已有元素,那么原容量大于0,当原容量小于默认容量时,只会执行代码"此处5" 5、new HashMap(initialCapacity),如果table已有元素,同上,原容量大于0,当原容量大于等于默认容量时,只会执行代码"此处2"

总结 1、只原容量等于0或原容量小于默认初始容量时,新阀值 = 新容量 * 扩容因子 2、非1情况,新阀值 = 新容量 = 原容量*2

作者:耗子2015 链接:http://www.jianshu.com/p/21ef5957d6e9 來源:简书 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
转载请注明原文地址: https://www.6miu.com/read-1650341.html

最新回复(0)