Java面试知识点总结-集合类 - 图1

容器类概览

Map

HashMap

HashMap 主要用来存放键值对，它基于哈希表的Map接口实现，是常用的Java集合之一。JDK1.8 之前 HashMap 由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。
HashMap：它根据键的 hashCode 值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null ，允许多条记录的值为 null 。HashMap 非线程安全，即任一时刻可以有多个线程同时写 HashMap ，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections 的 synchronizedMap 方法使 HashMap 具有线程安全的能力，或者使用 ConcurrentHashMap

HashMap的基本结构

HashMap具有数组+链表+红黑树（JDK1.8增加了红黑树部分）的结构。
Java面试知识点总结-集合类 - 图2

// 基本的 Hash 桶节点
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

HashMap核心字段

int threshold;             // 所能容纳的key-value对极限  
final float loadFactor;    // 负载因子 
int modCount;              // 修改次数
int size;                  // Node数量

Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。结合负载因子的定义公式可知，threshold 就是在此 Load factor 和 length (数组长度)对应下允许的最大元素数目，超过这个数目就重新resize (扩容)。扩容后的 HashMap 容量是之前容量的两倍。默认的负载因子 0.75 是对空间和时间效率的一个平衡选择。如果内存空间很多而又对时间效率要求很高，可以降低负载因子 Load factor 的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子 load factor 的值，这个值可以大于1。
size 这个字段其实很好理解，就是 HashMap 中实际存在的键值对数量。注意和 table 的长度 length 、容纳最大键值对数量 threshold的区别。而 modCount 字段主要用来记录 HashMap 内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如 put 新键值对，但是某个 key 对应的 value 值被覆盖不属于结构变化。

HashMap的几个构造函数

不传任何值：仅把负载因子设定为默认负载因子
传一个Map类的参数：把负载因子设定为默认负载因子并调用putMapEntries(Map<? extends K, ? extends V> m, boolean evict)执行复制
传一个capacity值：调用下面的构造函数
传一个capacity值与loadFactor：对阈值与负载因子进行初始化

HashMap的长度为什么是2的幂次方
为了能让 HashMap 存取高效且尽量不发生碰撞，就要实现数据分配的均匀。Hash 值的范围值 -2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般很难出现碰撞。问题在于一个 40 亿长度的数组，内存容量将会是瓶颈。在存放数据前先计算目标对象的哈希码，然后对数组大小取模运算，得到的余数才是真正的数组下标。这个数组下标的计算方法是 (n - 1) & hashcode。（n代表数组长度）。取余 % 操作中如果除数是2的幂次则等价于与其除数减一的与 & 操作(也就是说 hash % length == hash & (length-1) is true 的前提是 length 是2的 n 次方)。采用二进制位操作 & ，相对于 % 能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方
在扩容时，每次桶数量(数组大小)翻倍的机制可以用于双链再哈希，详细过程可参考扩容的相关介绍

HashMap的快速失败机制
java.util.HashMap 线程不安全，因此如果在使用迭代器的过程中有其他线程修改了 HashMap，那么将抛出
ConcurrentModificationException ，这就是所谓 fail-fast 策略。在 HashMap 中，有一个变量 modCount 来指示集合被修改的次数。在创建 Iterator 迭代器的时候，会给这个变量赋值给 expectedModCount 。当集合方法修改集合元素时，例如集合的 remove() 方法时，此时会修改 modCount 值，但不会同步修改 expectedModCount 值。当使用迭代器遍历元素操作时，会首先对比 expectedModCount 与 modCount 是否相等。如果不相等，则马上抛出 java.util.ConcurrentModificationException异常。而通过Iterator的remove()方法移除元素时，会同时更新 expectedModCount 的值，将 modCount 的值重新赋值给 expectedModCount，这样下一次遍历时，就不会发抛出 java.util.ConcurrentModificationException 异常。上述机制可以解释为什么 HashMap 通过迭代器自身的 remove 或 add 方法就不会出现迭代器失败。

HashMap定位桶下标的方法
```
static final int hash(Object key) {   //jdk1.8 & jdk1.7 
   in th; 
   // h = key.hashCode() 为第一步 取hashCode值 
   // h ^ (h >>> 16)  为第二步 高位参与运算 
   return(key == null) ? 0: (h = key.hashCode()) ^ (h >>> 16); 
} 
static int indexFor(int h,int length) {  //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的 
   return h & (length-1); //第三步 取模运算 
}
```
这里 Hash 算法本质上就是三步：取 key 的 hashCode 值、高位运算、取模运算。对于任意给定的对象，只要它的 hashCode() 返回值相同，那么程序调用方法一所计算得到的 Hash 码值总是相同的。首先想到的就是把 hash 值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，模运算的消耗还是比较大的，在 HashMap 中是这样做的：调用方法二来计算该对象应该保存在 table 数组的哪个索引处。这个方法非常巧妙，它通过 h & (table.length -1) 来得到该对象的保存位，而 HashMap 底层数组的长度总是 2 的 n 次方，这是 HashMap 在速度上的优化。当 length 总是2的n次方时，h & (length-1) 运算等价于对length取模，也就是 h % length，但是 & 比 % 具有更高的效率。
在 JDK1.8 的实现中，优化了高位运算的算法，通过 hashCode() 的高 16 位异或低 16 位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

HashMap的Put方法

1.8版本以前的流程：
如果定位到的数组位置没有元素就直接插入
如果定位到的数组位置有元素，遍历以这个元素为头结点的链表，依次和插入的key比较，如果key相同就直接覆盖，不同就采用头插法插入元素

值得注意的是，在put的执行流程中，当判断key是否存在时，使用了如下的判断方法：

if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
    break;
public V put(K key, V value) { 
    // 对key的hashCode()做hash 
    return putVal(hash(key), key, value, false, true); 
} 
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为空则创建 
    if ((tab = table) == null || (n = tab.length) == 0) 
        n = (tab = resize()).length; 
    // 步骤②：计算index，并对null做处理  
    if ((p = tab[i = (n - 1) & hash]) == null)  
        tab[i] = newNode(hash, key, value, null); 
    else { 
        Node<K,V> e; K k; 
        // 步骤③：节点key存在，直接覆盖value 
        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); 
                       //链表长度大于8转换为红黑树进行处理 
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st   
                        treeifyBin(tab, hash); 
                    break; 
                } 
                   // key已经存在直接覆盖value 
                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; 
}

简述get()流程

通过 hash & (table.length - 1)获取该key对应的数据节点的hash槽;
判断首节点是否为空, 为空则直接返回空;
再判断首节点.key 是否和目标值相同, 相同则直接返回(首节点不用区分链表还是红黑树);
首节点.next为空, 则直接返回空;
首节点是树形节点, 则进入红黑树数的取值流程, 并返回结果;

