1.1类图

1.2 扩容

HashMap、HashSet默认初始容量大小 16；HashTable默认初始容量大小 11；ArrayList、Vector默认初始容量大小 10；

• HashMap

创建时不指定容量，则默认初始容量大小 16，扩容因子为 0.75，扩容倍数为 2，因为在计算元素该存放的位置的时候，用到的算法是将元素的 hashcode 与当前 map 长度-1 进行与运算。return h & (length-1);如果 map 长度为 2 的幂次，那长度-1 的二进制一定为 11111...这种形式，碰撞几率小，不浪费空间。

• HashTable

默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1；

• ArrayList

以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右），奇偶不同。ArrayList的扩容是创建一个1.5倍的新数组，然后把原数组的值拷贝过去。

• StringBuffer

初始容量可以容纳 16 个字符，size 可以指定，可以字符串传参，基础上再加 16。将新容量扩为大小变成 2 倍+2，if 判断一下，容量如果不够，直接扩充到需要的容量大小。构造方法可以传入参数 int，意味着这里传入参数可以是 0，那么在参数是 0 的情况下，0<<1 运算结果也是 0，那么在初始化数组的时候必然会报错，所以作为设计的安全性考虑，这里防止出现报错，选择了+2。

1.3Collection

Collection 是一个集合接口，它提供了对集合对象进行基本操作的通用接口方法，所有集合都是它的子类，比如 List、Set 等。Java不提供直接继承自Collection的类，只提供继承于的子接口。

Collections 是一个包装类，包含了很多静态方法、不能被实例化，而是作为工具类使用，比如提供的排序方法：Collections.sort(list);提供的反转方法：Collections.reverse(list)。

1.3.1List、Set、Queue

• List 必须保持元素特定的顺序 (有序、可重复、查找效率高、插入删除低、下标遍历)
• Set 不能有重复元素(无序、不可重复、查询效率低)
• Queue 保持一个队列(先进先出)的顺序

1.3.2ArrayList、Vector、LinkedList

相同点：三者都实现 List 接口，都是有序集合。前两个底层采用 Object[] elementData 数组。LinkedList双向链表(JDK1.6之前为循环链表，JDK1.7取消了循环)。

不同点：

• Vector 是 Java 早期提供线程安全（Synchronized 实现）的动态数组，扩容时先创建新的扩容后数组，并拷贝原有数组数据，最后删除原数组，扩容会提高 1 倍（变成原来的 2 倍），特点：查询快，增删慢，线程安全，效率低。建议在单线程中才使用 ArrayList，而在多线程中可以选择 Vector 或者 CopyOnWriteArrayList。
• ArrayList 也是动态数组的数据结构，是非线程安全的，所以性能要好，扩容时增加 50%（变成原来的 1.5 倍）。ArrayList 默认初始长度 10。
• LinkedList 是双向链表的数据结构（注意：JDK1.6 之前为循环链表，JDK1.7 取消了循环），也是非线程安全。
• ArrayList 比 LinkedList 查询效率高，因为 LinkedList 是线性的数据存储方式，需要移动指针从前往后依次查找，而 ArrayList 根据角标 index 直接锁定位置；查找原理：数组空间连续，查询通过偏移量找。链表逻辑连续，空间不连续，指针访问。
• 插入和删除效率：在 List 中间插入和删除数据时，ArrayList 要比 LinkedList 效率低很多，因为 ArrayList 增删操作要影响数组内的其他数据的下标（整体移动），而如果是正常的末尾追加方式，效率大体相同；ArrayList：若增加至末尾 O(1)；若在指定位置 i 插入 O(n-i)。LinkedList：插入删除都是近似 O(1)，而数组为近似 O(n)。多数情况下，ArrayList更利于查找，LinkedList更利于增删。

• 内存空间占用：ArrayList是预先定义好的数组，可能会有空的内存空间，存在一定空间浪费，但LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。ArrayList基于数组，是一块连续的内存空间，LinkedList基于链表，内存空间不连续。
• ArrayList 实现了 RandomAccess 接口， 而 LinkedList 没有实现。 ArrayList 底层是数组，而 LinkedList 底层是链表。数组天然支持随机访问，时间复杂度为 O（1），所以称为快速随机访问。链表需要遍历到特定位置才能访问特定位置的元素，时间复杂度为 O（n），所以不支持快速随机访问。ArrayList 实现了 RandomAccess 接口，就表明了他具有快速随机访问功能。 RandomAccess 接口只是标识，并不是说 ArrayList 实现 RandomAccess 接口才具有快速随机访问功能的！
• LinkedList还额外实现了Deque接?，所以 LinkedList还可以当做队列来使?。

fail-fast是一种可能触发的机制，实际上ArrayList 的线程安全仍然没有保证，如果遇到多线程场景，可以通过如下方案保证线程安全：

1.使用Vector代替ArrayList。（不推荐，Vector是一个历史遗留类）

2.使用Collections.synchronizedList 方法将其转换成线程安全的容器后再使用。List<String> syncList = Collections.synchronizedList(arraylist)。

3.使用CopyOnWriteArrayList代替ArrayList。

4.在使用 ArrayList 时，应用程序通过同步机制去控制 ArrayList 的读写。

list 的遍历方式选择：

• 实现了 RandomAccess 接口的list，优先选择普通 for 循环 ，其次 foreach。
• 未实现 RandomAccess接口的list，优先选择iterator遍历（foreach遍历底层也是通过iterator实现的,），大size的数据，千万不要使用普通for循环。

双向链表： 包含两个指针，一个prev指向前一个节点，一个next指向后一个节点。

双向循环链表： 最后一个节点的 next 指向head，而 head 的prev指向最后一个节点，构成一个环。

1.3.3HashSet 如何保证 key 不重复

通过 HashSet 的 add 方法实现可知，其维护了一个 HashMap 来实现元素的添加；我们知道，HashMap 作为双列集合，它的键是不能够重复的，HashMap 针对 hashCode 相同且 equals 比较值相同的时候执行的是更新操作，所以 Hashmap 中的 key 是唯一的，也决定了 hashset 元素值也是唯一的。

1.3.4HashSet、HashMap 区别

HashSet 底层就是基于 HashMap 实现的（除了个别方法自己实现，其他调用 hashmap 的）。HashMap 使用键(Key)计算 hashcode，HashSet 使用成员对象来计算 hashcode 值。

1.3.5List、Set 区别

1、List,Set 都是继承自 Collection 接口

2、特点区分：

List 特点：元素有序不唯一。可以插入多个 null 元素。list 方法常用的实现类有：ArrayList、LinkedList 和 Vector。

Set 特点：元素无序唯一，重复元素会覆盖掉，只允许插入一个 null 元素（元素虽无序，但元素在 set 中的位置是有该元素的 HashCode 决定的，其位置其实是固定的；加入 Set 的 Object 必须定义 equals()方法 ，另外 list 支持 for 循环，也就是通过下标来遍历，也可以用迭代器，但是 set 只能用迭代，因为无序，无法用下标来取得想要的值。）Set 方法中常用的实现类有: HashSet、LinkedHashSet以及 TreeSet。

