Java中各种集合的扩充机制

Veröffentlicht am | Bearbeitet am | in
Symbole im Artikel gezählt: 3.2k | Lesezeit ≈ 3 minuten.

JAVA中的部分需要扩容的内容总结如下：

HashMap：

  1. 初始容量定义：默认为1 << 4（16）。最大容量为1<< 30
  2. 扩容加载因子为(0.75)，第一个临界点在当HashMap中元素的数量大于table数组长度加载因子（16*0.75=12），
    则按oldThr << 1（原长度*2）扩容。

HashSet:

  1. 初始容量定义：16。因为构造一个HashSet，其实相当于新建一个HashMap，然后取HashMap的Key。
  2. 扩容机制和HashMap一样。

Hashtable:

  1. 初始容量定义：capacity (11)。

  2. 扩容加载因子(0.75)，当超出默认长度（int）（110.75）=8时，扩容为old\2+1。

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

    HashTable和HashMap区别:

    1. 继承不同。
      public class Hashtable extends Dictionary implements Map
      public class HashMap extends AbstractMap implements Map
    2. Hashtable 中的方法是同步的，而HashMap中的方法在缺省情况下是非同步的。在多线程并发的环境下，可以直接使用
      Hashtable，但是要使用HashMap的话就自己增加同步处理了。
    3. Hashtable中，key和value都不允许出现null值。在HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。当get()方法返回null值时，
      即可以表示 HashMap中没有该键，也可以表示该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中
      是否存在某个键， 而应该用containsKey()方法来判断。
    4. 两个遍历方式的内部实现上不同。Hashtable、HashMap都使用了 Iterator。而由于历史原因，Hashtable还使用了Enumeration的方式 。
    5. 哈希值的使用不同，HashTable直接使用对象的hashCode。而HashMap重新计算hash值。
    6. Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式。HashTable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16， 增加的方式是 old*2。

ArrayList:

  1. 初始容量定义：10。
  2. 扩容：oldCapacity + (oldCapacity >> 1)，即原集合长度的1.5倍。

int newCapacity = (oldCapacity * 3)/2 + 1;

CopyOnWriteArrayList：

CopyOnWriteArrayList在做修改操作时，每次都是重新创建一个新的数组，在新数组上操作，最终再将新数组替换掉原数组。因此，在做修改操作时，仍可以做读取操作，读取直接操作的原数组。读和写操作的对象都不同，因此读操作和写操作互不干扰。只有写与写之间需要进行同步等待。另外，原数组被声明为volatile，这就保证了，一旦数组发生变化，则结果对其它线程(读线程和其它写线程)是可见的。

CopyOnWriteArrayList并不像ArrayList一样指定默认的初始容量。它也没有自动扩容的机制，而是添加几个元素，长度就相应的增长多少。CopyOnWriteArrayList适用于读多写少，既然是写的情况少，则不需要频繁扩容。并且修改操作每次在生成新的数组时就指定了新的容量，也就相当于扩容了，所以不需要额外的机制来实现扩容。

  1. ArrayList与Vector初始容量都为10。
  2. 扩容机制不同，当超出当前长度时ArrayList扩展为原来的1.5倍，而若不考虑扩容因子Vector扩展为原来的2倍。

  3. ArrayList为非线程安全的，处理效率上较Vector快，若同时考虑线程安全和效率，可以使用 CopyOnWriteArrayList。

    StringBuffer:

  4. 初始容量定义：16。

  5. 扩容：因为StringBuffer extends AbstractStringBuilder，所以实际上是用的是AbstractStringBuilder
    的扩容方法，当用append(str)添加字符串时，假设字符串中已有字符长度为count的字符串,初始长度value=16,若要添加的
    字符串长度（count+str.length()）<=(value*2+2)则按value2+2长度扩容，并且value=value\2+2，若（count+str.length()）>(value*2+2)，则按count+str.length()长度扩容，并且value=count+str.length()。下次超出时再按以上方法与value*2+2比较扩容。

    1
    2
    3
    4
    5
    private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int newCapacity = (value.length << 1) + 2;
    if (newCapacity - minCapacity < 0) {
    newCapacity = minCapacity;

StringBuilder:

1
2
3
4
5
6
7
8
9
10
11
public final class StringBuilder
extends AbstractStringBuilder
implements java.io.Serializable, CharSequence
public StringBuilder() {
super(16);
}
private int newCapacity(int minCapacity) {
// overflow-conscious code
int newCapacity = (value.length << 1) + 2;
if (newCapacity - minCapacity < 0) {
newCapacity = minCapacity;
  1. StringBuilder是jdk1.5引进的，而StringBuffer在1.0就有了
  2. StringBuilder和StringBuffer都是可变的字符串。能够通过append或者insert等方法改动串的内容；
  3. StringBuffer是线程安全的而StringBuilder不是，因而在多线程的环境下优先使用StringBuffer，而其它情况下推荐使用
    StringBuilder，由于它更快。
  4. StrngBuilder和StringBuffer都继承自AbstractStringBuilder类，AbStractStringBuilder主要实现了扩容、append、
    insert方法。StrngBuilder和StringBuffer的相关方法都直接调用的父类。
  5. StringBuilder和StringBuffer的初始容量都是16,程序猿尽量手动设置初始值。以避免多次扩容所带来的性能问题；
  6. StringBuilder和StringBuffer的扩容机制是这种：首先试着将当前数组容量扩充为原数组容量的2倍加上2，假设这个新容
    量仍然小于预定的最小值（minimumCapacity），那么就将新容量定为（minimumCapacity），最后推断是否溢出，若溢出，
    则将容量定为整型的最大值0x7fffffff。

Thanks!