进入链表的取值流程, 并返回结果;

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 && // 总是检查链表第一个节点
            ((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;
}

简述resize()的过程

resize方法是HashMap中进行扩容的方法。扩容操作会带来极大的开销，因为会伴随着一次重新Hash分配，并遍历Hash表中的所有元素。在实际使用过程中要尽力避免。
Java面试知识点总结-集合类 - 图5
这里描述下链表的迁移过程：

// 下面这段就是把原来table里面的值全部搬到新的table里面
  if (oldTab != null) {
      for (int j = 0; j < oldCap; ++j) {
          Node<K,V> e;
          if ((e = oldTab[j]) != null) {
              // 这里注意, table中存放的只是Node的引用, 这里将oldTab[j]=null只是
              //清除旧表的引用, 但是真正的node节点还在, 只是现在由e指向它
              oldTab[j] = null;
              // 如果该存储桶里面只有一个bin, 就直接将它放到新表的目标位置
              if (e.next == null)
                  newTab[e.hash & (newCap - 1)] = e;
              // 如果该存储桶里面存的是红黑树, 则拆分树
              else if (e instanceof TreeNode)
                  //红黑树的部分以后有机会再讲吧
                  ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
              // 下面这段代码很精妙, 我们单独分一段详细来讲
              else { // preserve order
                  Node<K,V> loHead = null, loTail = null;
                  Node<K,V> hiHead = null, hiTail = null;
                  Node<K,V> next;
                  do {
                      next = e.next;
                      if ((e.hash & oldCap) == 0) {
                          if (loTail == null)
                              loHead = e;
                          else
                              loTail.next = e;
                          loTail = e;
                      }
                      else {
                          if (hiTail == null)
                              hiHead = e;
                          else
                              hiTail.next = e;
                          hiTail = e;
                      }
                  } while ((e = next) != null);
                  if (loTail != null) {
                      loTail.next = null;
                      newTab[j] = loHead;
                  }
                  if (hiTail != null) {
                      hiTail.next = null;
                      newTab[j + oldCap] = hiHead;
                  }
              }
          }
      }
  }

首先，定义了两个新的链表分别是： lo 链表与 hi 链表，其中 loHead 与 hiHead 指向头部， loTail 与 hiTail 指向尾部。然后，从旧 table 的某个桶的头部开始，逐一将桶内链表上的每一个节点迁移到 lo 链表或 hi 链表中。决定进入 lo 链表或 hi 链表的依据是判断条件：(e.hash & oldCap) == 0。下面解释下为什么采用这种判断依据。首先， oldCap 的大小必然是2的n次幂，newCap 的大小必然是2的n+1次幂，在求桶的下标时使用公式 (capacity-1)&hash ，这个公式本质上取出了 hash值的低 n 位，这个 n 对应于 n 次幂。然而，当迁移时需要计算在新 table 下的桶下标，这是使用的公式是 (2*capacity-1) & hash ，这样就会比原来多取出一位，而二进制只有0/1，这也与两个新链表 hi/lo 对应。(e.hash & oldCap) == 0时，这个节点应该被丢进 lo 链表，否则进入 hi 链表。在将原 table 上某个桶的一个链表全部拆完后，将这两个链表分别链接到新 table 对应的桶中，而这两个桶下标间存在一种数值上的关系，即二者差为一个原来的 table 长度——oldCap。
Java面试知识点总结-集合类 - 图6
有一点注意区别，JDK1.7 中 rehash 的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，但是 JDK1.8 不会倒置。

HashMap多线程安全性

fail-fast

如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。

死链

当需要调整HashMap的大小时，如果有多个线程同时尝试调整大小，可能会导致节点间的引用构成循环链而造成死循环。https://www.cnblogs.com/wang-meng/p/7582532.html

HashMap版本区别

简述1.8版本与1.8版本前HashMap在hash(key)的区别

1.8版本前：

static int hash(int h) {
  // This function ensures that hashCodes that differ only by
  // constant multiples at each bit position have a bounded
  // number of collisions (approximately 8 at default load factor).
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
}

1.8版本

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

相比于 JDK1.8 的 hash 方法，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。
1.7 插入节点采用头插法(倒置)；1.8 采用尾插法
1.7是数组+链表；1.8是数组+链表+红黑树
HashMap为何链表长度到8才扩展为红黑树
当HashCode的离散性强时，使用树形bin的概率极低，官方在源码给出如下数据：
```
0:    0.60653066
1:    0.30326533
2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006
```
可以看到，一个bin中链表长度达到8个元素的概率为0.00000006，几乎是不可能事件。之所以选择8是根据概率统计决定。
HashMap如何保证其容量为2的n次方
先考虑如何求一个数的掩码，对于 10010000，它的掩码为 11111111，可以使用以下方法得到：
```
mask |= mask >> 1    11011000
mask |= mask >> 2    11111110
mask |= mask >> 4    11111111
```
mask+1 是大于原始数字的最小的 2 的 n 次方。 ```java num 10010000 mask+1 100000000

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

<a name="3prnZ"></a>
## HashTable
Hashtable：Hashtable 是遗留类，很多映射的常用功能与 HashMap 类似，不同的是它承自 Dictionary类，并且是线程安全的，任一时间只有一个线程能写 Hashtable ，并发性不如 ConcurrentHashMap ，因为 ConcurrentHashMap 引入了分段锁。 Hashtable 不建议在新代码中使用，不需要线程安全的场合可以用 HashMap 替换，需要线程安全的场合可以用 ConcurrentHashMap 替换
<a name="KkCEC"></a>
## LinkedHashMap
LinkedHashMap 是 HashMap 的一个子类，保存了记录的插入顺序，在用 Iterator 遍历 LinkedHashMap 时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序
<a name="cpGv4"></a>
## TreeMap
TreeMap 实现 SortedMap 接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的。如果使用排序的映射，建议使用 TreeMap 。在使用 TreeMap 时，key 必须实现 Comparable 接口或者在构造 TreeMap 传入自定义的 Comparator ，否则会在运行时抛出 java.lang.ClassCastException 类型的异常
<a name="rJ0J6"></a>
### TreeMap的实现
<a name="MGMZa"></a>
#### 节点
```java
static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;
}

红黑树的节点是用Entry类表示的，该类包括两个指向左右两个孩子节点的指针left、right，一个指向父亲节点的指针parent，表示当前颜色的变量color,默认为黑色。K泛型的key表示键，V泛型的value表示值。

插入算法

首先执行二叉搜索树的插入算法，保证左子树的关键字最大不超过x.key，右子树的关键字最小不低于x.key。

Entry<K,V> t = root;
if (t == null) { 
    @1
    compare(key, key); // type (and possibly null) check
    root = new Entry<>(key, value, null);
    size = 1;
    modCount++;
    return null;
}
@2
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
    do {
        parent = t;
        cmp = cpr.compare(key, t.key);
        if (cmp < 0)
            t = t.left;
        else if (cmp > 0)
            t = t.right;
        else  @3
            return t.setValue(value);
    } while (t != null);
}
else {
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
    Comparable<? super K> k = (Comparable<? super K>) key;
    do {
        parent = t;
        cmp = k.compareTo(t.key);
        if (cmp < 0)
            t = t.left;
        else if (cmp > 0)
            t = t.right;
        else
            return t.setValue(value);
    } while (t != null);
}
@4
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
    parent.left = e;
else
    parent.right = e;

