常见集合容器的初始容量、加载因子、扩容倍数

常见集合容器的初始容量、加载因子、扩容倍数

基于数组的集合，当数据元素的数目达到容量的上限时，容器会重新分配一段更大的连续内存，然后将容器原来的数据全部复制到新的内存上。如果容器的容量设置不合理，频繁扩容，会大大降低系统的性能。

• ArrayList

  • 初始容量 DEFAULT_CAPACITY = 10
  • 扩容倍数1.5

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

• Vector

  • 初始容量 10

  public Vector() {
      this(10);
  }
  

  • 扩容倍数 2

  private void grow(int minCapacity) {
      // overflow-conscious code
      int oldCapacity = elementData.length;
      int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                       capacityIncrement : oldCapacity);
      if (newCapacity - minCapacity < 0)
          newCapacity = minCapacity;
      if (newCapacity - MAX_ARRAY_SIZE > 0)
          newCapacity = hugeCapacity(minCapacity);
      elementData = Arrays.copyOf(elementData, newCapacity);
  }
  

• Stack

  继承自Vector。初始容量和扩容倍机制相同。

• HashMap

  • 初始容量 DEFAULT_INITIAL_CAPACITY = 1 << 4;
  • 加载系数 DEFAULT_LOAD_FACTOR = 0.75f;
  • 扩容倍数 2

  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) {
          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
      }
      ...  ...
  }
  

• ConcurrentHashMap

  • 初始容量DEFAULT_CAPACITY = 16;
  • 加载系数LOAD_FACTOR = 0.75f;
  • 扩容倍数2

• HashTable

  • 初始容量

  /**
   * Constructs a new, empty hashtable with a default initial capacity (11)
   * and load factor (0.75).
   */
  public Hashtable() {
      this(11, 0.75f);
  }
  

  • 加载系数0.75f
  • 扩容倍数 old * 2 + 1

  int newCapacity = (oldCapacity << 1) + 1;