容器类概览

这里直接套用CYC大佬的图。

HashMap

HashMap是什么

HashMap 主要用来存放键值对，它基于哈希表的Map接口实现，是常用的Java集合之一。JDK1.8 之前 HashMap 由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间。

HashMap：它根据键的 hashCode 值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null ，允许多条记录的值为 null 。HashMap 非线程安全，即任一时刻可以有多个线程同时写 HashMap ，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections 的 synchronizedMap 方法使 HashMap 具有线程安全的能力，或者使用 ConcurrentHashMap
Hashtable：Hashtable 是遗留类，很多映射的常用功能与 HashMap 类似，不同的是它承自 Dictionary类，并且是线程安全的，任一时间只有一个线程能写 Hashtable ，并发性不如 ConcurrentHashMap ，因为 ConcurrentHashMap 引入了分段锁。 Hashtable 不建议在新代码中使用，不需要线程安全的场合可以用 HashMap 替换，需要线程安全的场合可以用 ConcurrentHashMap 替换
LinkedHashMap：LinkedHashMap 是 HashMap 的一个子类，保存了记录的插入顺序，在用 Iterator 遍历 LinkedHashMap 时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序
TreeMap：TreeMap 实现 SortedMap 接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的。如果使用排序的映射，建议使用 TreeMap 。在使用 TreeMap 时，key 必须实现 Comparable 接口或者在构造 TreeMap 传入自定义的 Comparator ，否则会在运行时抛出 java.lang.ClassCastException 类型的异常

HashMap的基本结构

HashMap具有数组+链表+红黑树（JDK1.8增加了红黑树部分）的结构。
图片说明

// 基本的 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表中的所有元素。在实际使用过程中要尽力避免。

这里描述下链表的迁移过程：

// 下面这段就是把原来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。

图片说明

有一点注意区别，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 次方。

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

HashMap和其他集合类的比较

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 链表。

ConcurrentHashMap的实现原理

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

ConcurentHashMap不允许空key与空value

https://www.cnblogs.com/fanguangdexiaoyuer/p/12335921.html

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性能一直处于领先地位。

列表

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。

Vector概览

Vector的实现与 ArrayList 类似，但是使用了 synchronized 进行同步。

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

ArrayList与Vector的区别

Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。
Arraylist不是同步的，所以在不需要保证线程安全时时建议使用Arraylist。
Vector每次扩容请求其大小的2倍空间，而ArrayList是1.5倍。

如何得到线程安全的ArrayList

可以使用 Collections.synchronizedList(); 得到一个线程安全的 ArrayList。

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更多的空间（因为要存放直接后继和直接前驱以及数据）。

ArrayList如何高效使用

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

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

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

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

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 不适合内存敏感以及对实时性要求很高的场景。

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

容器类概览

HashMap

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次方

HashMap和其他集合类的比较

HashMap和HashTable的区别

HashMap和HashSet区别

ConcurrentHashMap和Hashtable的区别

ConcurrentHashMap和Hashtable/HashMap的区别

ConcurrentHashMap的实现原理

ConcurentHashMap不允许空key与空value

ConcurentHashMap的put方法

ConcurentHashMap的get方法

ConcurentHashMap的resize方法

ConcurrentHashMap的remove流程

计算ConcurentHashMap的size大小

ConcurrentHashMap中的remove方法

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

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

单线程Hashmap性能对标Concurenthashmap

列表

ArrayList概览

ArrayList的几种构造函数

ArrayList的resize方法

ArrayList的remove方法

ArrayList的序列化

ArrayList中的Fail-Fast机制

Vector概览

ArrayList与Vector的区别

如何得到线程安全的ArrayList

LinkedList概览

ArrayList和LinkedList的区别

ArrayList如何高效使用

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

List遍历的选择优先级

Arrays.asList()

CopyOnWriteArrayList