本篇博客内容主要是集合内容的介绍，包括：
Collection下的List,Set相关的集合
Map的相关集合
关于TreeSet和TreeMap内部实现(红黑树)的部分有时间再补上。
整理不易，可累死仙鱼我了，看完有收获的话记得点赞欧~

Collection

1 List

1.1 ArrayList

1.1.1 类说明

ArrayList是继承AbstractList抽象类，实现List，RandomAccess，Cloneable，lava.io.Serializable接口的数组队列，相当于动态数组，容量可以动态增长，地址空间连续。
java
1
2
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
实现RandomAccess接口使ArrayList支持快速随机访问查询。

如下，RandomAccess接口中是没有任何实现的(Cloneable，Serializable也是)，就相当于给ArrayList做了一个可以快速随机访问的标识，因为ArrayList的底层实现是Object数组才支持快速随机访问。
java
1
2
public interface RandomAccess {
}
ArrayList不是线程安全的，建议在单线程中使用，多线程情况下可以选择使用Vector(这个都快弃用了)或者CopyOnWirteArrayList。

1.1.1 内部结构

1.1.1.1 初始化

初始化(构造时)，默认的数组初始化容量大小为10：

调用无参的构造方法进行只是进行了数组的初始化，这个时候并没有分配容量，当添加第一个元素，调用add(E e)方法时，会初始化数组容量大小为10；

java

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //0
// Object数组
transient Object[] elementData;
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/***************************************************************************************************/
private static final int DEFAULT_CAPACITY = 10; //10
private int size;
// 将指定元素追加到此列表的末尾
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
// 得到最小扩容量
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //小于10则返回默认容量
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        //调用grow方法进行扩容，调用此方法代表已经开始扩容了
        grow(minCapacity);
}

1.1.1.2 扩容

扩容：如当前数组长度为10，来了第十一个元素，就要就行扩容

java

// minCapacity 所需的最小容量
public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}
// 判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        // 扩容的核心方法
        grow(minCapacity);
}
// 需要分配的最大数组的大小
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// ArrayList扩容的核心方法
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // newCapacity为旧容量oldCapacity的1.5倍，oldCapacity >> 1 等价于 oldCapacity/2
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 新容量小于最小需求量，则最小需求量为数组的新容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 新容量是否大于ArrayList所定义的最大容量
    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所定义的最大容量时，比较最小需求量和MAX_ARRAY_SIZE
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

1.1.1.3 删除元素

删除该列表中指定位置的元素。将任何后续元素向左移动一位（从其索引中减去一个元素）。

java

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

1.1.1.4 copyOf()和arraycopy()

Arrays.copyOf()和System.arraycopy():

联系：看两者源代码可以发现 copyOf() 内部实际调用了 System.arraycopy()方法

java

public static  T[] copyOf(U[] original, int newLength, Class newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

区别：arraycopy() 需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置。copyOf() 是系统自动在内部新建一个数组，并返回该数组。

1.2 Vector

1.2.1 类说明

Vector继承了AbstractList抽象类，实现了List，RandomAccess，Cloneable，java.io.Serializable接口，底层实现也是动态数组，和ArrayList不同的是Vector是线程的，Vector中的很多方法使用synchronized关键字进行了同步加锁操作。这个类现在使用的很少了。
java
1
2
3
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
其他的内容和ArrayList差不多，不再赘述。

1.2.2 内部结构

1.2.2.1 初始化

调用Vector的无参构造方法，默认的初始化大小为10：注意ArrayList调用无参的构造方法时并没有分配大小，在第一次add的时候，初始化大小为10，而Vector调用无参的构造方法时，直接初始化数组大小为10，注意区分。
java
1
2
3
public Vector() {
this(10);
}

1.2.2.2 扩容

Vector的扩容和ArrayList的扩容基本一致

java

// 调用add(E e)/add(int index, E element)都会进行是否要扩容的判断，这里仅以add(E e)为例
public synchronized boolean add(E e) {
    modCount++;
    // 判断是否普需要扩容
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}
// 判断是否需要扩容
private void ensureCapacityHelper(int minCapacity) {
    // 若最小期望容量比实际的数组容量大，说明数组长度不够，就需要扩容
    if (minCapacity - elementData.length > 0)
        // 扩容的核心方法
        grow(minCapacity);
}
// 扩容
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);
}

1.2.2.3 删除元素

删除元素和ArrayList基本一致

java

public synchronized E remove(int index) {
    modCount++;
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);

    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--elementCount] = null; // Let gc do its work

    return oldValue;
}