• HashSet：底层数据结构是哈希表（无序，唯一），通过 hashcode()和 equals()保证元素唯一。
• LinkedHashSet： 底层数据结构是链表和哈希表（FIFO 插入有序，唯一），由链表保证元素有序，由哈希表保证元素唯一。
• TreeSet：底层数据结构是红黑树（唯一，有序），通过自然排序和比较器排序保证元素有序，根据比较返回值是否是 0 来保证元素唯一性。

3、Set 和 List 效率对比：

Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。

List：和数组类似，List 可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变。

1.3.6List.remove()方法

推荐 Iterator.remove()

public class ListRemove {
  public static void main(String[] args) {
    /**
     * 总结：1.用for循环遍历 List 删除元素时，需要注意索引会左移的问题。
     *2.List删除元素时，为避免陷阱，建议使用迭代器iterator的remove方式--5。
     *3.List删除元素时，默认按索引删除，而不是对象删除。
     */
    List<Integer> list = new ArrayList<Integer>(){{
      add(1);add(2);add(3);add(3);add(4);
    }};
    System.out.println("原始 list==" + list);
//        test1(list);
//        test2(list);
//        test3(list);
//        test4(list);
    test5(list);
//        test6(list);
//        test7(list);
//        test8(list);
  }
  // 1、普通 for 循环遍历 List 删除指定元素--错误！！！相邻有相同元素会漏删
  public static void test1(List<Integer> list) {
    for (int i = 0; i < list.size(); i++) {
      if (list.get(i) == 3) {
        list.remove(i);
      }
    }
    System.out.println("情况 1 后 list1==" + list);
  }
  // 2、for 循环遍历 List 删除元素时，让索引同步调整--正确！
  public static void test2(List<Integer> list) {
    for (int i = 0; i < list.size(); i++) {
      if (list.get(i) == 3) {
        list.remove(i--);
      }
    }
    System.out.println("情况 2 后 list2==" + list);
  }
  // 3、倒序遍历 List 删除元素--正确！
  public static void test3(List<Integer> list) {
    for (int i = list.size() - 1; i >= 0; i--) {
      if (list.get(i) == 3) {
        list.remove(i);
      }
    }
    System.out.println("情况 3 后 list3==" + list);
  }
  // 4.foreach遍历List删除元素--错误！！抛异常：java.util.ConcurrentModificationException
  /**
   * 通过代码我们发现Itr是ArrayList中定义的一个私有内部类，
   * 在next、remove方法中都会调用checkForComodification方法，
   * 该方法的作用是判断modCount != expectedModCount是否相等，
   * 如果不相等则抛出ConcurrentModificationException 异常。
   */
  public static void test4(List<Integer> list) {
    for (Integer i : list) {
      if (i == 3) {
          list.remove(i);
      }
    }
    System.out.println("情况 4 后 list4==" + list);
  }
  // 5、迭代删除List元素--正确！
  // Iterator.remove() 方法会在删除当前迭代对象的同时，会保留原来元素的索引。
  // 所以用迭代删除元素是最保险的方法，建议大家使用List过程中需要删除元素时，使用这种方式。
  public static void test5(List<Integer> list) {
    Iterator<Integer> it = list.iterator();
    while (it.hasNext()) {
      if (it.next() == 3) {
        it.remove();
      }
    }
    System.out.println("情况 5 后 list5==" + list);
  }
  // 6、迭代遍历,用 list.remove(i)方法删除元素--错误！！！抛出异常：java.util.ConcurrentModificationException，
  public static void test6(List<Integer> list) {
    Iterator<Integer> it = list.iterator();
    while (it.hasNext()) {
      Integer value = it.next();
      if (value == 3) {
        list.remove(value);
      }
    }
    System.out.println("情况 6 后 list6==" + list);
  }
  // 7、List 删除元素时，注意 Integer 类型和 int 类型的区别.
  public static void test7(List<Integer> list) {
    list.remove(2);
    System.out.println("情况 7 后 list7==" + list);
  }
  // 8、List 删除元素时，注意 Integer 类型和 int 类型的区别.
  public static void test8(List<Integer> list) {
    list.remove(new Integer(2));
    System.out.println("情况 8 后 list8==" + list);
  }
}

1.3.7ArrayList 扩容机制

以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。

• 添加元素时使用 ensureCapacityInternal()方法来保证容量足够，如果不够时，需要使用 grow()方法进行扩容
• 新容量的大小为 oldCapacity + (oldCapacity >> 1)，即 oldCapacity+oldCapacity/2。其中 oldCapacity >> 1 需要取整，所以新容量大约是旧容量的 1.5 倍左右。（oldCapacity 为偶数就是 1.5 倍，为奇数就是 1.5 倍-0.5）
• 扩容操作需要调用 Arrays.copyOf()把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。
• modCount 记录结构修改次数

1.3.8ArrayList 序列化

ArrayList的序列化不太一样，它使用transient修饰存储元素的elementData的数组，transient关键字的作用是让被修饰的成员属性不被序列化。出于效率的考虑，数组可能长度100，但实际只用了50，剩下的50不用其实不用序列化，这样可以提高序列化和反序列化的效率，还可以节省内存空间。

ArrayList通过两个方法readObject、writeObject自定义序列化和反序列化策略，实际直接使用两个流ObjectOutputStream和ObjectInputStream来进行序列化和反序列化。

1.4Map

注意：

• TreeMap 默认是按 Key 的自然顺序排序，实现 Comprator 接口可自定义排序规则。
• LinkedHashMap 是 HashMap 一个子类，保存了记录的插入顺序，在遍历时保持与插入一样的顺序。
• 单线程可用 HashMap，多线程中推荐 ConcurrentHashMap。
• 可以使用Map m = Collections.synchronizeMap(hashMap)；让HashMap同步。

1.4.1HashMap

原理：HashMap 底层是 hash 数组和单向链表实现，数组是主体，链表主要为了解决冲突，由 Node 内部类（实现 Map.Entry<K,V>接口）实现，HashMap 通过 put & get 方法存储和获取。

Java 8 中 new HashMap 的时候不会先创建这个数组，而是在第一次添加元素的时候创建。

在 Java 8 之前存储数据的内部类是 Entry< K, V>，之后用 Node< K, V>代替。代码大体都是一样的。

Node 代码：

static class Node implements Map.Entry { 
  // hash 是通过计算得到的散列值
  final int hash;
  final K key; 
  V value; 
  // 指向另一个 Node，这样 HashMap 可以像链表一样存储数据
  Node<K,V> next; 
  ... 
} 

内部变量:

// 默认容量大小 
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; 
// 哈希表 
transient Node[] table; 
// 键值对的数量 
transient int size; 
// 记录 HashMap 结构改变次数，与 HashMap 的快速失败相关 
transient int modCount; 
// 扩容的阈值 
int threshold; 
// 装载因子 
final float loadFactor;

HashMap 有两个重要的参数：容量（Capacity）和负载因子（LoadFactor）。