@1 表示根节点为空的情况直接插入到根节点
@2 表示根节点非空，通过传入的Comparator或者key自身实现的Comparable来比较key的值，先从根部节点比较。
@3 如果key的值与比较节点的值相同，直接将value赋给节点返回。
@4 如果key.value < root.value，接下来比较key与root左子树的值；如果key.value > root.value,接下来比较key与root右子树的值。以此循环，直到要比较的节点为空,将新节点插入该位置。

插入后的颜色修复

经过二叉搜索树的插入算法，此时树已满足二叉搜索树的条件，接下来在不破坏二叉搜索树性质的条件下对颜色修复使得该树满足红黑树的性质。
如果新插入的节点非根节点，并且父亲是红色，因为它自身也是红色，因此违反了性质4，需要调整颜色。
下面以父节点是左孩子的判断分支分析，父节点是右孩子的状况具有对称性，不重复推导。

情况一，叔节点是红色

如果当前节点x的父亲是左节点，并且和叔节点y（父亲的兄弟节点）都是红色，这时候父亲的父亲节点必须是黑色的，否则不满足性质4。将父亲x,p和叔节点y都染成黑色，将父亲的父亲x.p.p节点染成红色。此时插入的节点x、插入节点的父亲节点x.p、叔节点y都满足红黑树性质，但是父亲的父亲节点x.p.p被染成红色后未必还满足红黑树性质，所以将x设置为x.p.p节点，交给下个迭代解决。
Java面试知识点总结-集合类 - 图7
红黑树插入情况一.png

情况二，当前的节点是右孩子，叔节点是黑色

如果x是右孩子，将x设置成x.p，对x左旋。
Java面试知识点总结-集合类 - 图8
红黑树插入情况二.png

情况三，当前节点是左孩子，叔节点y是黑色

将x的父亲节点x.p染成黑色，再将x节点的父亲的父亲x.p.p染成红色。
Java面试知识点总结-集合类 - 图9
红黑树情况三变色.png
将x.p.p右旋。
Java面试知识点总结-集合类 - 图10
红黑树情况三右旋.png
经过上述步骤的变化现在已经成为一颗符合性质的红黑树。
三种情况针对父亲节点是左孩子的情况，父亲是右孩子的情况可以根据三种情况反推。

插入算法小结

因为一颗有n个节点的红黑树，其高度为lg n，二叉搜索树的插入最多执行O(lg n)的时间。而颜色修复在情况一沿着树上升2层，循环才会重复执行。循环可能执行的总数为O(lg n),一旦进入情况2或3，下面执行的旋转不超过2次，循环就结束了。所以红黑树的插入算法时间是O(lg n)。

删除算法

首先通过getEntry找到与key对应的节点，然后调用deleteEntry方法删除节点。
首先根据二叉搜索树的删除算法删除节点，具体表现为:

如果删除的节点没有子树，直接删除，如果它是黑色的，从哨兵节点开始颜色修复。
如果删除的节点只有一个子树，用它的孩子节点替换它，如果它是黑色的，从它的孩子开始执行颜色修复。
如果删除的节点有双子树，用右子树最小的节点替换它，并对最小节点的右节点执行颜色修复。

删除算法小结
因为包含n个节点的红黑树高度为O(lg n),因此执行二叉搜索树的删除算法时间效率为O(lg n)，在执行删除后的颜色调整时，情况1、3、4执行至多三次旋转便能终止。情况2最多循环数的高度O(lg n)，且不会执行旋转。所以红黑树的删除时间为O(lg n)。

WeakHashMap
WeakHashMap特点是，当除了自身有对key的引用外，此key没有其他引用，那么WeakHashMap会在下次对WeakHashMap进行增删改查操作时及时丢弃该键值对，节约内存使用，此特性使得WeakHashMap非常适合构建缓存系统。
WeakHashMap是主要通过expungeStaleEntries函数的来实现移除其内部不用的entry从而达到的自动释放内存的目的。基本上只要对WeakHashMap的内容进行访问就会调用expungeStaleEntries函数，从而达到清除不再被外部引用的key对应的entry键值对。如果预先生成了WeakHashMap，而在GC以前又不曾访问该WeakHashMap,那么因为没有机会调用expungeStaleEntries函数，因此并不会回收不再被外部引用的key对应的entry。
Entry键值对
WeakHashMap的键值对Entry继承自WeakReference，并实现了Map.Entry
```
private static class Entry<K,V> extends 
 WeakReference<Object> implements Map.Entry<K,V>
```
当弱引用指向的对象只能通过弱引用（没有强引用或弱引用）访问时，GC会清理掉该对象，之后，引用对象会被放到ReferenceQueue中。在Entry的构造函数中可以得知，通过super(key, queue)将key保存为弱引用，通过this.value = value将value保存为强引用。当key中的引用被gc掉之后，在下次访问WeakHashMap（调用expungeStaleEntries函数）时相应的entry也会自动被移除。
```
     /**
      * Creates new entry.
      */
     Entry(Object key, V value,
           ReferenceQueue<Object> queue,
           int hash, Entry<K,V> next) {
         super(key, queue);
         this.value = value;
         this.hash  = hash;
         this.next  = next;
     }
```
expungeStaleEntries()：清除过期的条目
从ReferenceQueue中取出过期的entry，从WeakHashMap找到对应的entry，逐一删除。
expungeStaleEntries()清空table中无用键值对，原理如下：
当WeakHashMap中某个“弱引用的key”由于没有再被引用而被GC收回时，被回收的“该弱引用key”也被会被添加到”ReferenceQueue(queue)”中。

当我们执行expungeStaleEntries时，就遍历”ReferenceQueue(queue)”中的所有key后就在“WeakReference的table”中删除与“ReferenceQueue(queue)中key”对应的键值对

/**
  * Expunges stale entries from the table.
  */
private void expungeStaleEntries() {
 //首先通过循环一直从queue中取过期entry直到取完为止
 for (Object x; (x = queue.poll()) != null; ) {
     //然后通过加锁queue进行删除过期entry的操作
     synchronized (queue) {
         @SuppressWarnings("unchecked")
         Entry<K,V> e = (Entry<K,V>) x;
         int i = indexFor(e.hash, table.length);
         Entry<K,V> prev = table[i];
         Entry<K,V> p = prev;
         while (p != null) {
             Entry<K,V> next = p.next;
             if (p == e) {
                 //在同步代码块中先把从queue中取出的Object类型的数据强制转化为Entry
                 //对象e，然后计算此entry在桶的位置（table数组的下标i），
                 //然后开始遍历entry链表，如果此entry是链表头，设置此entry的后继为新
                 //的链表头
                 if (prev == e)
                     table[i] = next;
                 //否则将此entry的前序节点的后继指针指向此entry的后继节点
                 else
                     prev.next = next;
                 // Must not null out e.next;
                 // stale entries may be in use by a HashIterator
                 //最后设置被删除的entry的value为null，加速垃圾回收，接着修改size
                 e.value = null; // Help GC
                 size--;
                 break;
             }
             prev = p;
             p = next;
         }
     }
 }
}

从表中删除过时的条目流程：