1.3 LinkedList

1.3.1 类说明

LinkedList是一个继承了AbstractSequentialList抽象类实现了List和Deque，Cloneable，java.io.Serializable的双端链表（双向链表）。
java
1
2
3
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList底层的链表结构(双向链表，长度没有限制，在JDK1.7之前底层为双向循环链表，在JDK1.7的时候去掉了循环，双向循环链表和双向链表的区别就在于首尾节点是否相连)使它支持高效的插入和删除操作，另外它实现了Deque接口(Deque接口继承了Queue接口)，使得LinkedList类也具有队列的特性;
LinkedList不是线程安全的，如果想使LinkedList变成线程安全的，可以调用静态类Collections类中的synchronizedList方法：
java
1
List list=Collections.synchronizedList(new LinkedList(...));

1.3.2 内部结构

底层是双向链表，如下图：

LinkedList源码中有一个内部私有类，描述了双端链表的节点Node，可知Node包含三个属性：前驱节点，节点值，后继节点，如下：

java

private static class Node<E> {
    E item;//节点值
    Node next;//后继节点
    Node prev;//前驱节点
    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

链表的操作头插啊尾插啊，中间插入啊，删除啊等就不介绍了，都是比较基础的数据结构的知识。

2 Set

2.1 HashSet

2.1.1 类说明

HashSet继承AbstractSet抽象类，实现Set，Cloneable，java.io.Serializable接口。

java

1
2
3

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

存放的元素是无序的，不可重复的，它维持它自己的内部排序，所以随机访问没有任何意义。允许存放null值，底层封装HashMap（是基于HashMap实现的，最终依然使用数组存储数据）所以也是不同步的线程不安全的。
java
1
2
// 保障线程安全
Collections.synchronizedSet(new HashSet(...));

2.1.2 内部结构

就是一个元素不重复的HashMap(HashMap的详细介绍在下面)，可以看到HashSet的构造方法是直接new的HashMap。

java

private transient HashMap map;
public HashSet() {
    map = new HashMap<>();
}
public HashSet(Collection c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    // 看到LinkedHashMap莫慌，LinkedHashMap的构造也是调用父类HashMap的构造实现的
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

那么，是如何保障元素的不重复呢？

很简单，HashMap中的key保障了唯一，使所有的value对应一个内部的对象PRESENT即可。

java

// 定义value对应的唯一内部对象
private static final Object PRESENT = new Object();
// HashMap的put方法如果该位置已经存在一个一样的Key（==或者equals相等），会用新的value替换原来的旧的value，并且返回旧的value，所以对于HashSet而言第一次插入返回null就代表成功，以后再次插入同样的元素，返回的是一个对象，表示已经存在这样的元素了，插入失败！
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

2.2 LinkedHashSet

2.2.1 类说明

LinkedHashSet继承了HashSet类，实现了Set，Cloneable，java.io.Serializable接口。

java

1
2
3

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

因为实现了Set接口，所以具有Set集合元素不重复的特点，同时具有可预测的迭代顺序，也就是我们插入的顺序(默认)。
LinkedHashSet源码中的方法非常简单，是基于LinkedHashMap实现的(LinkedHashMap下面有详细的介绍)。
LinkedHashSet是有序的，它是按照插入的顺序排序的。

2.2.2 内部结构

2.2.2.1 初始化

调用LinkedHashSet默认的构造方法(无参)，可以得知，初始化大小为16。
java
1
2
3
public LinkedHashSet() {
super(16, .75f, true);
}

基于LinkedHashMap实现的证据：

打开LinkedHashSet的源码你可能首先会有一点懵逼，因为里面一共就一个静态常量，四个构造方法和一个重写的切分的方法。而且构造方法上是super，也看不出是基于什么父类实现的，如下：

java

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}
public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}
public LinkedHashSet() {
    super(16, .75f, true);
}
public LinkedHashSet(Collection c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}

但是别慌，按住Ctrl，点进super，你会发现都是基于同一个方法实现的，如下，可以看出，是直接new了一个LinkedHashMap，所以现在知道为什么说是基于LinkedHashMap实现了的不。

java

1
2
3

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

同时，基于好奇心我又点进了LinkedHashMap，看到了下面的类：

java

public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

看到了一句很关键的话：accessOrder = false，这里写死了就让accessOrder为false，也就是说，LinkedHashSet是不支持按访问顺序对元素排序的，只能按插入顺序排序。

后面会介绍LinkedHashMap，就不赘述了，好，下一个！