容量（Capacity）：是指 HashMap 中桶的数量，默认的初始值为 16。容量必须满足是 2 次幂，如果我们指定 initialCapacity 不为 2 次幂时，HashMap 的 tableSizeFor 方法将其转换为大于 n 的最小的 2 的 N 次方数，能保证 n 永远都是 2 次幂。

负载因子（LoadFactor）：也被称为装载因子，LoadFactor 是用来判定 HashMap 是否扩容的依据，默认值为 0.75f，装载因子的计算公式 = HashMap 存放的 KV 总和（size）/ Capacity。

Capacity 为什么是 2 的幂次?

因为当容量为 2 的幂时，会满足一个公式：(n - 1) & hash = hash % n，而&比%具有更高的效率，能保证索引值肯定在 capacity 中，不会超出数组长度。

(n - 1) & hash 实际上是计算出 key 在 tab 中索引位置。

扰动函数作用及实现

作用：解决碰撞问题

实现：①使用key.hashCode()计算hash值并赋值给变量h；②将h向右移动16位；③将变量h和向右移16位的h做异或运算（二进制位相同为0，不同为1）。此时得到经过扰动函数后的hash值。

所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
  // cap-1 后，n 的二进制最右一位肯定和 cap 的最右一位不同，即一个为 0，一个为 1，例如 cap=17（00010001），n=cap-1=16（00010000）
  // 减 1→移位→按位或运算→加1返回  
  int n = cap - 1;
  //n = (00010000 | 00001000) = 00011000
  n |= n >>> 1;
  //n = (00011000 | 00000110) = 00011110
  n |= n >>> 2;
  //n = (00011110 | 00000001) = 00011111
  n |= n >>> 4;
  //n = (00011111 | 00000000) = 00011111
  n |= n >>> 8;
  //n = (00011111 | 00000000) = 00011111
  n |= n >>> 16;
  //n = 00011111 = 31
  //n = 31 + 1 = 32, 即最终的 cap = 32 = 2 的 (n=5)次方
  return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

扩容源码：

final Node<K,V>[] resize() {
  Node<K,V>[] oldTab = table; // now the table is null
  int oldCap = (oldTab == null) ? 0 : oldTab.length;  // so oldCap == 0
  /*
  * 1、若调用的是带有参数的构造器，oldThr = tableSizeFor(initialCapacity)  > 0,
  * 2、若调用的是无参数的构造器，oldThr == 0
  */
  int oldThr = threshold; 
  int newCap, newThr = 0;
  if (oldCap > 0) {
    //下面代码不会调用，因为 oldCap == 0
  }
  else if (oldThr > 0) // initial capacity was placed in threshold
    //若调用的是带有参数的构造器，此时计算的桶数组大小就是 tableSizeFor(initialCapacity) > 0
    newCap = oldThr;
  else {// zero initial threshold signifies using defaults
    //若调用的是无参数的构造器，newCap == 16, newThr == (int) 16 * 0.75
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  if (newThr == 0) {
    //到这里如果 newThr 还没有被赋值，就执行下面代码
    //为什么到这里 newThr 依然为 0 呢？如果调用带有参数的构造器，那么 threashold 是大于 0 的，那么
    //就执行上面的 if(oldThr > 0),将 oldThr 值赋给 newCap，此时 newThr 依然为 0, 而原来的 threshold 也就没有了用处
    //这说明之前将一个 2 的幂次方值赋值给 threshold，只是为了赋值给桶数组的默认容量值（newCap = oldThr），赋值完之后，
    //threashold 就需要重新计算了，下面就是计算过程：
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
    (int)ft : Integer.MAX_VALUE);
  }
  //覆盖 threshold
  threshold = newThr;
  //开辟空间在这里
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  table = newTab;
  if (oldTab != null) {
    //这里面的代码不会调用，因为 oldTab == null。
  }
  //返回桶数组的引用
  return newTab;
}

Put 源码大致思路：

首次 put 步骤：①、分配数组空间；（无参构造默认空间16）②、插入键值对；③、++modCount;

非首次 put 步骤：①、调用 hash(K) 方法计算K的hash值，然后结合数组长度，计算得数组下标；

②、根据hash值找到对应桶位置的第一个元素，判断是否有

a.没有，直接将键值对插入到哈希表中。

b.有，则发生碰撞；

i.key 相同且它们两者 equals 返回 true，则更新键值对；

ii.如果是红黑树，则执行树的插入

iii.如果是链表，有 key 满足相等条件，替换旧值；否则插入 key-value 到链表最后；插入之后如果当前链表长度大于 TREEIFY_THRESHOLD，转换成红黑树结构。

③、判断是否超过阀值，如果超过就要扩容（当容器中的元素个数大于capacity * loadfactor时，容器会进行扩容resize为2n）；

注意：1、JDK 1.7 之前使用头插法、JDK 1.8 使用尾插法

public V put(K key, V value) {
  // 对 key 进行 hash()
  return putVal(hash(key), key, value, false, true);
}
// 扰动函数
static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h ??? 16);
}


//onlyIfAbsent 为 false，说明如果已经存在相同(== 、equals)的 key，则覆盖并返回旧值。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
  Node?K,V?[] tab; Node?K,V? p; int n, i;
  // tab 为空则创建
  // 第一次 put 值的时候，会触发下面的 resize()，开辟数组空间
  if ((tab = table) == null || (n = tab.length) == 0)
    // resize()是调整 table 数组大小的，若 table 数组为空或长度为 0，重新调整大小 
    n = (tab = resize()).length;
   // (n - 1) & hash 计算出的值是存放数组的位置，若当前位置为空，则直接放入其中
  if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  else {
    //第一次调用 put 的时候，下面代码都不会执行
    // hash 冲突
    Node?K,V? e; K k;
    // 如果 hash 相同，并且 key 值也相同，则找到存放位置
    if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
      e = p;
    // 该链为二叉树，则放入二叉树中
    else if (p instanceof TreeNode)
      e = ((TreeNode?K,V?)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
            // 如果链表中的值大于 TREEIFY_THRESHOLD - 1，则将链表转换成二叉树  
            treeifyBin(tab, hash);
          break;
        }
        if (e.hash == hash &&
          ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        p = e;
      }
    }
    // 表示对于当前 key 早已经存在
    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      // 如果 onlyIfAbsent 为 false 或则 oldValue 为空，替换原来的值
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      afterNodeAccess(e);
      // 返回原来的值
      return oldValue;
    }
  }
  // HashMap 结构修改次数，主要用于判断迭代器中 fail-fast
  ++modCount;
  // 超过 load factor*current capacity，resize
  if (++size ? threshold)
    resize();
  afterNodeInsertion(evict);
  return null;
}

获取对象时，将 K 传给 get() 方法：

①、调用 hash(K) 方法（计算 K 的 hash 值）从而获取该键值所在链表的数组下标；

②、顺序遍历链表，equals()方法查找相同 Node 链表中 K 值对应的 V 值。

hashCode 是定位的，存储位置；equals 是定性的，比较两者是否相等。