首先通过循环一直从queue中取过期entry直到取完为止
然后通过加锁queue进行删除过期entry的操作
在同步代码块中先把从queue中取出的Object类型的数据强制转化为Entry对象e，然后计算此entry在桶的位置（table数组的下标i），然后开始遍历entry链表，如果此entry是链表头，设置此entry的后继为新的链表头
否则将此entry的前序节点的后继指针指向此entry的后继节点
最后设置被删除的entry的value为null，加速垃圾回收，接着修改size

WeakHashMap的增删改查操作都会直接或者间接的调用expungeStaleEntries()方法，达到及时清除过期entry的目的。
此特性会到导致两次调用size、get等方法可能会返回不一致的数据。
在tomcat的源码里，实现缓存时会用到WeakHashMap。

package org.apache.tomcat.util.collections;
import java.util.Map;
import java.util.WeakHashMap;
import java.util.concurrent.ConcurrentHashMap;
public final class ConcurrentCache<K,V> {
    private final int size;
    private final Map<K,V> eden;
    private final Map<K,V> longterm;
    public ConcurrentCache(int size) {
        this.size = size;
        this.eden = new ConcurrentHashMap<>(size);
        this.longterm = new WeakHashMap<>(size);
    }
    public V get(K k) {
        V v = this.eden.get(k);
        if (v == null) {
            synchronized (longterm) {
                v = this.longterm.get(k);
            }
            if (v != null) {
                this.eden.put(k, v);
            }
        }
        return v;
    }
    public void put(K k, V v) {
        if (this.eden.size() >= size) {
            synchronized (longterm) {
                this.longterm.putAll(this.eden);
            }
            this.eden.clear();
        }
        this.eden.put(k, v);
    }
}

源码中有eden和longterm的两个map，对jvm堆区有所了解的话，可以猜测出tomcat在这里是使用ConcurrentHashMap和WeakHashMap做了分代的缓存。在put方法里，在插入一个k-v时，先检查eden缓存的容量是不是超了。没有超就直接放入eden缓存，如果超了则锁定longterm将eden中所有的k-v都放入longterm。再将eden清空并插入k-v。在get方法中，也是优先从eden中找对应的v，如果没有则进入longterm缓存中查找，找到后就加入eden缓存并返回。
经过这样的设计，相对常用的对象都能在eden缓存中找到，不常用（有可能被销毁的对象）的则进入longterm缓存。而longterm的key的实际对象没有其他引用指向它时，gc就会自动回收heap中该弱引用指向的实际对象，弱引用进入引用队列。longterm调用expungeStaleEntries()方法，遍历引用队列中的弱引用，并清除对应的Entry，不会造成内存空间的浪费。

ConcurrentHashMap原理

ConcurrentHashMap不是Collection接口下的直接实现类
ConcurrentHashMap 和 HashMap 实现上类似，最主要的差别是1.7中 ConcurrentHashMap 采用了分段锁（Segment），每个分段锁维护着几个桶（HashEntry），多个线程可以同时访问不同分段锁上的桶，从而使其并发度更高（并发度就是Segment的个数）。其中 Segment 继承自 ReentrantLock 。默认的并发级别为16，也就是说默认创建 16 个 Segment 。JDK1.8 使用了 CAS 操作来支持更高的并发度，在 CAS 操作失败时使用内置锁 synchronized。并且 JDK1.8 的实现也在链表过长时会转换为红黑树。

ConcurentHashMap的put方法

先判断 key 与 value 是否为空。与 HashMap 不同，ConcurrentHashMap 不允许 null 作为 key 或 value 。这是因为 ConcurrentHashmap 支持并发。当通过 get(key) 获取对应的 value 时，如果获取到的是 null 时，无法判断它是put(key,value) 的时候 value 为 null ，还是这个 key 从来没有做过映射。 HashMap 是非并发的，可以通过 contains(key) 来做这个判断。而支持并发的 Map 在调用 m.contains(key)和 m.get(key)，可能已经不同了；
计算 hash 值来确定放在数组的哪个位置
判断当前 table 是否为空，空的话初始化 table
根据重哈希算出的值通过与运算得到桶索引，利用 Unsafe 类直接获取内存内存中对应位置上的节点，若没有碰撞即桶中无结点 CAS 直接添加
如果取出来的节点的 hash 值是 MOVED(-1) 的话，则表示当前正在对这个数组进行扩容，复制到新的数组，则当前线程也去帮助复制
最后一种情况就是，如果这个节点，不为空，也不在扩容，则通过 synchronized 来加锁，进行添加操作

其他部分同 HashMap 中的操作

final V putVal(K key, V value, boolean onlyIfAbsent) {
  if (key == null || value == null) throw new NullPointerException();
  //K,V都不能为空，否则的话跑出异常
  int hash = spread(key.hashCode());    //取得key的hash值
  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();    //第一次put的时候table没有初始化，则初始化table
      else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {    
          //通过哈希计算出一个表中的位置因为n是数组的长度，所以(n-1)&hash肯定不会出现数组越界
          if (casTabAt(tab, i, null,        
                       //如果这个位置没有元素的话，则通过cas的方式尝试添加，
                       //注意这个时候是没有加锁的
                 new Node<K,V>(hash, key, value, null)))        
              //创建一个Node添加到数组中区，null表示的是下一个节点为空
              break;                   
          // no lock when adding to empty bin
      }
      /*
           * 如果检测到某个节点的hash值是MOVED，则表示正在进行数组扩张的数据复制阶段，
           * 则当前线程也会参与去复制，通过允许多线程复制的功能，
           *一次来减少数组的复制所带来的性能损失
           */
      else if ((fh = f.hash) == MOVED)   
          tab = helpTransfer(tab, f);
      else {
          /*
               * 如果在这个位置有元素的话，就采用synchronized的方式加锁，
               *     如果是链表的话(hash大于0)，就对这个链表的所有元素进行遍历，
               *         如果找到了key和key的hash值都一样的节点，则把它的值替换到
               *         如果没找到的话，则添加在链表的最后面
               *  否则，是树的话，则调用putTreeVal方法添加到树中去
               * 
               *  在添加完之后，会对该节点上关联的的数目进行判断，
               *  如果在8个以上的话，则会调用treeifyBin方法，来尝试转化为树，或者是扩容
               */
          V oldVal = null;
          synchronized (f) {
              if (tabAt(tab, i) == f) {        
                  //再次取出要存储的位置的元素，跟前面取出来的比较
                  if (fh >= 0) {               
                      //取出来的元素的hash值大于0，当转换为树之后，hash值为-2
                      binCount = 1;           
                      for (Node<K,V> e = f;; ++binCount) {    
                          //遍历这个链表
                          K ek;
                          if (e.hash == hash &&       
                              //要存的元素的hash，key跟要存储的位置的节点的相同的时候，
                              //替换掉该节点的value即可
                              ((ek = e.key) == key ||
                               (ek != null && key.equals(ek)))) {
                              oldVal = e.val;
                              if (!onlyIfAbsent)        
                                  //当使用putIfAbsent的时候，
                                  //只有在这个key没有设置值得时候才设置
                                  e.val = value;
                              break;
                          }
                          Node<K,V> pred = e;
                          if ((e = e.next) == null) {    
                              //如果不是同样的hash，同样的key的时候，
                              //则判断该节点的下一个节点是否为空，
                              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,   
                          //调用putTreeVal方法，将该元素添加到树中去
                            value)) != null) {
                          oldVal = p.val;
                          if (!onlyIfAbsent)
                              p.val = value;
                      }
                  }
              }
          }
          if (binCount != 0) {
              if (binCount >= TREEIFY_THRESHOLD)    
                  //当在同一个节点的数目达到8个的时候，则扩张数组或将给节点的数据转为tree
                  treeifyBin(tab, i);   
              if (oldVal != null)
                  return oldVal;
              break;
          }
      }
  }
  addCount(1L, binCount);    //计数
  return null;
}