2.3 TreeSet

2.3.1 类说明

TreeSet继承了AbstractSet抽象类，实现了NavigableSet，Cloneable，java.io.Serializable接口，就像HashSet是基于HashMap实现的一样，TreeSet是基于TreeMap实现的(后面有TreeMap的介绍)，可以说TreeSet的底层是自平衡的排序二叉树(红黑树)。
java
1
2
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
TreeSet实现了NavigableSet接口，而NavigableSet接口继承SortedSet接口，所以是一个有序的集合，它的作用是提供有序的Set集合。
TreeSet的元素支持2种排序方式：自然排序或者根据提供的Comparator进行排序。

2.3.2 内部结构

Map

1 HashMap

1.1 类说明

HashMap继承AbstractMap抽象类，实现Map，Cloneable，Serializable接口，主要用于存放键值对。
java
1
2
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
在JDK1.8之前的HashMap是由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的(拉链法解决冲突)，在JDK1.8之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值(默认是8)时，将链表转化为红黑树，可以减少搜索时间。
HashMap是非线程安全的，若要保证线程安全，可以使用 ConcurrentHashMap 。
HashMap可以存储一个Key为null，多个value为null的元素。

1.2 内部结构：

1.2.1 初始化

先看一下HashMap的无参构造方法，如下：

java

static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
 * Constructs an empty HashMap with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

乍一看HashMap的无参构造方法只是简单的指定了哈希表的加载因子，并没有定义初始化容量，但是这个构造方法上面的注释说：初始化容量大小为16，于是找啊找，终于找到了，原来是直接定义了一个常量，默认为16。

java

/**
 * 1 << 4 :表示1左移4为，即2的4次方，那可不就是16嘛
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

1.2.2 hash()的变化

hash()：先说一下hash()方法的变化，从下面的代码可以看出，1.8之后的性能更高，毕竟只有一次>>>

JDK1.8之前的hash():

java

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

JDK1.8之后的hash():

java

// key.hashCode()返回散列值，即hashcode
// >>>:无符号右移，忽略符号位，空位都以0补齐
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

1.2.3 存储结构

1.8之后的存储结构：数组+链表+红黑树，大致如下图：

数组：Node[] table，即哈希桶数组，存储了头节点的table数组，HashMap就是使用哈希表实现的：

java

transient Node[] table;
// 实现了Map.Entry接口，本质上就是一个键值对
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node next;
    Node(int hash, K key, V value, Node 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;
    }
}

1.2.4 put()方法

以向HashMap中添加数据为例介绍以下几个操作：插入是在链表的尾部插入。

java

// 调用put()方法
  public V put(K key, V value) {
      return putVal(hash(key), key, value, false, true);
  }
  // 调用putVal()方法之前调用了hash()，获取key对应的hashcode
  static final int hash(Object key) {
      int h;
      // 可以看到 取到hashcode后 和自己本身的高16位做了亦或操作，是为了使hashcode的生成更加散列
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }
  // 接下来调用putVal()方法进行具体的插入数据
  final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
      Node[] tab; Node p; int n, i;
      // 判断table是否进行了初始化
      if ((tab = table) == null || (n = tab.length) == 0)
          // table初始化，即扩容
          n = (tab = resize()).length;
      // 将新生成的hashcode和table的长度n-1做&操作，获取该节点在数据中的下标
      // 如果数组中该位置没有数据，则根据传入的值生成新node节点
      if ((p = tab[i = (n - 1) & hash]) == null)
          tab[i] = newNode(hash, key, value, null);
      else { // 该位置上已经存在其他节点(上面if操作已经对p进行了赋值，为tab[(n-1)&hash])
          Node e; K k;
          // 判断已经存在的节点数据和新传入的节点key和hash值是否相同
          if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
              e = p;
          // 判断是否是一个树节点，若是，直接在红黑树中插入键值对
          else if (p instanceof TreeNode)
              e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
          else { //  已存在节点的key和新增的key不相同，发生hash冲突
              // 将新节点放入该节点链表的最后
              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;
                  }
                  // 在将新节点放置在链表最后位置后，终止循环
                  if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                      break;
                  p = e;
              }
          }
          // 定位到put数据位置，进行value赋值操作
          if (e != null) { // existing mapping for key
              V oldValue = e.value; // 获取key 对应节点的原来数据
              if (!onlyIfAbsent || oldValue == null)
                  e.value = value; // 重新赋值
              afterNodeAccess(e);
              return oldValue; // 返回节点原数据
          }
      }
      // 没有发生hash冲突，数组的某个位置被占用，hashMap 结构修改次数 
      ++modCount;
      // 数组已经被占用数量++，自增后判断当前数组是否需要扩容
      if (++size > threshold)
          resize();
      afterNodeInsertion(evict);// LinkedHashMap 方法
      return null;
  }
  // TreeNode节点
  static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
      TreeNode parent;  // red-black tree links
      TreeNode left;
      TreeNode right;
      TreeNode prev;    // needed to unlink next upon deletion
      boolean red;
      TreeNode(int hash, K key, V val, Node next) {
          super(hash, key, val, next);
      }
      /**
           * Returns root of tree containing this node.
           */
      final TreeNode root() {
          for (TreeNode r = this, p;;) {
              if ((p = r.parent) == null)
                  return r;
              r = p;
          }
      }
  }

