1. 整体关系图

  Collection
      |---------List
                    |----------ArrayList
                    |----------LinkedList
                    |----------Vector（笔者在开发中用的很少）
      |---------Set
                    |----------HashSet       
                    |----------LinkedHashSet      
                    |----------TreeSet
  Map
      |----------HashMap
                    |----------LinkedMap
      |----------TreeMap

下面，会对这几个实现类做一些说明

2. ArrayList

• 属性

  /**
    * 初始化数组长度,当使用 List<T> list = new ArrayList<>()初始化集合时，第一次调用add方法会将数组长度设置为此值;
    */
 private static final int DEFAULT_CAPACITY = 10;

  /**
   *   当调用构造器方法传递的初始化大小为0或者空集合的时候，elementData为此值
   */
  private static final Object[] EMPTY_ELEMENTDATA = {};

  /**
   *  调用 List<T> list = new ArrayList<>(); 时 elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA
   */
  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

  /**
   *  存放集合数据
   */
  transient Object[] elementData; 

• 构造器

  /**
   *  创建一个给定初始值大小的数组，其中elementData存放真实数据
   */
  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;
  }
  
  /**
    * 将集合的数据放入到此数组中,如果集合为空，则elementData = EMPTY_ELEMENTDATA
    */
  public ArrayList(Collection<? extends E> c) {
      elementData = c.toArray();
      if ((size = elementData.length) != 0) {
          // c.toArray might (incorrectly) not return Object[] (see 6260652)
          if (elementData.getClass() != Object[].class)
              elementData = Arrays.copyOf(elementData, size, Object[].class);
      } else {
          // replace with empty array.
          this.elementData = EMPTY_ELEMENTDATA;
      }
  }
  

• 添加

    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 void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    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);
    }

通过上面的方法不难看到，在调用add方法时，会首先进行数组大小检查，当使用new ArrayList 构造方法时，默认数组长度取DEFAULT_CAPACITY（10），调用grow()方法进行扩容，每次扩容 大小为原来数组大小的1.5倍 ，即int newCapacity = oldCapacity + (oldCapacity >> 1); 底层会调用System.arrayCopy进行数组复制，注意,System.arrayCopy调用java本地native方法，在内存进行数组复制，这个是个线程不安全的方法，多线程竞争的情况下会出现java.lang.RuntimeException: System.arraycopy is not thread safe。

• 获取

public E get(int index) {
      rangeCheck(index);

      return elementData(index);
  }
private void rangeCheck(int index) {
      if (index < 0 || index >= this.size)
          throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
  }
 @SuppressWarnings("unchecked")
  E elementData(int index) {
      return (E) elementData[index];
  }

从这里看出获取方法是从elementData里面取出来数据,这里就不加赘述了。

• 删除

/**
  * 找到对应的数组下标，如果这个是最后一个元素，直接将其置为null；
  * 如果不是最后一个元素，则调用System.arraycopy方法，将后面的元素位置+1，最后将最后一个元素置空
  *  eg.      
  *             before :     1   |  2  |   3  |  4  |  5
  *             move :       1   |  2  |   4  |  5  |  __
  *             after:         1   |  2  |   4  |  5  |  null
  */
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;
}
/**
 *  此方法跟上面的方法大同小异，都是先通过确定数组下标在进行删除操作
 */
public boolean remove(Object o) {
      if (o == null) {
          for (int index = 0; index < size; index++)
              if (elementData[index] == null) {
                  fastRemove(index);
                  return true;
              }
      } else {
          for (int index = 0; index < size; index++)
              if (o.equals(elementData[index])) {
                  fastRemove(index);
                  return true;
              }
      }
      return false;
  }

• 更新

  /**
    * 根据传入的数组下标确定值，返回原值
    */
  public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
   }