在 1.7 版本的多线程场景下，如果有多个线程同时执行 put 时，如果其他线程已经获取到 Segment 的锁，那么当前未获得锁的线程会以自旋的方式去继续调用 tryLock() 方法去获取锁，超过指定次数会挂起，等待唤醒。
关于 put 中对 CAS 和 synchronized 的使用：

CAS 用于当桶为空时，使用 cas 尝试加入新的桶头结点
synchronized 用于桶不为空时，向链表或树中 put 结点的情形

ConcurentHashMap的get方法
当key为null的时候回抛出NullPointerException的异常
get操作通过首先计算key的hash值来确定该元素放在数组的哪个位置
判断table是否为空且table长度大于0且下标不为空
然后遍历该位置的所有节点
如果均无法定位到key则返回null

ConcurentHashMap的resize方法
当需要扩容的时候，调用的时候tryPresize方法。在tryPresize方法中，并没有加锁，允许多个线程进入，如果数组正在扩张，则当前线程也去帮助扩容。值得注意的是，复制之后的新链表不是旧链表的绝对倒序；在扩容的时候每个线程都有处理的步长，最少为16，在这个步长范围内的数组节点只有自己一个线程来处理。整个操作是在持有段锁的情况下执行。

ConcurrentHashMap的remove流程
remove 操作也是确定需要删除的元素的位置，不过这里删除元素的方法不是简单地把待删除元素的前面的一个元素的 next 域指向后面的节点。HashEntry 中的 next 是 final 修饰的，一经赋值以后就不可修改。在定位到待删除元素的位置以后，程序就将待删除元素前面的那一些元素全部复制一遍，然后再一个一个重新接到链表上去。从源码来看，就是将定位之后的所有entry克隆并拼回前面去。这意味着每次删除一个元素就要将那之前的元素克隆一遍。这其实是由entry的不变性来决定的，仔细观察entry定义，发现除了value，其他所有属性都是用 final 来修饰的，这意味着在第一次设置了 next 域之后便不能再改变它，取而代之的是将它之前的节点全都克隆一次。至于 entry 为什么要设置为不变性，这跟不变性的访问不需要同步从而节省时间有关。
```
V remove(Object key, int hash, Object value) {
  lock();
  try {
      int c = count - 1;
      HashEntry<K,V>[] tab = table;
      int index = hash & (tab.length - 1);
      HashEntry<K,V> first = tab[index];
      HashEntry<K,V> e = first;
      while (e != null && (e.hash != hash || !key.equals(e.key)))
          e = e.next;
      V oldValue = null;
      if (e != null) {
          V v = e.value;
          if (value == null || value.equals(v)) {
              oldValue = v;
              // All entries following removed node can stay
              // in list, but all preceding ones need to be
              // cloned.
              ++modCount;
              HashEntry<K,V> newFirst = e.next;
              for (HashEntry<K,V> p = first; p != e; p = p.next)
                  newFirst = new HashEntry<K,V>(p.key, p.hash,
                                                newFirst, p.value);
              tab[index] = newFirst;
              count = c; // write-volatile
          }
      }
      return oldValue;
  } finally {
      unlock();
  }
}
```
计算ConcurentHashMap的size大小
计算ConcurrentHashMap的元素大小是一个有趣的问题，因为可能存在并发操作。当计算 size 的时候，并发插入的数据可能会导致计算出来的 size 和实际的 size 有偏差，JDK1.7版本用两种方案：
第一种方案使用不加锁的模式去尝试多次计算 ConcurrentHashMap 的 size，最多三次，比较前后两次计算的结果，结果一致就认为当前没有元素加入，计算的结果是准确的
第二种方案是如果第一种方案不符合，就会给每个 Segment 加上锁，然后计算 ConcurrentHashMap 的 size 返回

ConcurrentHashMap中的remove方法
当要删除的结点存在时，删除的最后一步操作要将 count 的值减一。这必须是最后一步操作，否则读取操作可能看不到之前对段所做的结构性修改
remove 执行的开始就将 table 赋给一个局部变量 tab。这是因为 table 是 volatile 变量，读写volatile 变量的开销很大。编译器也不能对 volatile 变量的读写做任何优化，直接多次访问非 volatile 实例变量没有多大影响，编译器会做相应优化

ConcurrentHashMap的工作原理以及差异对比
ConcurrentHashMap 为了提高本身的并发能力，在内部采用了一个叫做 Segment 的结构，一个 Segment 其实就是一个类 Hash Table 的结构，Segment 内部维护了一个链表数组。ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作，第一次 Hash 定位到 Segment，第二次Hash定位到元素所在的链表的头部，因此，这一种结构的带来的副作用是Hash的过程要比普通的HashMap要长，但是带来的好处是写操作的时候可以只对元素所在的Segment进行操作即可，不会影响到其他的Segment，这样，在最理想的情况下，ConcurrentHashMap 可以最高同时支持 Segment 数量大小的写操作（刚好这些写操作都非常平均地分布在所有的 Segment上），所以，通过这一种结构，ConcurrentHashMap的并发能力可以大大的提高。JAVA7之前ConcurrentHashMap主要采用锁机制，在对某个Segment进行操作时，将该Segment锁定，不允许对其进行非查询操作，而在JAVA8之后采用CAS无锁算法，这种乐观操作在完成前进行判断，如果符合预期结果才给予执行，对并发操作提供良好的优化。
JDK1.7版本锁的粒度是基于Segment的，默认同时支持16个并发写，而 JDK1.8 的粒度就是 HashEntry（首节点）的数量
JDK1.8 版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用 synchronized 来进行同步，所以不需要分段锁的概念，也就不需要 Segment 这种数据结构。由于粒度的降低，实现的复杂度也增加了
JDK1.8使用红黑树来优化链表，基于较长的链表的遍历效率很低，而红黑树的遍历效率很高
JDK1.8为什么使用内置锁 synchronized 来代替重入锁 ReentrantLock，原因有以下几点：因为粒度降低了，在相对而言的低粒度加锁方式，synchronized 并不比 ReentrantLock 差，在粗粒度加锁中ReentrantLock 可能通过 Condition 来控制各个低粒度的边界，更加的灵活。而在细粒度中，Condition 的优势就没有了；在大量的数据操作下，基于 API 的 ReentrantLock 会有更多的内存开销

