目录

• ArrayList
• Vector
• LinkedList
• HashMap
• Hashtable

ArrayList

数据结构：数组

 transient Object[] elementData; // non-private to simplify nested class access  

空参构造函数创建的是一个空数组，当 add 一个元素时，才初始化容量为 DEFAULT_ capacity = 10。

扩容：默认每次扩容1.5倍

 private  void  grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
  // 默认每次扩容1.5倍
    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. copy Of(elementData, newCapacity);
}  

Vector

数据结构：数组

 protected Object[] elementData;
public Vector() {
    this(10);
}  

空参构造函数默认创建容量10

扩容：默认对旧容量翻倍

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

LinkedList

数据结构：双向 链表

 // 指向双向链表的头和尾 
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;
        }
}  

HashMap

数据结构：数组+链表+ 红黑树

 // 数组
transient Node<K,V>[] table;
// 链表
static class Node<K,V> implements Map.Entry<K,V> {
      // 存储 key 的哈希值
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
  // ...
}
// 红黑树
static final class TreeNode<K,V>  extends  LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
         boolean  red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super( hash , key, val, next);
        }
   // ...
 }  

扩容：旧容量翻倍，见 resize 方法。

参数:扩容、链表与红黑树互转

 //默认的初始容量为 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大的容量上限为 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的负载因子为 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//变成树型结构的临界值为 8
static final int TREEIFY_THRESHOLD = 8;
//恢复链式结构的临界值为 6
static final int UNTREEIFY_THRESHOLD = 6;
// 哈希表 中键值对的个数
transient int size;
//哈希表被修改的次数
transient int modCount;
//它是通过 capacity*load factor 计算出来的，当 size 到达这个值时，就会进行扩容操作
int threshold;
//负载因子
final float loadFactor;
//当哈希表的大小超过这个 阈值 ，才会把链式结构转化成树型结构，否则仅采取扩容来尝试减少冲突
static final int MIN_TREEIFY_CAPACITY = 64;  

HashMap 关于红黑树的三个关键参数

方法解析

• hash 方法：计算 key 的哈希值

 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }  

这个 hash 方法先通过 key 的 hashCode 方法获取一个哈希值，再拿这个哈希值与它的高 16 位的哈希值做一个异或操作来得到最后的哈希值。

为啥要这样做呢？注释中是这样解释的：如果当 n 很小，假设为 64 的话，那么 n-1即为 63（0x111111），这样的值跟 hashCode()直接做与操作，实际上只使用了哈希值的后 6 位。如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成冲突了，所以这里把高低位都利用起来，从而解决了这个问题。

• tableSizeFor 方法

把 cap 变成第一个大于等于 2 的幂次方的数。例如，16 还是 16，13 就会调整为 16，17 就会调整为 32。

 static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}  

• resize 方法

HashMap 在进行扩容时，使用的 rehash 方式非常巧妙，因为每次扩容都是翻倍，与原来计算（n-1）&hash 的结果相比，只是多了一个 bit 位，所以节点要么就在原来的位置，要么就被分配到“原位置+旧容量”这个位置。

例如，原来的容量为 32，那么应该拿 hash 跟 31（0x11111）做与操作；在扩容扩到了 64 的容量之后，应该拿 hash 跟 63（0x111111）做与操作。新容量跟原来相比只是多了一个 bit 位，假设原来的位置在 23，那么当新增的那个 bit 位的计算结果为 0时，那么该节点还是在 23；相反，计算结果为 1 时，则该节点会被分配到 23+31 的桶上。正是因为这样巧妙的 rehash 方式，保证了 rehash 之后每个桶上的节点数必定小于等于原来桶上的节点数，即保证了 rehash 之后不会出现更严重的冲突。

Hashtable

数据结构：数组+链表

 private transient Entry<?,?>[] table;
private static class Entry<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Entry<K,V> next;
   // ...
 }  

key 和 value 都不能是 null

 public  synchronized  V put(K key, V value) {
        // value 不能是 null 
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        // key 不能是 null 
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
}  

扩容：翻倍+1

 protected void rehash() {
        int oldCapacity = table.length;
        Entry<?,?>[] oldMap = table;

        // 翻倍+1
        int newCapacity = (oldCapacity << 1) + 1;
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            if (oldCapacity == MAX_ARRAY_SIZE)
                // Keep running with MAX_ARRAY_SIZE buckets
                return;
            newCapacity = MAX_ARRAY_SIZE;
        }
        Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

        modCount++;
        threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
        table = newMap;

        for (int i = oldCapacity ; i-- > 0 ;) {
            for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
                Entry<K,V> e = old;
                old = old.next;

                int index = (e.hash & 0x7FFFFFFF) % newCapacity;
                e.next = (Entry<K,V>)newMap[index];
                newMap[index] = e;
            }
        }
}