get 源码大致思路：

1. bucket 里的第一个节点，直接命中；

2. 如果有冲突，则通过 key.equals(k)去查找对应的 entry

3. 若为树，则在树中通过 key.equals(k)查找，O(logn)；

4. 若为链表，则在链表中通过 key.equals(k)查找，O(n)。

public V get(Object key) {
  Node?K,V? e;
  return (e = getNode(hash(key), key)) == null ? null : e.value;
}


/**
* 该方法是 Map.get 方法的具体实现
* 接收两个参数
* @param hash key 的 hash 值，根据 hash 值在节点数组中寻址，该 hash 值是通过 hash(key) 得到的
* @param key key 对象，当存在 hash 碰撞时，要逐个比对是否相等
* @return 查找到则返回键值对节点对象，否则返回 null
*/
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) {
        if (first.hash == hash && // 首先比对首节点，如果首节点的 hash 值和 key 的 hash 值相同，并且首节点的键对象和 key 相同（地址相同或 equals 相等），则返回该节点
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first; // 返回首节点
 
        // 如果首节点比对不相同、那么看看是否存在下一个节点，如果存在的话，可以继续比对，如果不存在就意味着 key 没有匹配的键值对    
        if ((e = first.next) != null) {
            // 如果存在下一个节点 e，那么先看看这个首节点是否是个树节点
            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)))) // 比对时还是先看 hash 值是否相同、再看地址或 equals
                    return e; // 如果当前节点 e 的键对象和 key 相同，那么返回 e
            } while ((e = e.next) != null); // 看看是否还有下一个节点，如果有，继续下一轮比对，否则跳出循环
        }
    }
    return null; // 在比对完了应该比对的树节点 或者全部的链表节点 都没能匹配到 key，那么就返回 null

1.4.1.1Java7 和 Java8 区别

主要区别如下：

• 存储结构：JDK7 使用的是数组 + 链表；JDK8 使用的是数组 + 链表 + 红黑树。原因：发生 hash 冲突，元素会存入链表，链表过长转为红黑树，将时间复杂度由O(n)降为O(logn)。
• 存放数据的规则：JDK7 无冲突时，存放数组；冲突时，存放链表；JDK8 无冲突时直接存放数组，有冲突时，当链表长度小于 8 时，存放在单链表结构中，当链表长度大于 8 时，树化并存放至红黑树的数据结构中。
• 插入数据方式：JDK7 使用的是头插法（先将原位置的数据移到后 1 位，再插入数据到该位置）；JDK8 使用的是尾插法（直接插入到链表尾部/红黑树）。（因为 JDK1.7 是用单链表进行的纵向延伸，当采用头插法时会容易出现逆序且环形链表死循环问题。但是在 JDK1.8 之后是因为加入了红黑树使用尾插法，能够避免出现逆序且链表死循环的问题。）
• JDK8 中的因为使用了红黑树保证了插入和查询了效率，所以实际上 JDK8 中的 Hash 算法实现的复杂度降低了
• 扩容rehash：扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置，1.8 采用更简单的判断逻辑，不需要重新通过哈希函数计算位置，新的位置不变或索引 + 新增容量大小。原因：提高扩容的效率，更快地扩容。
• 扩容时机：插入时1.7 先判断是否需要扩容，再插入；1.8 先进行插入，插入完再判断是否需要扩容；
• JDK8 中数组扩容的条件也发了变化，只会判断是否当前元素个数是否超过了阈值，而不再判断当前 put 进来的元素对应的数组下标位置是否有值。
• 散列函数：1.7 做了四次移位和四次异或，jdk1.8只做一次。原因：做 4 次的话，实际效用也不大，改为一次，提升效率。

桶数组是用来存储数据元素，链表是用来解决冲突，红黑树是为了提高查询的效率。

• 数据元素通过映射关系，也就是散列函数，映射到桶数组对应索引的位置
• 如果发生冲突，从冲突的位置拉一个链表，插入冲突的元素
• 如果链表长度>8&数组大小>=64，链表转为红黑树
• 如果红黑树节点个数<6 ，转为链表

JDK7 中 HashMap 死循环导致 CPU100%的原因：

HashMap 之所以在并发下扩容会造成死循环，是因为多个线程并发进行时，一个线程先期完成了扩容，将原的链表重新散列到自己的表中，并且链表变成了倒序，后一个线程再扩容时，又进行自己的散列，再次将倒序链表变为正序链表。于是形成了一个环形链表，当表中不存在元素时，造成死循环。虽然在 JDK1.8 中，修正了这个问题，但是 HashMap 始终存在着其他的线程安全问题。所以在并发情况下，我们应该使用 HastTable 或者 ConcurrentHashMap 来代替 HashMap。推荐 ConcurrentHashMap。

1.4.1.2 常见问题

1.当两个对象的 hashCode 相同会发生什么？

因为 hashCode 相同，不一定就是相等的（equals 方法比较），所以两个对象所在数组的下标相同，"碰撞"就此发生。又因为 HashMap 使用链表存储对象，这个 Node 会存储到链表中。

2.key 的 hash 的实现

JDK1.8 中，是通过 hashCode()的高 16 位异或低 16 位实现的：(h = k.hashCode()) ^ (h >>> 16)，使用位运算替代取模运算，在 table 的长度比较小的情况下，也能保证 hashcode 的高位参与到地址映射的计算当中，避免碰撞，同时不会有太大的开销。

3.key 的 hash 右移 16 位的原因

因为 h 的 int 类型正好 32 位，右移 16 位正好为 32bit 的一半，然后再与 h 异或时，就能达到 h 的高 16 位和低 16 位都能参与计算，使计算出的 hash 值更加的分散，且最大努力减少哈希冲突。

5.为什么要用异或运算符？

保证了对象 hashCode 的 32 位值只要有一位发生改变，整个 hash()返回值就会改变。尽可能的减少碰撞。

6.HashMap 的 table 的容量如何确定？loadFactor 是什么？该容量如何变化？这种变化会带来什么问题？

①、table 数组大小是由 capacity 这个参数确定的，默认是16，也可以构造时传入，最大限制是1<<30；

②、loadFactor是装载因子，主要目的是用来确认table数组是否需要动态扩展，默认值是0.75，比如table数组大小为16，装载因子为0.75时，threshold就是12，当table的实际大小超过12时，table就需要动态扩容；

③、扩容时，调用 resize() 方法，将 table 长度变为原来的两倍（注意是 table 长度，而不是 threshold）

④、数据很大的情况下，扩展时将会带来性能的损失，在性能要求很高的地方，这种损失很可能很致命。

7.数组扩容的过程？

创建一个新的数组，其容量为旧数组的两倍，并重新计算旧数组中结点的存储位置。结点在新数组中的位置只有两种，原下标位置或原下标+旧数组的大小。

8.拉链法导致的链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？

之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当长度大于 8 的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

9.红黑树，为什么不用二叉树、平衡树

红黑树本质上是一种二叉查找树，为了保持平衡，它又在二叉查找树的基础上增加了一些规则：