1.2.5 get()方法

那么又是如何获取数据的呢？

java

// 调用get()方法，通过key获取
public V get(Object key) {
    Node e;
    // 计算key对应的hashcode值，去获取节点
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// 获取节点
final Node getNode(int hash, Object key) {
    Node[] tab; Node first, e; int n; K k;
    // 数组不为空，长度部位0并且有元素
    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)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);
        }
    }
    // 否则，没有这个节点，返回null
    return null;
}
// 获取树节点，源码就放到这里，不再深入了
final TreeNode getTreeNode(int h, Object k) {
    return ((parent != null) ? root() : this).find(h, k, null);
}

2 Hashtable

2.1 类说明

Hashtable继承了Dictionary抽象类，实现了Map，Cloneable，java.io.Serializable接口，虽然和HashMap同样都属于散列表，但使用的情况很少。
java
1
2
3
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializables
唯一一点优于HashMap是：Hashtable是线程安全的。但是想在多线程下使用散列表的话还是建议使用上面说过的ConcurrentHashMap来替换Hashtable。
Hashtable不允许key或者value为null。

2.2 内部结构

2.2.1 初始化

初始化（无参构造方法）：Hashtable默认capacity是11，默认负载因子是0.75f。
java
1
2
3
public Hashtable() {
this(11, 0.75f);
}

2.2.2 存储结构

Hashtable的底层是：Entry数组+链表实现的，结构如下图：

java

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

    protected Entry(int hash, K key, V value, Entry next) {
        this.hash = hash;
        this.key =  key;
        this.value = value;
        this.next = next;
    }

    @SuppressWarnings("unchecked")
    protected Object clone() {
        return new Entry<>(hash, key, value,
                           (next==null ? null : (Entry) next.clone()));
    }

    // Map.Entry Ops

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }

    public V setValue(V value) {
        if (value == null)
            throw new NullPointerException();

        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }

    public boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry e = (Map.Entry)o;

        return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
            (value==null ? e.getValue()==null : value.equals(e.getValue()));
    }

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

    public String toString() {
        return key.toString()+"="+value.toString();
    }
}

2.2.3 put()方法

与HashMap不同的是这里会对value进行是否为空的校验，节点为Entry节点，没有红黑树（看着很像JDK1.8之前的HashMap）

并且HashMap是在链表的尾部插入元素，而Hashtable是在链表的头部插入元素，可能是因为没有HashMap的红黑树机制，如果要在尾部添加元素的话可能需要遍历大量的数据(链表的长度没有限制)。

java