简述ConcurrentHashMap中变量使用final和volatile修饰的作用
final 可实现不变模式（immutable），是多线程安全里最简单的一种保障方式。不变模式主要通过 final 关键字来限定的。在 JMM 中 final 关键字还有特殊的语义。final 域使得确保初始化安全性（initialization safety）成为可能，初始化安全性让不可变形对象不需要同步就能自由地被访问和共享
使用 volatile 来保证某个变量内存的改变对其他线程即时可见，在配合 CAS 可以实现不加锁对并发操作的支持 remove 执行的开始就将 table 赋给一个局部变量 tab，将 tab 依次复制出来，最后直到该删除位置，将指针指向下一个变量

单线程Hashmap性能对标Concurenthashmap
1.8版本的concurentHashMap在单线程下和HashMap效率有什么区别
```
// 先对ConcurentHashMap测试，再对HashMap测试
loopcount                 HashMap(ms)               ConcurrentHashMap(ms)
1000                      60                        2                  
1000000                   123                       270                
10000000                  1099                      2014               
100000000                 8071                      14197
```
```
// 先对HashMap测试，再对ConcurentHashMap测试
loopcount                 HashMap(ms)               ConcurrentHashMap(ms)
1000                      1                         46                 
1000000                   96                        240                
10000000                  828                       2132               
100000000                 8692                      20234
```
通过两次压测表明，刨除编译优化以及代码预热的原因，在单线程场景下HashMap性能一直处于领先地位。

ConcurrentSkipListMap
ConcurrentSkipListMap是线程安全的有序的哈希表，适用于高并发的场景。
ConcurrentSkipListMap和TreeMap，它们虽然都是有序的哈希表。但是，第一，它们的线程安全机制不同，TreeMap是非线程安全的，而ConcurrentSkipListMap是线程安全的。第二，ConcurrentSkipListMap是通过跳表实现的，而TreeMap是通过红黑树实现的。
关于跳表(Skip List)，它是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，这样也就是说跳表的插入和删除的工作是比较简单的。
ConcurrentSkipListMap具有Skip list的性质，并且适用于大规模数据的并发访问。多个线程可以安全地并发执行插入、移除、更新和访问操作。与其他有锁机制的数据结构在巨大的压力下相比有优势。
TreeMap插入数据时平衡树采用严格的旋转（比如平衡二叉树有左旋右旋）来保证平衡，因此Skip list比较容易实现，而且相比平衡树有着较高的运行效率。
查找功能在50W数据量以后，TreeMap更有效率，因为ConcurrentSkipListMap自带锁机制，会占用一些效率，但对于多线程并发的环境下，ConcurrentSkipListMap的效率会比TreeMap要好的。

HashMap和其他Map集合类的比较

HashMap和HashTable的区别
线程是否安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过synchronized 修饰
效率：因为线程安全的问题，HashMap 要比 HashTable 效率高
对 Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛出 NullPointerException。
初始容量大小和每次扩充容量大小的不同：创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用2的幂作为哈希表的大小,后面会介绍到为什么是2的幂次方。
底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable没有这样的机制。

HashMap和HashSet区别

ConcurrentHashMap和Hashtable的区别
底层数据结构： JDK1.7的 ConcurrentHashMap 底层采用分段的数组+链表实现，JDK1.8 采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用数组+链表的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
实现线程安全的方式（重要）：在JDK1.7的时候，ConcurrentHashMap（分段锁）对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。到了 JDK1.8 的时候已经摒弃了Segment的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6以后对 synchronized锁做了很多优化）整个看起来就像是优化过且线程安全的 HashMap，虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

ConcurrentHashMap和Hashtable/HashMap的区别
HashMap不支持并发操作，没有同步方法，ConcurrentHashMap支持并发操作，通过继承 ReentrantLock（JDK1.7重入锁）/CAS和synchronized(JDK1.8内置锁)来进行加锁（分段锁），每次需要加锁的操作锁住的是一个 segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全
JDK1.8之前HashMap的结构为数组+链表，JDK1.8之后HashMap的结构为数组+链表+红黑树；JDK1.8之前ConcurrentHashMap的结构为segment数组+数组+链表，JDK1.8之后ConcurrentHashMap的结构为数组+链表+红黑树
在 1.7 中，ConcurrentHashMap与HashMap 和 Hashtable 最大的不同在于：put 和 get 两次 Hash 到达指定的 HashEntry ，第一次 hash 到达 Segment ,第二次到达 Segment 里面的 Entry ,然后在遍历 entry 链表。
Set
特点：注重独一无二的性质,该体系集合可以知道某物是否已近存在于集合中,不会存储重复的元素
HashSet
线程不安全，HashSet类按照哈希算法来存取集合中的对象，存取速度比较快，允许包含值为null的元素，但最多只能有一个null元素；底层是以哈希表实现的。
内部基于HashMap实现
HashSet存储的对象都被作为HashMap的key值保存到了HashMap中。
```
public boolean add(E e) {
  return map.put(e, new Object())==null;
}
```
put方法调用了hashMap的put方法，value存放一个new Object()，hashMap的put方法根据hash(key) 判断是否重复
其他方法也类似，hashSet类本身没有重写eques和hashCode方法，而是调用了hashMap的方法。
LinkedHashSet
LinkedHashSet继承自HashSet 还多了一个可以同时指定容量和负载因子的构造函数,如不指定则默认是0.75。这是因为HashSet内部是以一个HashMap对象实现的(构造函数中创建赋给Map类型的成员变量map)、LinkedHashSet中是以一个LinkedHashMap对象实现的(构造函数中调用父类的一个默认访问权限级别的构造函数来创建然后同样赋给map)，因为HashMap和LinkedHashMap都是用数组+(双向节点)链表来实现的，所以就有了容量和负载因子这两个参数，也相应地有了这两个构造函数。

TreeSet
来继续看TreeSet的定义：基于TreeMap实现的NavigableSet。根据元素的自然顺序进行排序，或根据创建Set时提供的Comparator进行排序，具体取决于使用的构造方法。
TreeSet实现了SortedSet接口（NavigableSet接口继承了SortedSet接口），顾名思义这是一种排序的Set集合，根据源码可以知道底层使用TreeMap实现的，本质上是一个红黑树原理。也正因为它排了序，所以相对HashSet来说，TreeSet提供了一些额外的根据排序位置访问元素的方法。例如：first(),last(),lower(),higher(),subSet(),headSet(),tailSet()。
TreeSet的排序分两种类型，一种是自然排序；一种是定制排序；
方式一：自然排序
元素自身具备比较性，需要元素实现Comparable接口，重写compareTo方法，也就是让元素自身具备比较性，然后按升序排序。所以自然排序中的元素对象，都必须实现了Comparable接口。不然就会抛出异常。对于TreeSet判断元素是否重复的标准，也是调用元素从Comparable接口继承的compareTo方法，如果返回0就是重复元素(返回一个 -1，0，或1表示这个对象小于、等于或大于指定对象。)。其实Java常见的类基本已经实现了Comparable接口。这种方式叫做元素的自然排序也叫做默认排序。

方式二：定制排序

