java集合源码分析

一、java集合

1.ArrayList源码

前置声明
1
2
3
4
5
6
7
8
9
10
// 默认数组长度
private static final int DEFAULT_CAPACITY = 10;
// 空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默认空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 数组
transient Object[] elementData; // non-private to simplify nested class access
// 集合大小
private int size;
初始化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 指定初始容量的构造
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
      	this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
      	this.elementData = EMPTY_ELEMENTDATA;
    } else {
      	throw new IllegalArgumentException("Illegal Capacity: "+
                                         initialCapacity);
    }
}

// 默认空初始化---懒加载
public ArrayList() {
  	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

// 传入实现了Collection接口的对象
public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
           elementData = a;
        } else {
         	 elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}
add操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 最常用方式
public boolean add(E e) {
    // 确定容量 动态扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 进数组
    elementData[size++] = e;
    return true;
}

// 指定位置插入，不常用
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

// 确定数组大小并决定是否扩容
private void ensureCapacityInternal(int minCapacity) {
  	ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 计算较大值 minCapacity是size+1
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
      	return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
  	return minCapacity;
}
// 确定是否需要扩容 
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // 内存不足，需要扩容
    if (minCapacity - elementData.length > 0)
      	grow(minCapacity);
}
// 扩容 每次扩容1.5倍
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);// 新数组长度 = 1.5 * 旧数组长度
    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); // 复制到新数组
}

为什么ArrayList每次扩容容积都要变成原来的1.5倍呢？

在ArrayList的实现中，每次扩容容量都会增加原来容量的一半。这个增量的选择是为了在避免频繁扩容和节省内存之间寻求一个平衡点。

具体来说，如果每次只增加一个固定的值，那么当需要容纳大量元素时，ArrayList可能会不断地进行扩容操作，这会导致额外的内存分配和复制元素的开销。而如果每次增加原容量的比例太小，那么ArrayList可能需要频繁进行扩容操作，这同样会导致不必要的开销。

因此，1.5倍的增量选择是一种折中方案，既可以避免过于频繁的扩容操作，又可以减少额外的内存分配和元素复制的开销。同时，这个增量值也可以根据实际情况进行调整。

get方法
1
2
3
4
public E get(int index) {
  	rangeCheck(index); // 检查是否数组越界
  	return ArrayList.this.elementData(offset + index);
}

在多线程环境下，如果一个线程修改了集合中的元素，而另一个线程正在遍历这个集合，就可能会导致遍历出错。为了避免这种情况的发生，ArrayList类提供了checkForComodification方法，用于检测集合是否在遍历过程中被修改过。

modCount变量表示ArrayList被修改的次数，每次修改（增加或删除元素）时modCount会自增

set方法
1
2
3
4
5
6
public E set(int index, E e) {
    rangeCheck(index); // 检查是否越界
    E oldValue = ArrayList.this.elementData(offset + index); // 获取原来下标对应的值
    ArrayList.this.elementData[offset + index] = e;
    return oldValue;
}
remove方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;// 要移动元素个数
    if (numMoved > 0)
        // 从删除位置往后拷贝删除
        System.arraycopy(elementData, index+1, elementData, index,
                       	numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

2.LinkedList源码

前置声明
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 数组大小
transient int size = 0;
// 头节点
transient Node<E> first;
// 尾节点
transient Node<E> last;

// 封装的节点类型
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}
初始化
1
2
3
4
5
6
7
8
// 空构造器
public LinkedList() {
}
// 传入实现Collection接口的其他对象
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}
add方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 新增单个节点
public boolean add(E e) {
    linkLast(e);
    return true;
}

// 尾插法插入新节点
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
      	first = newNode;
    else
      	l.next = newNode;
    size++;
    modCount++;
}
get方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 获取index位置数值
public E get(int index) {
    checkElementIndex(index); // 检查是否越界
    return node(index).item;
}

// 遍历查找
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
          	x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
          	x = x.prev;
        return x;
    }
}
set方法
1
2
3
4
5
6
7
public E set(int index, E element) {
    checkElementIndex(index); // 检查越界
    Node<E> x = node(index); // 找到节点
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}
remove方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 删除某一坐标节点
 public E remove(int index) {
     checkElementIndex(index);
     return unlink(node(index)); // node找到index位置的节点
 }

 // 删除节点
 E unlink(Node<E> x) {
     // assert x != null;
     final E element = x.item;
     final Node<E> next = x.next;
     final Node<E> prev = x.prev;

     if (prev == null) {
         first = next;
     } else {
         prev.next = next;
         x.prev = null;
     }

     if (next == null) {
         last = prev;
     } else {
         next.prev = prev;
         x.next = null;
     }

     x.item = null;
     size--;
     modCount++;
     return element;
 }

3.HashMap源码