1、每个节点非红即黑

2、根节点永远是黑色的

3、所有的叶子节点都是黑色的（如图中NULL节点）

4、每个红色节点的两个字节点一定都是黑色；

5、从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）

之所以不用二叉树：

红黑树是一种平衡的二叉树，插入、删除、查找的最坏时间复杂度都为 O(logn)，避免了二叉树最坏情况下的O(n)时间复杂度。

之所以不用平衡二叉树：

平衡二叉树是比红黑树更严格的平衡树，为了保持保持平衡，需要旋转的次数更多，也就是说平衡二叉树保持平衡的效率更低，所以平衡二叉树插入和删除的效率比红黑树要低。

10.jdk8 中对 HashMap 做了哪些改变？

在 java 1.8 中，如果链表的长度超过了 8，那么链表将转换为红黑树。（桶的数量必须大于 64，小于 64 的时候只会扩容）

发生 hash 碰撞时，java 1.7 会在链表的头部插入，而 java 1.8 会在链表的尾部插入

在 java 1.8 中，Entry 被 Node 替代(换了一个马甲)。

11.HashMap，LinkedHashMap，TreeMap 有什么区别？

HashMap 参考其他问题；

LinkedHashMap 保存了记录的插入顺序，在用 Iterator 遍历时，先取到的记录肯定是先插入的；遍历比 HashMap 慢；

TreeMap 实现 SortMap 接口，能够把它保存的记录根据键排序（默认按键值升序排序，也可以指定排序的比较器）

12.HashMap & TreeMap & LinkedHashMap 使用场景？

一般情况下，使用最多的是 HashMap。

HashMap：在 Map 中插入、删除和定位元素时；

TreeMap：在需要按自然顺序或自定义顺序遍历键的情况下；

LinkedHashMap：在需要输出的顺序和输入的顺序相同的情况下。

13.HashMap 和 HashTable 有什么区别？

相同点：

①、HashMap和Hashtable都实现了Map接口；②、都可以存储key-value数据。

不同点：

①、HashMap 是线程不安全的，效率高，HashTable 是线程安全的，效率低；

②、HashMap最多只允许一条记录的键为null，允许多条记录的值为null，而 HashTable不允许；

③、HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast 的。

④、HashMap 默认初始化数组的大小为16，HashTable 为 11，前者扩容时，扩大两倍，后者扩大两倍+1；

⑤、HashMap 需要重新计算 hash 值，而 HashTable 直接使用对象的 hashCode；

14.HashMap遍历的五种最佳方法：

• 使用 Iterator 遍历 HashMap EntrySet

Iterator < Entry < Integer, String >> iterator = coursesMap.entrySet().iterator();
while (iterator.hasNext()) {
  Entry < Integer, String > entry = iterator.next();
  System.out.println(entry.getKey());
  System.out.println(entry.getValue());
}

• 使用 Iterator 遍历 HashMap KeySet

Iterator < Integer > iterator = coursesMap.keySet().iterator();
while (iterator.hasNext()) {
  Integer key = iterator.next();
  System.out.println(key);
  System.out.println(coursesMap.get(key));
}

• 使用 For-each 循环迭代 HashMap

for (Map.Entry < Integer, String > entry: coursesMap.entrySet()) {
  System.out.println(entry.getKey());
  System.out.println(entry.getValue());
}

• 使用 Lambda 表达式[4]遍历 HashMap

coursesMap.forEach((key, value) -> {
  System.out.println(key);
  System.out.println(value);
});

• 使用 Stream API[5] 遍历 HashMap

coursesMap.entrySet().stream().forEach((entry) - > {
  System.out.println(entry.getKey());
  System.out.println(entry.getValue());
});

1.4.2ConcurrentHashMap

HashMap 是线程不安全的，而线程安全的 Map 有 HashTable 和 ConcurrentHashMap。

ConcurrentHashMap 介绍

①、重要的常量：private transient volatile int sizeCtl;

当为负数时，-1 表示正在初始化，-N 表示 N - 1 个线程正在进行扩容；

当为 0 时，表示 table 还没有初始化；

当为其他正数时，表示初始化或者下一次进行扩容的大小。

②、数据结构：

Node 是存储结构的基本单元，继承 HashMap 中的 Entry，用于存储数据；

TreeNode 继承 Node，但是数据结构换成了二叉树结构，是红黑树的存储结构，用于红黑树中存储数据；

TreeBin 是封装 TreeNode 的容器，提供转换红黑树的一些条件和锁的控制。

③、存储对象时（put() 方法）： 1.如果没有初始化，就调用 initTable() 方法来进行初始化； 2.如果没有 hash 冲突就直接 CAS 无锁插入； 3.如果需要扩容，就先进行扩容； 4.如果存在 hash 冲突，就加锁来保证线程安全，两种情况：一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入； 5.如果该链表的数量大于阀值 8，就要先转换成红黑树的结构，break 再一次进入循环 6.如果添加成功就调用 addCount() 方法统计 size，并且检查是否需要扩容。

④、扩容方法 transfer()：默认容量为 16，扩容时，容量变为原来的两倍。

helpTransfer()：调用多个工作线程一起帮助进行扩容，这样的效率就会更高。

⑤、获取对象时（get()方法）：

1.计算 hash 值，定位到该 table 索引位置，如果是首结点符合就返回；

2.如果遇到扩容时，会调用标记正在扩容结点 ForwardingNode.find()方法，查找该结点，匹配就返回；

3.以上都不符合的话，就往下遍历结点，匹配就返回，否则最后就返回 null。

1.4.2.1 与 HashTable 比较

相同点：

1.HashTable 和 ConcurrentHashMap 的共同特点是不允许 key 和 value 为 null， 而 HashMap 就比较随意，都可以是 null。

2.HashTable 和 ConcurrentHashMap 的操作方法基本一样。只是底层对锁的使用细节不一样。

3.都是线程安全的。

不同点：

1.HashTable 位于这个 java.util 包下，就是实现了HashMap加上synchronized，属于 fail-fast，不支持并发修改；对所有操作都加 synchronized，包括 get，所以效率低。

2.ConcurrentHashMap 位于 JUC（java.util.concurrent）包下，属于 fail-safe，它允许并发修改，但是无法保证在迭代过程中获取到最新的值；在检索数据时不需要锁，也不支持锁住整个表来阻止其他线程的访问。

3.ConcurrentHashMap是1.5的产物，是HashTable的替代，比HashTable的扩展性更好。（是 Java 并发包 java.util.concurrent 中提供的一个线程安全且高效的 HashMap 实现）。读操作不加锁，由于HashEntry的value变量是volatile的，也能保证读取到最新的值。

4.ConcurrentHashMap在JDK 1.7 中使用分段锁（ReentrantLock + Segment + HashEntry），相当于把一个 HashMap 分成多个段，每段分配一把锁，这样支持多线程访问。锁粒度：基于 Segment，包含多个 HashEntry。JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度：Node（首结点）（实现 Map.Entry<K,V>）。锁粒度降低了。