TreeSet另外一种排序就是定制排序，也叫自定义比较器。这种一般是在元素本身不具备比较性，或者元素本身具备的比较性不满足要求，这个时候就只能让容器自身具备。定制排序，需要关联一个Comparator对象，由Comparator提供逻辑。
一般步骤为，定义一个类实现Comparator接口，重写compare方法。然后将该接口的子类对象作为参数传递给TreeSet的构造方法。

注意：

当Comparable比较方式和Comparator比较方式同时存在时，以Comparator的比较方式为主；
在重写compareTo或者compare方法时，必须要明确比较的主要条件相等时要比较次要条件。（假设姓名和年龄一直的人为相同的人，如果想要对人按照年龄的大小来排序，如果年龄相同的人，需要如何处理？不能直接return 0，因为可能姓名不同（年龄相同姓名不同的人是不同的人）。此时就需要进行次要条件判断（需要判断姓名），只有姓名和年龄同时相等的才可以返回0.）
通过return 0来判断唯一性。

为什么使用TreeSet存入字符串,字符串默认输出是按升序排列的?
因为字符串实现了一个接口,叫做Comparable 接口.字符串重写了该接口的compareTo 方法,所以String对象具备了比较性.那么同样道理,我的自定义元素(例如Person类,Book类)想要存入TreeSet集合,就需要实现该接口,也就是要让自定义对象具备比较性.

treeSet总结：
存入TreeSet集合中的元素要具备比较性.
比较性要实现Comparable接口，重写该接口的compareTo方法
TreeSet属于Set集合，该集合的元素是不能重复的，TreeSet通过compareTo或者compare方法中的来保证元素的唯一性。
添加的元素必须要实现Comparable接口。当compareTo()函数返回值为0时，说明两个对象相等，此时该对象不会添加进来。

列表

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

Arrays.asList()
asList() 是 Arrays 类下的一个方法，用于将数组装换成 List 。在使用时需要注意的是，传入的数组必须是对象数组，而不能是基本类型数组。当传入一个基本类型数组时，Arrays.asList() 真正得到的参数不是数组中的元素，而是数组本身导致 List 只存在一个元素，即这个数组。为了解决这一问题，使用基本类型的包装类即可。此外，在转换为 List 后不能使用集合修改方法 add()、remove()、clear()等方法，否则会抛出异常。造成这一现象的原因是方法返回的并不是新的 java.util.ArrayList，而是Arrays 的一个内部类，这个内部类并没有实现集合的修改方法或者说并没有重写这些方法。而且，通过对数组的修改，会使得List中的对应值也发生改变。
正确使用Arrays.asList()的姿势：
```
List list = new ArrayList<>(Arrays.asList("a", "b", "c"))
Integer [] myArray = { 1, 2, 3 };
List myList = Arrays.stream(myArray).collect(Collectors.toList());
//基本类型也可以实现转换（依赖boxed的装箱操作）
int [] myArray2 = { 1, 2, 3 };
List myList = Arrays.stream(myArray2).boxed().collect(Collectors.toList());
```
ArrayList
ArrayList 是基于数组实现的，所以支持快速随机访问。RandomAccess 接口标识着该类支持快速随机访问。
```
public class ArrayList<E> extends AbstractList<E>
      implements List<E>, RandomAccess, Cloneable, java.io.Serializable
```
ArrayList 底层使用 transient Object[] elementData 存储数据。transient 在序列化时有特殊应用，下面会进行阐述。ArrayList 的默认大小为 10 。

ArrayList的几种构造函数
啥也不传：elementData 引用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
传一个指定的数组容量：根据情况 new 数组或引用 EMPTY_ELEMENTDATA
传一个Collection：调用 Arrays.copyOf() 复制

ArrayList的resize方法
添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为 oldCapacity + (oldCapacity >> 1)，也就是旧容量的 1.5 倍。扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。
boolean add(E e):先调用 void ensureCapacityInternal(size+1)确保添加后数组不越界，返回后添加数据
void ensureCapacityInternal(int minCapacity)：获取默认容量和传入参数的较大者，然后调用ensureExplicitCapacity(minCapacity)
void ensureExplicitCapacity(int minCapacity)：modCount 自增；参数值大于当前数组长度，进行扩容，调用grow(minCapacity)
void grow(int minCapacity)：进行扩容，每次设定新容量为旧容量的1.5倍(int newCapacity = oldCapacity + (oldCapacity >> 1))

ArrayList的remove方法
需要调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上，该操作的时间复杂度为 O(N)，可以看到 ArrayList 删除元素的代价是非常高的。
```
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;
}
```
ArrayList的序列化
ArrayList 基于数组实现，并且具有动态扩容特性，因此保存元素的数组不一定都会被使用，那么就没必要全部进行序列化。保存元素的数组 elementData 使用 transient 修饰，该关键字声明数组默认不会被序列化。ArrayList 实现了 writeObject() 和 readObject() 来控制只序列化数组中有元素填充那部分内容。
```
private void readObject(java.io.ObjectInputStream s)
  throws java.io.IOException, ClassNotFoundException {
  elementData = EMPTY_ELEMENTDATA;
  // Read in size, and any hidden stuff
  s.defaultReadObject();
  // Read in capacity
  s.readInt(); // ignored
  if (size > 0) {
      // be like clone(), allocate array based upon size not capacity
      ensureCapacityInternal(size);
      Object[] a = elementData;
      // Read in all elements in the proper order.
      for (int i=0; i<size; i++) {
          a[i] = s.readObject();
      }
  }
}
private void writeObject(java.io.ObjectOutputStream s)
  throws java.io.IOException{
  // Write out element count, and any hidden stuff
  int expectedModCount = modCount;
  s.defaultWriteObject();
  // Write out size as capacity for behavioural compatibility with clone()
  s.writeInt(size);
  // Write out all elements in the proper order.
  for (int i=0; i<size; i++) {
      s.writeObject(elementData[i]);
  }
  if (modCount != expectedModCount) {
      throw new ConcurrentModificationException();
  }
}
```
序列化时需要使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出。而 writeObject() 方法在传入的对象存在 writeObject() 的时候会去反射调用该对象的 writeObject() 来实现序列化。反序列化使用的是 ObjectInputStream 的 readObject() 方法，原理类似。

ArrayList中的Fail-Fast机制
modCount 用来记录 ArrayList 结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化。在进行序列化或者迭代等操作时，需要比较操作前后 modCount 是否改变，如果改变了需要抛出 ConcurrentModificationException。

ArrayList如何高效使用
在需要大量添加元素的时候，调用 ensureCapacity(int minCapacity)，进行预扩容。

在ArrayList中经常出现Arrays.copyOf()与System.arraycopy()，二者区别是什么？
Arrays.copyOf()内部实际调用了System.arraycopy()方法
System.arraycopy() 需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置
Arrays.copyOf()是系统自动在内部新建一个数组，并返回该数组
Vector
Vector的实现与 ArrayList 类似，但是使用了 synchronized 进行同步。 ```java public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; }

public synchronized E get(int index) { if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index);

return elementData(index);

}

<a name="tAWq8"></a>
### ArrayList与Vector的区别
- Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。
- Arraylist不是同步的，所以在不需要保证线程安全时时建议使用Arraylist。
- Vector每次扩容请求其大小的2倍空间，而ArrayList是1.5倍。
<a name="mfjzj"></a>
### 如何得到线程安全的ArrayList
可以使用 Collections.synchronizedList(); 得到一个线程安全的 ArrayList。
```java
List<String> list = new ArrayList<>();
List<String> synList = Collections.synchronizedList(list);
List<String> list = new CopyOnWriteArrayList<>();