前置声明
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// 默认容初始量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

  // 最大容量
  static final int MAXIMUM_CAPACITY = 1 << 30;

  // 默认负载因子
  static final float DEFAULT_LOAD_FACTOR = 0.75f;

  // 转红黑树阈值
  static final int TREEIFY_THRESHOLD = 8;

  // 扩容后树转链表阈值
  static final int UNTREEIFY_THRESHOLD = 6;

  // 最小树化数组阈值
  static final int MIN_TREEIFY_CAPACITY = 64;

  // 封装的节点---hashmap中数据都以Node结构存储在桶中
  static class Node<K,V> implements Map.Entry<K,V> {
  		final int hash;
      final K key;
      V value;
      Node<K,V> next;

      Node(int hash, K key, V value, Node<K,V> next) {
          this.hash = hash;
          this.key = key;
          this.value = value;
          this.next = next;
      }

      public final K getKey()        { return key; }
      public final V getValue()      { return value; }
      public final String toString() { return key + "=" + value; }

      public final int hashCode() {
          return Objects.hashCode(key) ^ Objects.hashCode(value);
      }

      public final V setValue(V newValue) {
          V oldValue = value;
          value = newValue;
          return oldValue;
      }

      public final boolean equals(Object o) {
          if (o == this)
              return true;
          if (o instanceof Map.Entry) {
              Map.Entry<?,?> e = (Map.Entry<?,?>)o;
              if (Objects.equals(key, e.getKey()) &&
                  Objects.equals(value, e.getValue()))
                  return true;
          }
          return false;
      }
  }

// 散列函数 使用 扰动函数 将哈希值进一步打乱
  static final int hash(Object key) {
      int h;
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }
初始化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 指定初始化容量与负载因子---很少使用
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;
     this.threshold = tableSizeFor(initialCapacity);
 }

 // 指定初始化容量---用于知道hashmap大概要存储多少数据时
 public HashMap(int initialCapacity) {
     this(initialCapacity, DEFAULT_LOAD_FACTOR);
 }

 // 默认构造方法，使用默认负载因子
 public HashMap() {
     this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
 }

 // 传进来一个map初始化
 public HashMap(Map<? extends K, ? extends V> m) {
     this.loadFactor = DEFAULT_LOAD_FACTOR;
     putMapEntries(m, false);
 }
put方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// put方法，本质是调用putVal
public V put(K key, V value) {
      return putVal(hash(key), key, value, false, true);
  }
// 实际上实现put方法的地方
  /********onlyIfAbsent – if true, don't change existing value********/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                 boolean evict) {
    	// tab就是哈希桶，也就是数组+链表中的数组部分 p用来指向key对应的桶位置节点
      Node<K,V>[] tab; Node<K,V> p; int n, i;
    	// 未初始化，先resize进行初始化
      if ((tab = table) == null || (n = tab.length) == 0)
          n = (tab = resize()).length;
    	// p指向要插入的桶节点位置，判断当前位置是否为空，为空直接把value封装放进去
     // (n - 1) & hash 这一步很妙，与double扩容配合可以使得扩容时，节点要么不移动桶位置，要么+原数组长度移动
      if ((p = tab[i = (n - 1) & hash]) == null) 
          tab[i] = newNode(hash, key, value, null);
      else {
        	// 存在哈希冲突 e是要插入的位置，如果已存在这个key，e就指向这个key对应的节点
          Node<K,V> e; K k;
        	// 桶处的根节点和插入的key相等，直接把e指向p
          if (p.hash == hash &&
              ((k = p.key) == key || (key != null && key.equals(k))))
              e = p;
        	// 如果桶位置已经树化，调用树的putTreeVal方法
          else if (p instanceof TreeNode)
              e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 树版本的putVal
          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;
                  }
                // 找到已存在key对应节点
                  if (e.hash == hash &&
                      ((k = e.key) == key || (key != null && key.equals(k))))
                      break;
                  p = e;
              }
          }
        	// key已存在，替换value
          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);  // Callbacks to allow LinkedHashMap post-actions
      return null;
  }

// 尝试将链表树化
  final void treeifyBin(Node<K,V>[] tab, int hash) {
      int n, index; Node<K,V> e;
    	// 如果数组长度未达阈值（64），则先进行数组扩容
      if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
          resize();
      else if ((e = tab[index = (n - 1) & hash]) != null) {
          TreeNode<K,V> hd = null, tl = null;
          do {
              TreeNode<K,V> p = replacementTreeNode(e, null);
              if (tl == null)
                  hd = p;
              else {
                  p.prev = tl;
                  tl.next = p;
              }
              tl = p;
          } while ((e = e.next) != null);
          if ((tab[index] = hd) != null)
              hd.treeify(tab);
      }
  }