HashTable 是使用 synchronize 关键字加锁的原理（就是对对象加锁），一把锁（锁住整个链表结构）处理并发问题，多个线程竞争一把锁，容易阻塞；

1.4.2.2Java7 和 Java8 区别

1.4.2.3Java7 版本

在 JDK1.7 中，它是由 Segment 数组 + HashEntry 组成 ，数据结构上和 HashMap（1.7）一样，仍然是数组加链表。它的一个最主要特点就是分段锁 ，它默认允许的并发量是 16。Segment 是 ConcurrentHashMap 中的一个内部类，通过继承了 ReentrantLock 这个可重入锁来进行加锁，所以每次需要加锁的操作锁住的是一个 segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全。

• Segment 数组长度为 16，不可以扩容
• Segment[i] 的默认大小为 2，负载因子是 0.75，得出初始阈值为 1.5，也就是以后插入第一个元素不会触发扩容，插入第二个会进行第一次扩容
• 这里初始化了 segment[0]，其他位置还是 null
• 当前 segmentShift 的值为 32 - 4 = 28，segmentMask 为 16 - 1 = 15，姑且把它们翻译为移位数和掩码

put 源码

@SuppressWarnings("unchecked")
public V put(K key, V value) {
    Segment<K,V> s;
    if (value == null)
        throw new NullPointerException();
    // 1. 计算 key 的 hash 值    
    int hash = hash(key);
    //
    int j = (hash >>> segmentShift) & segmentMask;
    // 通过 UNSAFE 类去获取这个 Segment
    if ((s = (Segment<K,V>)UNSAFE.getObject      // nonvolatile; recheck
         (segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
        // 关键步骤 1
        s = ensureSegment(j);
            // 关键步骤 2
    return s.put(key, hash, value, false);
}


// ensureSegment 方法中，这个方法主要用来创建和获取 Segment 
@SuppressWarnings("unchecked")
private Segment<K,V> ensureSegment(int k) {
    final Segment<K,V>[] ss = this.segments;
    long u = (k << SSHIFT) + SBASE; // raw offset
    Segment<K,V> seg;
    if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
        Segment<K,V> proto = ss[0]; // use segment 0 as prototype
        int cap = proto.table.length;
        float lf = proto.loadFactor;
        int threshold = (int)(cap * lf);
        HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
        if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
            == null) { // recheck
            Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
            // 使用 while 循环，内部用 CAS，当前线程成功设值或其他线程成功设值后，退出
            while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
                   == null) {
                 // 关键步骤 3：使用到了 CAS 锁
                if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
                    break;
            }
        }
    }
    return seg;
}


final V put(K key, int hash, V value, boolean onlyIfAbsent) {
   // 步骤 1
    HashEntry<K,V> node = tryLock() ? null :
        scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
        HashEntry<K,V>[] tab = table;
        int index = (tab.length - 1) & hash;
        HashEntry<K,V> first = entryAt(tab, index);
        for (HashEntry<K,V> e = first;;) {
            if (e != null) {
                K k;
                 // 步骤 2
                if ((k = e.key) == key ||
                    (e.hash == hash && key.equals(k))) {
                    oldValue = e.value;
                    if (!onlyIfAbsent) {
                        e.value = value;
                        ++modCount;
                    }
                    break;
                }
                e = e.next;
            }
            else {
                // 步骤 3
                if (node != null)
                    node.setNext(first);
                else
                    node = new HashEntry<K,V>(hash, key, value, first);
                int c = count + 1;
                if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                    rehash(node);
                else
                    setEntryAt(tab, index, node);
                ++modCount;
                count = c;
                oldValue = null;
                break;
            }
        }
    } finally {
        // 步骤 4
        unlock();
    }
    return oldValue;
}

步骤 1：主要作用是上锁，tryLock()失败的话会进入一个自旋获取锁的过程，不断的尝试，当尝试的次数大于最大次数 MAX_SCAN_RETRIES 时就调用 lock()获取锁（阻塞锁）

步骤 2：遍历 HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等时如果 onlyIfAbsent=false 时覆盖旧的 value。

步骤 3：不为空则需要新建一个 HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容。

步骤 4：最后会解除在 1 中所获取当前 Segment 的锁。

get 操作不用锁，原理也一样，根据 key 的 hash 值找到那个 segment，再找到里面的 hashEntry。

虽然 ConcurrentHashMap 解决了并发问题，但是由于数据结构和 1.7 的 HashMap 一样，所以查询效率低。

1.4.2.4Java8 版本

在 JDK1.8 中

1.引入了红黑树，原因：链表查询时间复杂度 O(n)，插入时间复杂度 O(1)；而红黑树查询和插入时间复杂度都是 O(lgn)。.

2 采用了 CAS + synchronized 来保证并发安全性，放弃原有的 Segment 分段锁 。

Node 节点

// volatile 修饰是为了保证变量的可见性，禁止指令重排

put 源码

/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 关键点 1
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            // 关键点 2
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

关键点 1：主要通过 cas 的方式去设置首节点

关键点 2：通过 synchronized 去锁住这个首节点，接着通过 if (tabAt(tab, i) == f)去判断是不是同个首节点是的话再对其中的数据进行操作。

ConcurrentHashMap 在 JDK 1.8 中，为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock？

①、粒度降低了；

②、JVM 开发团队没有放弃 synchronized，而且基于 JVM 的 synchronized 优化空间更大，更加自然。

③、在大量的数据操作下，对于 JVM 的内存压力，基于 API 的 ReentrantLock 会开销更多的内存。

1.5 常见问题

1.5.1fail-fast 和 fail-safe 迭代器的区别

快速失败（fail-fast）：快速失败是Java集合的一种错误检测机制。

原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。

注意：这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。

场景：java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改），比如ArrayList 类。

安全失败（fail-safe）

采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。这种遍历基于容器的一个克隆。因此对容器中的内容修改不影响遍历。

原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发Concurrent Modification Exception。

缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。

场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改，比如CopyOnWriteArrayList类。常见的使用 fail-safe 方式遍历的容器有 ConcurrentHashMap 和 CopyOnWriteArrayList。

1.5.2Java 中线程安全的基本数据结构有哪些

HashTable、ConcurrentHashMap: 哈希表的线程安全版，效率上后者高；Vector、CopyOnWriteArrayList：线程安全版 Arraylist；Stack：线程安全版栈；BlockingQueue 及其子类：线程安全版队列。

1.5.3HashMap 和 Hashtable 的区别

• 线程安全：Hashtable 方法 sychonized 修饰，线程安全。建议使用ConcurrentHashMap替代Hashtable。
• 效率方面：由于 Hashtable 方法被 sychonized 修饰，效率比 HashMap 低
• 底层数据结构：HashMap jdk8 当链表长度>=8 并且数组长度>=64 链表会转红黑树，Hashtable 没有这样机制
• 初始容量与扩容：默认初始量：Hashtable 为 11，HashMap 为 16；若指定初始量：Hashtable 用指定的值，HashMap 会扩为 2 的幂次???。扩容：Hashtable 容量变为原来 2n+1 倍，HashMap 变为 2 倍。
• 对 Null key 与 Null value 支持：HashMap 支持一个 Null key 多个 Null value，Hashtable 不支持 Null key，否则报错空指针异常