LinkedList

基于双向链表实现，使用 Node 存储链表节点信息，first 与 last指针分别指向头尾节点。

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

ArrayList和LinkedList的区别

是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
底层数据结构： Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是双向链表数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
插入和删除是否受元素位置的影响： ① ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行add(E e) 方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element) ）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② LinkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。
是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index) 方法)。
内存空间占用： ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

CopyOnWriteArrayList

写操作在一个复制的数组上进行，读操作还是在原始数组中进行，读写分离，互不影响。写操作需要加锁，防止并发写入时导致写入数据丢失。写操作结束之后需要把原始数组指向新的复制数组。

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}
final void setArray(Object[] a) {
    array = a;
}
@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
    return (E) a[index];
}

CopyOnWriteArrayList 在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写少的应用场景。但是 CopyOnWriteArrayList 有其缺陷：

内存占用：在写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右
数据不一致：读操作不能读取实时性的数据，因为部分写操作的数据还未同步到读数组中

所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。

Stack

Stack 类表示后进先出（LIFO）的对象堆栈。它通过五个操作对类 Vector 进行了扩展，允许将向量视为堆栈。它提供了通常的 push 和 pop 操作，以及取堆栈顶点的 peek 方法、测试堆栈是否为空的 empty 方法、在堆栈中查找项并确定到堆栈顶距离的 search 方法。
因为它继承自Vector,那么它的实现原理是以数组实现堆栈的。如果要以链表方式实现堆栈可以使用LinkedList。
Stack的继承关系
java.lang.Object
继承者 java.util.AbstractCollection
继承者 java.util.AbstractList
继承者 java.util.Vector
继承者 java.util.Stack
所有已实现的接口：
Serializable, Cloneable, Iterable, Collection, List, RandomAccess
stack的API

boolean empty() 
      测试堆栈是否为空。
E   peek() 
      查看堆栈顶部的对象，但不从堆栈中移除它。
E   pop() 
      移除堆栈顶部的对象，并作为此函数的值返回该对象。
E   push(E item) 
      把项压入堆栈顶部。
int search(Object o) 
      返回对象在堆栈中的位置，以 1 为基数。

总结：

stack由于每个方法上都添加了synchronized并且继承了Vector是线程安全的
Stack实际上也是通过数组去实现的。实际调用的实现方法都是Vector中的方法- push时(即，将元素推入栈中)，是通过将元素追加的数组的末尾中。
peek时(即，取出栈顶元素，不执行删除)，是返回数组末尾的元素。
pop时(即，取出栈顶元素，并将该元素从栈中删除)，是取出数组末尾的元素，然后将该元素从数组中删除。

Queue
Queue接口与List、Set同一级别，都是继承了Collection接口。LinkedList实现了Queue接口。Queue接口窄化了对LinkedList的方法的访问权限（即在方法中的参数类型如果是Queue时，就完全只能访问Queue接口所定义的方法了，而不能直接访问 LinkedList的非Queue的方法），以使得只有恰当的方法才可以使用。BlockingQueue 继承了Queue接口。
队列通常（但并非一定）以 FIFO（先进先出）的方式排序各个元素。不过优先级队列和 LIFO 队列（或堆栈）例外，前者根据提供的比较器或元素的自然顺序对元素进行排序，后者按 LIFO（后进先出）的方式对元素进行排序。无论使用哪种排序方式，队列的头都是调用 remove() 或 poll() 所移除的元素。在 FIFO 队列中，所有的新元素都插入队列的末尾。其他种类的队列可能使用不同的元素放置规则。每个 Queue 实现必须指定其顺序属性。

`boolean`	add(E e) 将指定的元素插入此队列（如果立即可行且不会违反容量限制），在成功时返回 true，如果当前没有可用的空间，则抛出 IllegalStateException。
`E`	`element()` 获取，但是不移除此队列的头。
`boolean`	`offer(E e)` 将指定的元素插入此队列（如果立即可行且不会违反容量限制），当使用有容量限制的队列时，此方法通常要优于 `add(E)`，后者可能无法插入元素，而只是抛出一个异常。
`E`	`peek()` 获取但不移除此队列的头；如果此队列为空，则返回 null。
`E`	`poll()` 获取并移除此队列的头，如果此队列为空，则返回 null。
`E`	`[remove](http://www.cnblogs.com/java/util/Queue.html#remove())()` 获取并移除此队列的头。

Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。如果要使用前端而不移出该元素，使用element()或者peek()方法。
注意：poll和peek方法出错进返回null。因此，向队列中插入null值是不合法的。

Java面试知识点总结-集合类

容器类概览

Map

HashMap

HashMap的基本结构

HashMap核心字段

HashMap的几个构造函数

HashMap的长度为什么是2的幂次方

HashMap的快速失败机制

HashMap定位桶下标的方法

HashMap的Put方法

简述get()流程

简述resize()的过程

HashMap多线程安全性

fail-fast

死链

HashMap版本区别

简述1.8版本与1.8版本前HashMap在hash(key)的区别

HashMap为何链表长度到8才扩展为红黑树

HashMap如何保证其容量为2的n次方

插入算法

插入后的颜色修复

情况一，叔节点是红色

情况二，当前的节点是右孩子，叔节点是黑色

情况三，当前节点是左孩子，叔节点y是黑色

插入算法小结

删除算法

删除算法小结

WeakHashMap

expungeStaleEntries()：清除过期的条目

ConcurrentHashMap原理

ConcurentHashMap的put方法

ConcurentHashMap的get方法

ConcurentHashMap的resize方法

ConcurrentHashMap的remove流程

计算ConcurentHashMap的size大小

ConcurrentHashMap中的remove方法

ConcurrentHashMap的工作原理以及差异对比

简述ConcurrentHashMap中变量使用final和volatile修饰的作用

单线程Hashmap性能对标Concurenthashmap

ConcurrentSkipListMap

HashMap和其他Map集合类的比较

HashMap和HashTable的区别

HashMap和HashSet区别

ConcurrentHashMap和Hashtable的区别

ConcurrentHashMap和Hashtable/HashMap的区别

Set

HashSet

内部基于HashMap实现

LinkedHashSet

TreeSet

方式一：自然排序

方式二：定制排序

为什么使用TreeSet存入字符串,字符串默认输出是按升序排列的?

treeSet总结：

列表

List遍历的选择优先级

Arrays.asList()

ArrayList

ArrayList的几种构造函数

ArrayList的resize方法

ArrayList的remove方法

ArrayList的序列化

ArrayList中的Fail-Fast机制

ArrayList如何高效使用

在ArrayList中经常出现Arrays.copyOf()与System.arraycopy()，二者区别是什么？

Vector

LinkedList

ArrayList和LinkedList的区别

CopyOnWriteArrayList

Stack

Queue