resize方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
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
      }
      else if (oldThr > 0) // initial capacity was placed in threshold
          newCap = oldThr;
      else {               // zero initial threshold signifies using defaults
          newCap = DEFAULT_INITIAL_CAPACITY;
          newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
      }
      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;
      if (oldTab != null) { // 初始时不需要复制
          for (int j = 0; j < oldCap; ++j) {
              Node<K,V> e;
              if ((e = oldTab[j]) != null) {
                  oldTab[j] = null;
                  if (e.next == null)
                    	// 桶中元素就一个 找到元素新位置赋值
                      newTab[e.hash & (newCap - 1)] = e;
                  else if (e instanceof TreeNode)
                    	// 移动树
                      ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                  else { // preserve order
                      Node<K,V> loHead = null, loTail = null;
                      Node<K,V> hiHead = null, hiTail = null;
                      Node<K,V> next;
                      do {
                          next = e.next;
                          if ((e.hash & oldCap) == 0) {
                              if (loTail == null)
                                  loHead = e;
                              else
                                  loTail.next = e;
                              loTail = e;
                          }
                          else {
                              if (hiTail == null)
                                  hiHead = e;
                              else
                                  hiTail.next = e;
                              hiTail = e;
                          }
                      } while ((e = next) != null);
                      if (loTail != null) {
                          loTail.next = null;
                          newTab[j] = loHead;
                      }
                      if (hiTail != null) {
                          hiTail.next = null;
                          newTab[j + oldCap] = hiHead;
                      }
                  }
              }
          }
      }
      return newTab;
  }
get方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 获取key对应值
public V get(Object key) {
      Node<K,V> e;
      return (e = getNode(hash(key), key)) == null ? null : e.value;
  }

// 实际调用方式
  final Node<K,V> getNode(int hash, Object key) {
    	// first是哈希后桶位置上第一个节点
      Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
      if ((tab = table) != null && (n = tab.length) > 0 &&
          (first = tab[(n - 1) & hash]) != null) {
        	// 直接找到
          if (first.hash == hash && // always check first node
              ((k = first.key) == key || (key != null && key.equals(k))))
              return first;
          if ((e = first.next) != null) {
            	// 遍历树
              if (first instanceof TreeNode)
                  return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            	// 遍历链表
              do {
                  if (e.hash == hash &&
                      ((k = e.key) == key || (key != null && key.equals(k))))
                      return e;
              } while ((e = e.next) != null);
          }
      }
      return null;
  }
remove方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
  public V remove(Object key) {
      Node<K,V> e;
      return (e = removeNode(hash(key), key, null, false, true)) == null ?
          null : e.value;
  }
// 找到节点，删除即可，注意树结构删除节点之后可能会退化
final Node<K,V> removeNode(int hash, Object key, Object value,
                             boolean matchValue, boolean movable) {
      Node<K,V>[] tab; Node<K,V> p; int n, index;
      if ((tab = table) != null && (n = tab.length) > 0 &&
          (p = tab[index = (n - 1) & hash]) != null) {
          Node<K,V> node = null, e; K k; V v;
          if (p.hash == hash &&
              ((k = p.key) == key || (key != null && key.equals(k))))
              node = p;
          else if ((e = p.next) != null) {
              if (p instanceof TreeNode)
                  node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
              else {
                  do {
                      if (e.hash == hash &&
                          ((k = e.key) == key ||
                           (key != null && key.equals(k)))) {
                          node = e;
                          break;
                      }
                      p = e;
                  } while ((e = e.next) != null);
              }
          }
          if (node != null && (!matchValue || (v = node.value) == value ||
                               (value != null && value.equals(v)))) {
              if (node instanceof TreeNode)
                  ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
              else if (node == p)
                  tab[index] = node.next;
              else
                  p.next = node.next;
              ++modCount;
              --size;
              afterNodeRemoval(node);
              return node;
          }
      }
      return null;
  }

4.modCount与FailFast机制

上面三个类里面，都有monCount变量，那么这个变量是什么，有什么用处呢？

在 Java 集合中，modCount 是用于实现“快速失败”机制的一个计数器，用于跟踪集合对象自创建以来所发生的修改次数。当通过迭代器遍历集合时，如果在迭代过程中发现集合的 modCount 发生了变化，就会立即抛出 ConcurrentModificationException 异常，以避免并发修改导致的数据不一致问题。

快速失败机制的目的是为了保证多个线程并发操作同一个集合时的数据一致性。如果不使用快速失败机制，可能会导致数据不一致，而且这种不一致的结果可能是不可预测的。

因此，集合类在实现迭代器时，通常会在每次进行修改（新增，删除，更新）操作时，将 modCount 的计数器加 1，以便在下次迭代时检测到修改操作，抛出异常以提醒程序员代码存在问题。同时，这也是 Java 集合框架的一个核心设计原则之一，即在多线程环境中保证数据的一致性。

5.Vector

和ArrayList很相似，都是以动态数组的形式来存储数据，但是它是线程安全的，Vector的线程安全来自于每一个操作方法都加上了synchronized关键字，对性能来说有较大影响，目前属于逐渐废弃的方法

而对于ArrayList这种非线程安全的数组，可以使用Collections工具来实现线程安全，比Vector更加安全

1
List syncList = Collections.synchronizedList(list);

本质上是工具类为原方法封装了加锁的同步代码块

1
2
3
4
5
6
7
8
9
10
11
12
public E get(int index) {
    synchronized (mutex) {return list.get(index);}
}
public E set(int index, E element) {
    synchronized (mutex) {return list.set(index, element);}
}
public void add(int index, E element) {
    synchronized (mutex) {list.add(index, element);}
}
public E remove(int index) {
    synchronized (mutex) {return list.remove(index);}
}