public synchronized V put(K key, V value) {
    // Make sure the value is not null
    if (value == null) {
        throw new NullPointerException();
    }
    // Makes sure the key is not already in the hashtable.
    Entry tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry entry = (Entry)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;
}
private void addEntry(int hash, K key, V value, int index) {
    modCount++;

    Entry tab[] = table;
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();

        tab = table;
        hash = key.hashCode();
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    @SuppressWarnings("unchecked")
    Entry e = (Entry) tab[index];
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

2.2.4 get()方法

根据key获取数据的方法如下，是线程安全的：

java

public synchronized V get(Object key) {
    // 获得hashtable数组
    Entry tab[] = table;
    // 获得key对应的hashcode
    int hash = key.hashCode();
    // 根据当前key的hashcode计算出在hashtable数组中对应的下标
    int index = (hash & 0x7FFFFFFF) % tab.length;
    // 获取对应的链表，遍历找到匹配的hash取值返回
    for (Entry e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    // 否则返回null
    return null;
}

3 LinkedHashMap

3.1 类说明

LinkedHashMap继承了HashMap类，实现了Map接口。可以说LinkedHashMap是基于HashMap和双向链表来实现的。
java
1
2
3
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
LinkedHashMap是线程不安全的。
我们知道HashMap是无序的，内部是数组+单链表，而LinkedHashMap由于底层是数组+双向链表，从而保障了LinkedHashMap是有序的，且默认为插入顺序(无参构造默认accessOrder = false)。

3.2 内部结构

3.2.1 初始化

LinkedHashMap使用父类的构造方法初始化，我们在上面说过，其父类HashMap调用无参的构造方法进行初始化的时候，默认的初始化大小为16，那么LinkedHashMap调用无参方法进行初始化的时候的初始大小也是16。

java

public LinkedHashMap() {
    super();
    // true表示访问顺序，false表示插入顺序
    accessOrder = false;
}
/**
 * Constructs an empty HashMap with the default initial capacity
 * (16) and the default load factor (0.75).
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// 多了一个前驱后继的Entry
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry before, after;
    Entry(int hash, K key, V value, Node next) {
        super(hash, key, value, next);
    }
}

上面的初始化过程可用下面的图表示：

3.2.2 存储结构：

先看一下HashMap的存储结构：
再看一下LinkedHashMap的存储结构对比一下区别：

3.2.3 put()方法

LinkedHashMap并没有重写自己的put()方法，而是直接调用父类HashMap中的put方法，只是重写了newNode()方法，代码如下：

java

// 父类HashMap中的方法
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
// 父类HashMap中的方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node[] tab; Node p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        // LinkedHashMap中重写了newNode()方法
        tab[i] = newNode(hash, key, value, null);
    else {
        Node e; K k;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
        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;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        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);// LinkedHashMap 方法
    return null;
}
// 父类HashMap中的newNode()方法
Node newNode(int hash, K key, V value, Node next) {
    return new Node<>(hash, key, value, next);
}
// LinkedHashMap中重写了此方法
Node newNode(int hash, K key, V value, Node e) {
    LinkedHashMap.Entry p =
        new LinkedHashMap.Entry(hash, key, value, e);
    linkNodeLast(p);
    return p;
}
// LinkedHashMap中实现
private void linkNodeLast(LinkedHashMap.Entry p) {
    LinkedHashMap.Entry last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        // 将新节点 p 接在链表尾部
        p.before = last;
        last.after = p;
    }
}

3.2.4 get()方法

LinkedHashMap重写了get方法，默认是按照插入顺序查询

java

// LinkedHashMap 中覆盖
public V get(Object key) {
    Node e;
    // 默认是按照插入顺序查询的
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 如果为true表示按照访问顺序查询
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}
// 父类HashMap中的方法
final Node getNode(int hash, Object key) {
    Node[] tab; Node 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)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;
}
// LinkedHashMap中覆盖 
void afterNodeAccess(Node e) { // move node to last
    LinkedHashMap.Entry last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry p =
            (LinkedHashMap.Entry)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

4 TreeMap

4.1 类结构

TreeMap继承了AbstractMap抽象类，实现了NavigableMap，Cloneable，java.io.Serializable接口。

java

1
2
3

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

是一个有序的，非同步的，基于红黑树实现，该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。

Collection

1 List

1.1 ArrayList

1.1.1 类说明

1.1.1 内部结构

1.1.1.1 初始化

1.1.1.2 扩容

1.1.1.3 删除元素

1.1.1.4 copyOf()和arraycopy()

1.2 Vector

1.2.1 类说明

1.2.2 内部结构

1.2.2.1 初始化

1.2.2.2 扩容

1.2.2.3 删除元素

1.3 LinkedList

1.3.1 类说明

1.3.2 内部结构

2 Set

2.1 HashSet

2.1.1 类说明

2.1.2 内部结构

2.2 LinkedHashSet

2.2.1 类说明

2.2.2 内部结构

2.2.2.1 初始化

2.3 TreeSet

2.3.1 类说明

2.3.2 内部结构

Map

1 HashMap

1.1 类说明

1.2 内部结构：

1.2.1 初始化

1.2.2 hash()的变化

1.2.3 存储结构

1.2.4 put()方法

1.2.5 get()方法

2 Hashtable

2.1 类说明

2.2 内部结构

2.2.1 初始化

2.2.2 存储结构

2.2.3 put()方法

2.2.4 get()方法

3 LinkedHashMap

3.1 类说明

3.2 内部结构

3.2.1 初始化

3.2.2 存储结构：

3.2.3 put()方法

3.2.4 get()方法

4 TreeMap

4.1 类结构

4.2 内部结构