• 并发情况
  1. 只add，中间不进行遍历

  
   public static void main(String[] args) throws InterruptedException {
        List<Integer> list = new ArrayList<>();
        list.get(1);

        Random random = new Random();
        CountDownLatch countDownLatch = new CountDownLatch(20);
        for (int i = 0; i < 20; i++) {
            new Thread(() -> {
                System.out.println("线程" + Thread.currentThread().getName() + "开始执行");
                int total = random.nextInt(1000) % 4001 + 1000;
                System.out.println("长度：" + total);
                for (int j = 0; j < total; j++) {
                    list.add(j);

                }
                countDownLatch.countDown();
                System.out.println("线程" + Thread.currentThread().getName() + "执行完毕");
            }, String.valueOf(i)).start();
        }

        countDownLatch.await();
        System.out.println("集合长度：" + list.size());
    }

此样例只是模拟高并发下add操作，通过实验发现会报出java.lang.ArrayIndexOutOfBoundsException 异常,对于此异常网上没有什么好的解释。
笔者猜测在执行到add方法时，a,b 两个线程同时进行ensureCapacityInternal检查，每个线程检查都不够扩容条件，所以执行elementData[size++] = e 方法，
假设elementData的容量就是10，现在已经有了9个元素，正常情况下a线程插入正常，b线程在插入时候会变成elementData[10++]，由此造成数组下标越界。当然，
这个猜想如果有不对的地方欢迎指正

 public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
 }

2.插入和遍历同时进行

public static void main(String[] args){
     List<Integer> list = new ArrayList<>();

     for (int i = 0; i < 4; i++) {
         new Thread(() -> {
             System.out.println("线程" + Thread.currentThread().getName() + "开始执行");
             System.out.println("长度：" + 20);
             for (int j = 0; j < 20; j++) {
                 list.add(j);

             }
             System.out.println("线程" + Thread.currentThread().getName() + "执行完毕");

             for (Integer integer : list){
                 System.out.println(integer);
             }
         }, String.valueOf(i)).start();
     }

     System.out.println("集合长度：" + list.size());
 }

执行此操作会报java.util.ConcurrentModificationException异常，ArrayList里面有一个内部类，private class Itr implements Iterator<E>，在ListArray每次add是，有一个变量modCount一直在做自增，当做遍历操作的时候，ArrayList因为没有加入同步机制，所以checkForComodification检查方法不允许在遍历时进行新增和删除操作。

   /**
    * An optimized version of AbstractList.Itr
    */
   private class Itr implements Iterator<E> {
       int cursor;       // index of next element to return
       int lastRet = -1; // index of last element returned; -1 if no such
       int expectedModCount = modCount;
      ...
      ...
       final void checkForComodification() {
           if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
       }
      ...
      ...
  }

3. LinkedList

• 属性

    /**
      * 集合元素个数
      */
    transient int size = 0;

    /**
     * 集合首个元素
     */
    transient Node<E> first;

    /**
     * 集合最后一个元素
     */
    transient Node<E> last;

• 构造器

public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

• 新增

public boolean add(E e) {
    linkLast(e);
    return true;
}
void linkLast(E e) {
    // 保存集合中最后一个元素
    final Node<E> l = last;
    // 将传入的元素构造成node
    final Node<E> newNode = new Node<>(l, e, null);
    // 因为是末尾插入，新插入的元素为最后一个
    last = newNode;
    // 如果当前集合为空的时候，first和last都指向这个新增的元素
    // 如果不是空，维护原来的链状关系
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    
    // 集合元素个数+1
    size++;
    // 计数，遍历用
    modCount++;
}

// 新增集合
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

// 指定位置插入集合
public boolean addAll(int index, Collection<? extends E> c) {
    // 检查传入的index是否合理 (index >= 0 && index <= size)
    checkPositionIndex(index);
    Object[] a = c.toArray();
    // 记录插入元素个数
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Node<E> pred, succ;
    //分为两种情况
    // ①  集合从末尾插入，这时只要维护尾端的链式结构就可以，对原集合前面的元素没有影响,
    //       当循环插入之后，只需要将last节点指向最后一个元素即可
    // ②  从中间某一段插入，这时，succ记录原集合的指定位置元素，pred记录上一节点元素
    //       ，当循环插入之后，维护succ与插入的最后一个节点之间的关系
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }
    size += numNew;
    modCount++;
    return true;
}