1.5.4HashMap 并发线程安全问题？

HashMap不是线程安全的。

• 多线程下扩容死循环。JDK1.7 中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8 使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
• 多线程的 put 可能导致元素的丢失。多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在 JDK 1.7 和 JDK 1.8 中都存在。
• put 和 get 并发时，可能导致 get 为 null。线程 1 执行 put 时，因为元素个数超出 threshold 而导致 rehash，线程 2 此时执行 get，有可能导致这个问题。这个问题在 JDK 1.7 和 JDK 1.8 中都存在。

解决HashMap线程不安全方案：1、使用HashTable代替HashMap；2、使用Collections.synchronizedMap；3、使用ConcurrentHashMap代替HashMap。

• HashTable 是直接在操作方法上加 synchronized 关键字，锁住整个table数组，粒度比较大；
• Collections.synchronizedMap 是使用 Collections 集合工具的内部类，通过传入 Map 封装出一个 SynchronizedMap 对象，内部定义了一个对象锁，方法内通过对象锁实现；
• ConcurrentHashMap 在jdk1.7中使用分段锁，在jdk1.8中使用CAS+synchronized。

1.5.5hashmap 扩容流程

扩容时多线程操作可能会导致链表成环的出现，然后调? get ?法会死循环

触发时机：

1、未初始化，第一次 put 时；

2、大于扩容阈值。

流程：新建 2 倍大小的数组，根据新数组长度对其值重新 hash，寻址。具体会将原来数组链表拆为高低位链表，低位链表存放扩容后数组下标没变的结点，高位链表存放变了的，然后将高低位链表插入新数组

1.5.6TreeMap

TreeMap 是基于红黑树的一种提供顺序访问的 Map，主要是保证数据平衡，操作的时间复杂度都是 O(logn)；默认按键的升序排序，具体顺序可有指定的 comparator 决定。TreeMap 键、值都不能为 null；hashtable 也不能为 null。HashMap和TreeMap 都是非线性安全的，多线程并发情况建议使用ConcurrentHashMap；若既要保证线程安全又要保证顺序，可使用Collections.synchronizedMap()方法转化为线程安全的集合。

1.5.7List中的坑

1.Arrays.asList转换基本类型数组的坑

int[] arr = {1, 2, 3}; 
List list = Arrays.asList(arr); 
System.out.println(list.size()); 
// 1   想要转成的List应该是有三个对象而现在只有一个

源码中asList方法接收的是一个泛型T类型的参数，T继承Object对象。通过断点我们可以看到把 int数组 整体作为一个对象,返回了一个 List<int[]>。

解决方案：

方案一：Java8以上，利用Arrays.stream(arr).boxed()将装箱为Integer数组。

List collect = Arrays.stream(arr).boxed().collect(Collectors.toList()); 
System.out.println(collect.size()); 
System.out.println(collect.get(0).getClass()); 
// 3 
// class java.lang.Integer

方案二：声明数组的时候，声明类型改为包装类型。

Integer[] integerArr = {1, 2, 3}; 
List integerList = Arrays.asList(integerArr); 
System.out.println(integerList.size()); 
System.out.println(integerList.get(0).getClass()); 
// 3 
// class java.lang.Integer

2.Arrays.asList返回的List不支持增删操作

private static void asListAdd(){     
  String[] arr = {"1", "2", "3"};
  List strings = Arrays.asList(arr); 
  // 解决方案：new ArrayList<>(Arrays.asList(arr));
  // 修改后iterator.remove()不会抛异常   
  // List<String> strings = new ArrayList<>(Arrays.asList(arr));     
  arr[2] = "4";     
  System.out.println(strings.toString());     
  Iterator<String> iterator = strings.iterator();     
  while (iterator.hasNext()){         
    if ("4".equals(iterator.next())){             
      iterator.remove(); // 抛java.lang.UnsupportedOperationException     
    }     
  }
} 

Arrays.asList(arr) 返回的 ArrayList 不是 java.util.ArrayList，而是 Arrays的内部类，它没有实现 AbstractList 中的 add() 和 remove() 方法，所以不支持新增和删除。

3.Arrays.asList返回的List会随原始数组的修改而变化

asList中创建了ArrayList，但是他直接引用了原本的数组对象所以只要原本的数组对象一发生变化，List也跟着变化，所以在使用到引用的时候，我们需要特别的注意。

解决方案：重新new一个新的 ArrayList 来装返回的 List。

List strings = new ArrayList<>(Arrays.asList(arr));

4.ArrayList不当增删操作

详见1.3.6

foreach中操作增删，因为 modCount 会被修改，与第一步保存的数组修改次数不一致，抛出异常ConcurrentModificationException，正确操作：

5.ArrayList的 subList 强转 ArrayList 导致异常

ArrayList的sublist结果不可強转成ArrayList,否则会抛出ClassCastException异常，即java.util.RandomAccesSubList cannot be cast to java. util.ArrayList。

说明: subList 返回的是ArrayList 的内部类SubList, 并不是ArrayList ，而是ArrayList的一个视图，対于SubList子列表的所有操作最终会反映到原列表上。

private static void subListTest(){
  List<String> names = new ArrayList<String>() {{
    add("one");
    add("two");
    add("three");
  }};
  // ArrayList strings = (ArrayList) names.subList(0, 1);// 错误操作，抛异常
  // System.out.println(strings.toString());
  // List strings1= names.subList(0, 1); // 此操作不能增删元素
  // 解决ConcurrentModificationException异常，用new ArrayList(names.subList(0, 1))
  List strings1 = new ArrayList(names.subList(0, 1));
  strings.add(0, "ongChange");
  System.out.println(strings1.toString()); // [ongChange, one]
  System.out.println(names.toString()); // [ongChange, one, two, three]
  names.add("four"); // 错误操作，导致modCount不一致
  System.out.println(strings1.toString()); // 抛java.util.ConcurrentModificationException
  System.out.println(names.toString());
}

解决方案：在操作SubList的时候，new一个新的ArrayList来接收创建subList结果的拷贝

List strings = new ArrayList(names.subList(0, 1));

6.ArrayList的 subList 切片造成OOM

subList所产生的List，其实是对原来List对象的引用，产生的List只是原来List对象的视图，也就是说虽然值切片获取了一小段数据，但是原来的List对象却得不到回收，原来的List对象若是一个很大的对象，就可能导致OOM。为了方便我们测试，将vm调整一下 -Xms20m -Xmx40m

private static void subListOomTest(){
  IntStream.range(0, 1000).forEach(i ->{
    List<Integer> collect = IntStream.range(0, 100000).boxed().collect(Collectors.toList());
    data.add(collect.subList(0, 1));
  });
}

循环1000次创建了1000个具有10万个元素的List，因为始终被collect.subList(0, 1)强引用，得不到回收。

解决方式：