• 删除

  移除首项元素,如果集合为空，会抛出NoSuchElementException异常

public E remove() {
   return removeFirst();
}
public E removeFirst() {
   final Node<E> f = first;
   if (f == null)
       throw new NoSuchElementException();
   return unlinkFirst(f);
}

移除指定位置元素，如果集合为空或者位置不合法，会抛出IndexOutOfBoundsException异常

 public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
E unlink(Node<E> x) {
  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;
}

移除特定对象，会先遍历集合，如果没有找到，不会抛出异常，会返回false

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

• 更改,会返回原来的值

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

• 查询，会使用折半查找，查找的时间复杂度为O(n),对比ArrayList的时间复杂度O(1)在查找上的效率不高，但是插入和删除的效率要比ArrayList高，
  只需要维护链状结构即可。

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

4. Vector

• 对于Vector来说，为JDK1.0就已经存在古老集合，ArrayList在实现上很大一部分借鉴了Vector里面的方法，
  所不同的是Vector里面的方法大部分为同步方法，单个操作是线程安全的。有兴趣的同学可以看看源码，
  其实跟ArrayList大同小异。但是如果涉及到组合操作也会造成线程不安全问题。测试代码：

public static void main(String[] args) throws InterruptedException {

    List<String> list = new Vector<>();
    CountDownLatch count = new CountDownLatch(20);
    Random random = new Random();
    for (int i = 0; i < 20; i++) {
        new Thread(() -> {
            int k = random.nextInt(100);
            if (!list.contains(String.valueOf(k))) {
                try {
                    Thread.sleep(2000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                list.add(String.valueOf(k));
            }
            count.countDown();
        }, String.valueOf(i)).start();
    }
    count.await();
    System.out.println("运行前集合数量：\t" + list.size());
    Set<String> set = new HashSet<>();
    list.forEach(a -> set.add(a));
    System.out.println("排序后集合数量：\t" + set.size());
}

这里我们是中间加了一段Thread.sleep(2000);休息时间的代码，来让这个错误放大。测试结果表明list中的元素确实回出现重复值的情况，
所以要实现线程安全，外部还得加入安全机制。

5. HashMap(本来按照上面的顺序需要这里需要写HashSet，但是因为HashSet底层都是用的HashMap，所以先介绍HashMap)

• 参考资料：

  1. HashMap源码注解 之 静态工具方法hash()、tableSizeFor()
  2. HashMap中的tableSizeFor方法
  3. JDK1.8源码解析-HashMap
  4. HashMap源码解析JDK1.8(史上最详细的源码分析)（如果感觉我这里讲的不清晰，可以来这里，这个博客感觉写的是最全的,本文的很多注释也是参考这篇文章）

• 属性

    /**默认容量，1向左移位4个，00000001变成00010000，也就是2的4次方为16，使用移位是因为移位是计算机基础运算，效率比加减乘除快。**/
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    //最大容量，2的30次方。
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //加载因子，用于扩容使用。
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //当某个桶节点数量大于8时，会转换为红黑树。
    static final int TREEIFY_THRESHOLD = 8;
    //当某个桶节点数量小于6时，会转换为链表，前提是它当前是红黑树结构。
    static final int UNTREEIFY_THRESHOLD = 6;
    //当整个hashMap中元素数量大于64时，也会进行转为红黑树结构。
    static final int MIN_TREEIFY_CAPACITY = 64;
    //存储元素的数组，transient关键字表示该属性不能被序列化
    transient Node<K,V>[] table;
    //将数据转换成set的另一种存储形式，这个变量主要用于迭代功能。
    transient Set<Map.Entry<K,V>> entrySet;
    //元素数量
    transient int size;
    //统计该map修改的次数
    transient int modCount;
    //临界值，也就是元素数量达到临界值时，会进行扩容。
    int threshold;
    //也是加载因子，只不过这个是变量。
    final float loadFactor; 

• 构造器,注意：构造HashMap的时候并不会进行table的初始化操作，这个操作会延迟到第一次调用put（）方法的时候。

// ① 设置负载因子为0.75f
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
// ② 初始化长度，使用默认的负载因子
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// ③ 指定负载因子和临界值容量
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);
}
// 求出给定数值的最接近的2的幂
// ① 如果cap 开始不进行 -1 ，造成的情况：如果我输入的是8，那么按照下面算法操作结果为16，
//   明显求出的数不是最接近的，最接近的是8，所以需要-1
// ② 位运算，如果这段代码不太理解可以参考：https://blog.csdn.net/fan2012huan/article/details/51097331，这篇文章讲的很详细
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;
}
// ④ 放入一个Map集合
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        // 如果table没有初始化
        if (table == null) { 
            // 因为容量阈值为 总容量 * 负载系数，所以这一步要根据m的大小来计算
            // 总容量
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            // 如果总容量超出临界值，则重新计算临界值大小,
            // 在putVal里面会对容器大小进行重新计算
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        // 容器已经初始化，但是临界值小于m的大小，进行扩容
        else if (s > threshold)
            resize();
        // 循环遍历,putVal 会在下面解释
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

• 新增

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
// 求出Key的hash值，将高位和低位混合，增加hash的随机性，笔者也是参考:
// https://blog.csdn.net/kenzhang28/article/details/80212936,
// 这篇文章会有详细描述
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // tab指向哈希数组，p为哈希数组特定位置的首个节点，n为数组大小，i为hash位置
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 当table没有初始化或者tab的容量为0是，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 如果当前hash值的节点为null，则证明没有元素存放，直接将新元素放进去
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 当节点值不为null的时候
        Node<K,V> e; K k;
        // 由上面的代码，p已经指向了首节点，如果首节点的hash值和key都相同，则将e指向p
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果当前节点为红黑树结构，则将值放在树中，e指向这里
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 如果当前结构为链表，遍历，如果当前元素的数量大于等于8，则将其转化为红黑树
            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);
    return null;
}