方式一：在subList方法返回后，重新使用new ArrayList，来构建一个独立的ArrayList。

List list = new ArrayList<>(collect.subList(0, 1));

方式二：利用Java8的Stream中的skip和limit来达到切片的目的。

List list = collect.stream().skip(0).limit(1).collect(Collectors.toList());

方式三：用一个新的容器来装结果，切断与原始List的关系。

7.LinkedList的插入速度不一定比ArrayList快

• 对于数组，随机元素访问的时间复杂度是0(1)，元素插入操作是O(n)；
• 对于链表，随机元素访问的时间复杂度是O(n)，元素插入操作是0(1)。

元素插入对于链表来说应该是他的优势，但是它就一定比数组快? 我们执行插入1000w次的操作。

private static void test(){
  StopWatch stopWatch = new StopWatch();
  int elementCount = 100000;
  stopWatch.start("ArrayList add");
  List<Integer> arrayList = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toCollection(ArrayList::new));
  // ArrayList插入数据
  IntStream.rangeClosed(0, elementCount).forEach(i ->arrayList.add(ThreadLocalRandom.current().nextInt(elementCount), 1));
  stopWatch.stop();


  stopWatch.start("linkedList add");
  List<Integer> linkedList = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toCollection(LinkedList::new));
  // ArrayList插入数据
  IntStream.rangeClosed(0, elementCount).forEach(i -> linkedList.add(ThreadLocalRandom.current().nextInt(elementCount), 1));
  stopWatch.stop();
  System.out.println(stopWatch.prettyPrint());
}


StopWatch '': running time = 44507882 ns
---------------------------------------------
ns         %     Task name
---------------------------------------------
043836412  098%  elementCount 100 ArrayList add
000671470  002%  elementCount 100 linkedList add


StopWatch '': running time = 196325261 ns
---------------------------------------------
ns         %     Task name
---------------------------------------------
053848980  027%  elementCount 10000 ArrayList add
142476281  073%  elementCount 10000 linkedList add


StopWatch '': running time = 26384216979 ns
---------------------------------------------
ns         %     Task name
---------------------------------------------
978501580  004%  elementCount 100000 ArrayList add
25405715399  096%  elementCount 100000 linkedList add

看到在执行插入1万、10完次操作的时候，LinkedList的插入操作时间是ArrayList的两倍以上。所以在实际的使用中，如果涉及到头尾对象的操作，可以使用LinkedList数据结构来进行增删的操作，发挥LinkedList的优势。

8.CopyOnWriteArrayList内存占用过多

CopyOnWrite，顾名思义就是写的时候会将共享变量新复制一份出来，这样做的好处是读操作完全无锁。

CopyOnWriteArrayList的add()方法

public boolean add(E e) {
  // 获取独占锁
  final ReentrantLock lock = this.lock;
  lock.lock();
  try {
    // 获取array
    Object[] elements = getArray();
    // 复制array到新数组，添加元素到新数组
    int len = elements.length;
    Object[] newElements = Arrays.copyOf(elements, len + 1);
    newElements[len] = e;
    // 替换数组
    setArray(newElements);
    return true;
  } finally {
    // 释放锁
    lock.unlock();
  }
}

CopyOnWriteArrayList 内部维护了一个数组，成员变量 array 就指向这个内部数组，所有的读操作都是基于新的array对象进行的。

因为上了独占锁，所以如果多个线程调用add()方法只有一个线程会获得到该锁，其他线程被阻塞，知道锁被释放， 由于加了锁，所以整个操作的过程是原子性操作，CopyOnWriteArrayList 会将新的array复制一份，然后在新复制处理的数组上执行增加元素的操作，执行完之后再将复制的结果指向这个新的数组。

由于每次写入的时候都会对数组对象进行复制，复制过程不仅会占用双倍内存，还需要消耗 CPU 等资源，所以当列表中的元素比较少的时候，这对内存和 GC 并没有多大影响，但是当列表保存了大量元素的时候，对 CopyOnWriteArrayList 每一次修改，都会重新创建一个大对象，并且原来的大对象也需要回收，这都可能会触发 GC，如果超过老年代的大小则容易触发Full GC，引起应用程序长时间停顿。

9.CopyOnWriteArrayList是弱一致性的

public Iterator<E> iterator() {
  return new COWIterator<E>(getArray(), 0);
}
static final class COWIterator<E> implements ListIterator<E> {
  /** Snapshot of the array */
  private final Object[] snapshot;
  /** Index of element to be returned by subsequent call to next.  */
  private int cursor;
  private COWIterator(Object[] elements, int initialCursor) {
    cursor = initialCursor;
    snapshot = elements;
  }
  public boolean hasNext() {
    return cursor < snapshot.length;
  }


  public boolean hasPrevious() {
    return cursor > 0;
  }
  @SuppressWarnings("unchecked")
  public E next() {
    if (! hasNext())
      throw new NoSuchElementException();
    return (E) snapshot[cursor++];
  }
}  

源码中看到调用iterator方法获取迭代器返回一个COWIterator对象，COWIterator的构造器里主要是保存了当前的list对象的内容和遍历list时数据的下标。snapshot是list的快照信息，因为CopyOnWriteArrayList的读写策略中都会使用getArray()来获取一个快照信息，生成一个新的数组。所以在使用该迭代器元素时，其他线程对该lsit操作是不可见的，因为操作的是两个不同的数组所以造成弱一致性。

private static void CopyOnWriteArrayListTest(){
  CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList();
  list.add("test1");
  list.add("test2");
  list.add("test3");
  list.add("test4");
  Thread thread = new Thread(() -> {
    System.out.println(">>>> start");
    list.add(1, "replaceTest");
    list.remove(2);
  });   
  // 在启动线程前获取迭代器
  Iterator<String> iterator = list.iterator();
  thread.start();
  try {
    // 等待线程执行完毕
    thread.join();
  } catch (InterruptedException e) {
    e.printStackTrace();
  }
  while (iterator.hasNext()){
    System.out.println(iterator.next());
  }
}


>>>> start
test1
test2
test3
test4

上面的demo中在启动线程前获取到了原来list的迭代器，在之后启动新建一个线程，在线程里面修改了第一个元素的值，移除了第二个元素，在执行完子线程之后，遍历了迭代器的元素，发现子线程里面操作的一个都没有生效，这里提现了迭代器弱一致性。

10.CopyOnWriteArrayList的迭代器不支持增删改

private static void CopyOnWriteArrayListTest(){
  CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
  list.add("test1");
  list.add("test2");
  list.add("test3");
  list.add("test4");
  Iterator<String> iterator = list.iterator();
  while (iterator.hasNext()){
    if ("test1".equals(iterator.next())){
      iterator.remove();// 抛java.lang.UnsupportedOperationException
    }
  }
  System.out.println(list.toString());
}

CopyOnWriteArrayList 迭代器是只读的，不支持增删操作CopyOnWriteArrayList迭代器中的 remove()和 add()方法，没有支持增删而是直接抛出了异常，因为迭代器遍历的仅仅是一个快照，而对快照进行增删改是没有意义的。