这里没有对resize()和链表转红黑树做进一步说明，有兴趣的同学可以继续看一看源码，
对于红黑树而言，笔者也是一知半解就不误人子弟了^_。

• 删除

public boolean remove(Object key, Object value) {
    return removeNode(hash(key), key, value, true, true) != null;
}
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;
    // 如果table已经初始化并且里面有元素
    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;
}

• 更新

// 比较老值，如果符合传入的则替换
 public boolean replace(K key, V oldValue, V newValue) {
    Node<K,V> e; V v;
    if ((e = getNode(hash(key), key)) != null &&
        ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
        e.value = newValue;
        afterNodeAccess(e);
        return true;
    }
    return false;
}
// 将对应的key的value设置为传入值
public V replace(K key, V value) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) != null) {
        V oldValue = e.value;
        e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
    return null;
}

• 查询

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) {
    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) {
        // 根据hash寻址，找出节点第一个元素,如果hash和key符合就返回
        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;
}

因为对红黑树没有什么研究，所以本文涉及到红黑树的部分就一笔带过，后续会单独写一章红黑树的介绍~~

6. LinkedHashmap

• 参考资料：
  1. JDK1.8源码(九)——java.util.LinkedHashMap 类
• LinkedHashMap，集成自HashMap，可以说LinkedHashMap = HashMap + LinkedList，跟HashMap不同的是
  LinkedHashMap加了一些维护链表的操作，其中accessOrder来决定是按照插入排序还是按照访问排序，具体细节
  可以参考上面给的链接，这里就不过多叙述了

7. TreeMap/HashSet/LinkedHashSet/TreeSet

• TreeMap是基于红黑树的结构来实现的，支持自定义排序，这里笔者会在后续专门写一篇关于红黑树的分析文章，
  并且会将红黑树的实现放在那篇文章里面讲解（说到底还是底蕴不足，学无止境啊~）
• TreeSet:底层是由TreeMap实现的，至于HashSet、LinkedHashSet都是由Map的对应实现类变种过来的，有兴趣
  可以看一下源码，这里就不过多做解释了。