参考：https://juejin.cn/post/6956079061726658568
https://juejin.cn/post/6844903664042164232

一、集合框架体系

1. 集合框架体系

集合：对象的容器，定义了对多个对象进行操作的常用方法。

集合和数组的区别：
（1）数组长度固定，集合长度不固定
（2）数组可以存储基本类型和引用类型，集合只能存储引用类型
（3）数组只能存储同一类型的元素，集合可以存储不同类型的元素

集合框架体系：
04-集合 - 图1

2. Iterable接口

public interface Iterable<T> {
    // 返回一个迭代器
    Iterator<T> iterator();
    // 实现的默认的for-each方法
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

派生自Iterable接口的集合，支持for-each循环。

3. Collection接口

表示：代表一组任意类型的对象。
根据集合的属性又可以划分：是否允许重复元素？元素是否有序？

public interface Collection<E> extends Iterable<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o); // 是否包含某个元素
    boolean containsAll(Collection<?> c); // 是否包含另一个集合的全部元素
    Iterator<E> iterator(); // 迭代
    Object[] toArray();
    boolean add(E e); // 增加单个元素
    boolean addAll(Collection<? extends E> c); // 增加在另一个集合中的元素
    boolean remove(Object o); // 移除单个元素
    boolean removeAll(Collection<?> c); // 移除在另一个集合中的元素
    boolean retainAll(Collection<?> c); // 保持在另一个集合中的元素
    void clear(); // 清空集合
    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, 0);
    }
    default Stream<E> stream() {
        return StreamSupport.stream(spliterator(), false);
    }
    default Stream<E> parallelStream() {
        return StreamSupport.stream(spliterator(), true);
    }
}

二、List接口

List表示一个有序集合，在Collection接口的基础上增加了在指定位置插入元素，在集合中检索元素位置等方法。

public interface List<E> extends Collection<E> {
    boolean addAll(int index, Collection<? extends E> c); // 在指定位置插入另一个集合的所有元素
    E get(int index); // 获取指定位置的元素
    E set(int index, E element); // 设置指定位置的元素值
    void add(int index, E element); // 在指定位置插入元素
    E remove(int index); // 删除指定位置的元素
    int indexOf(Object o); // 查询元素在集合中的位置
    int lastIndexOf(Object o); // 查询元素在集合中的最后一个位置
    List<E> subList(int fromIndex, int toIndex); // 根据下标获得一个子列表
    default void sort(Comparator<? super E> c) // 对列表进行排序
}

1. ArrayList

只基于数组实现，线程不安全
底层维护了一个object类型的数组elementData来存储元素；
如果使用无参构造器，初始大小为0，首次添加元素时扩容为10，后续需要扩容时按照1.5倍扩容。
如果初始化时声明了大小，后续扩容时按照1.5倍扩容。
被transient修饰的属性不参与对象的序列化。
capacity表示数组容量，size表示数组中的元素个数。

2. LinkedList

实现了List和Deque接口，底层是双向链表，线程不安全。

3. Vector

可以扩缩容的存储对象的数组，线程安全。

比较

	ArrayList	LinkedList	Vector
是否线程安全	否	否	是
底层数据结构	Object数组	双向循环链表	Object数组
插入、删除操作时间复杂度	插入、删除最后一个元素为O(1)，插入、删除元素到指定位置为O(n)	插入、删除元素为O(1)	插入、删除最后一个元素为O(1)，插入、删除元素到指定位置为O(n)
是否支持随机访问	实现了RandmoAccess接口，可以根据下标获取元素，支持随机访问	不支持	实现了RandmoAccess接口，可以根据下标获取元素，支持随机访问

三、Set接口

Set表示不包含重复元素的集合，最多只有一个null元素。Set接口和Collection接口相比，没有提供更多的方法。

public interface Set<E> extends Collection<E> {
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    boolean add(E e);
    boolean remove(Object o);
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean retainAll(Collection<?> c);
    boolean removeAll(Collection<?> c);
    void clear();
    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT);
    }
}

HashSet

底层实现基于HashMap，使用HashMap的key存储元素，基于默认的装载因子0.75，也可以自定义装载因子。

LinkedHashSet

LinkedHashSet也实现了Set接口，而且是HashSet的子类。
不同之处在于：LinkedHashSet的底层基于LinkedHashMap，而HashSet使用的是HashMap。
TreeSet
TreeSet实现了SortedSet接口 ```java

public interface SortedSet extends Set { Comparator<? super E> comparator(); SortedSet subSet(E fromElement, E toElement); SortedSet headSet(E toElement); SortedSet tailSet(E fromElement); E first(); E last(); @Override default Spliterator spliterator() { return new Spliterators.IteratorSpliterator(this, Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED) { @Override public Comparator<? super E> getComparator() { return SortedSet.this.comparator(); } }; } }


|  | HashSet | LinkedHashSet | TreeSete |
| --- | --- | --- | --- |
| 特点 | 无序、唯一 | 无序、唯一 | 有序、唯一 |
| 是否线程安全 | 否 | 否 |  |
| 底层结构 | HashMap | LinkedHashMap | 红黑树 |
---
<a name="XgiTr"></a>
# 四、Map接口
一个Map表示将key映射到value的接口，其中key不能重复，每个key可以映射到最多一个value。<br />Map接口提供了三种集合视角，分别是：只包含key的Set，只包含value的集合，和包含key-value映射的Set。
```java
public interface Map<K, V> {
    int size();
    boolean isEmpty();
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    V get(Object key);
    V put(K key, V value);
    V remove(Object key);
    void clear();
    void putAll(Map<? extends K, ? extends V> m)；
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();
    default V getOrDefault(Object key, V defaultValue);
    default V putIfAbsent(K key, V value);
    default boolean replace(K key, V oldValue, V newValue);
    default boolean remove(Object key, Object value);
    default void forEach(BiConsumer<? super K, ? super V> action);
}

1. HashMap

1.1 层次关系

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {}

HashMap类继承了抽象类AbstractMap，实现了Map接口。

1.2 基本思想

JDK1.8之后，HashMap的底层实现基于数组+链表+红黑树。

1.3 类静态属性

// 默认的初始哈希表容量
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;

1.4 基本结构

链表节点Node

 static class Node<K,V> implements Map.Entry<K,V> {
   final int hash;  // key的hash值，
   final K key;     // key
   V value;         // value
   Node<K,V> next;  // next Node
   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;
   }
 }

hash函数

 static final int hash(Object key) {
   int h;
   // 如果key为null，hash值为0，否则：key的hashCode结果的高16位与低16位做异或运算。
   return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

1.5 对象属性

transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;

1.6 核心方法分析

1.6.1 初始化

指定初始容量和加载因子

 // 第一种初始化：指定数组初始容量和加载因子
 public HashMap(int initialCapacity, float loadFactor) {
   if (initialCapacity < 0)
     throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
   if (initialCapacity > MAXIMUM_CAPACITY)
     initialCapacity = MAXIMUM_CAPACITY;
   if (loadFactor <= 0 || Float.isNaN(loadFactor))
     throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
   this.loadFactor = loadFactor;
   this.threshold = tableSizeFor(initialCapacity);// ?
 }
 // tableSizeFor方法：对于给定的capacity，返回不小于它的2的幂次的新的capacity
 // 比如：给定5-8会返回8，给定9-16会返回16，给定17-32会返回32。
 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
 public HashMap(int initialCapacity) {
   this(initialCapacity, DEFAULT_LOAD_FACTOR);
 }
 // 方法三：无参构造，使用默认的初始容量16和加载因子0.75构造一个空的HashMap
 public HashMap() {
   this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
 }

使用已有的map进行构造

 // 方法四：基于Map构造，先使用方法三构造，在将Map保存到HashMap中
 public HashMap(Map<? extends K, ? extends V> m) {
   this.loadFactor = DEFAULT_LOAD_FACTOR;
   putMapEntries(m, false);
 }
 // putMapEntries方法：批量插入元素
 final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
   int s = m.size();
   if (s > 0) {
     if (table == null) { // pre-size
       float ft = ((float)s / loadFactor) + 1.0F;
       int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                (int)ft : MAXIMUM_CAPACITY);
       if (t > threshold)
         threshold = tableSizeFor(t);
     }
     else if (s > threshold)  // 如果m元素数量大于阈值，需要扩容
       resize();
     // 遍历m，插入HashMap
     for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
       K key = e.getKey();
       V value = e.getValue();
       putVal(hash(key), key, value, false, evict);
     }
   }
 }

1.6.2 元素插入put

public V put(K key, V value) {
    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;  // key对应的数组下标所在的首个节点元素
    int n;  // 哈希表容量，数组长度
    int i;  // key对应的数组下标
    // 步骤一：预计算：如果原来的哈希表为空，新哈希表的长度为扩容后的长度
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 分支1：如果key的哈希值对应的数组下标所在的元素为空，直接构建新的节点插入即可
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {  // 分支2：如果key对应的数组下标存储不为空
        Node<K,V> e;  // 根据传入的key找到的节点
        K k;  // 首个节点元素的key
        // 分支2.1：如果传入的key与首个节点元素的key相等，则首个节点元素即为找到的节点
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)  // 分支2.2：如果是红黑树，使用相应的方法找到节点
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {  // 分支2.3：头结点不是要找的节点&链表结构：遍历链表
            for (int binCount = 0; ; ++binCount) {
                // 分支2.3.1：如果遍历完链表都没有找到，在链表末尾插入新的节点
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 如果插入新的结点后，当前链表长度大于树化的阈值，对链表进行树化转变为红黑树结构
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 分支2.3.2：如果遍历链表过程中找到了对应结点，中断遍历，此时结点e为找到的节点
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;  // 通过移动p指针来遍历链表
            }
        }
        // 找到结点之后的赋值操作
        // 分支2.3.1插入了新的结点同时进行了赋值，其余分支都是修改了原来的结点值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue; // 对于修改了原有结点值的情况，返回原来的值，且修改次数modCount和哈希表元素数量size都不变
        }
    }
    // 只有对于分支2.3.1的情况，有新的结点插入，修改次数加一，元素个数加一，可能需要扩容，且原来的值为null。
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

1.6.3 哈希表扩容resize

final Node<K, V>[] resize () {
    Node<K, V>[] oldTab = table;  // 保存原来的哈希表
    int oldCap = (oldTab == null) ? 0 : oldTab.length;  // 原来的哈希表容量
    int oldThr = threshold;  // 原来的哈希表扩容阈值
    int newCap, newThr = 0;  // 初始化新哈希表的容量和扩容阈值为0
    // 步骤一：计算新的哈希表的容量和扩容阈值
    // 1.1 如果原来的哈希表不为空
    if (oldCap > 0) {
        // 1.1.1 如果原来的哈希表的容量已经不小于允许的最大容量，则无法进行扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } // 1.1.2 新哈希表容量翻倍，扩容阈值翻倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    } // 1.2 如果旧哈希表为空但是其扩容阈值大于0（？），则新哈希表的容量等于就哈希表的扩容阈值。
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else { // 1.3 旧哈希表为空&&扩容阈值为0（旧哈希表使用无参构造且没有执行其他任何操作），使用默认值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 步骤二：扩容
    // 如果新的扩容阈值为0（？），重新根据容量和装载因子计算
    if (newThr == 0) {
        float ft = (float) newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes", "unchecked"})
    Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];  // 初始化空的新的哈希表
    table = newTab;
    // 如果旧的哈希表不为空，需要将其搬运过来
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {  // 遍历旧哈希表中的每个桶
            Node<K, V> e;  //保存结点的临时变量
            if ((e = oldTab[j]) != null) {  // 如果桶的第一个结点不为空
                oldTab[j] = null;  // 删除旧哈希表的结点便于JVM的GC
                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 { // 情况三：如果当前的桶是链表，将链表拆分为两个新链表，插入到新哈希表的对应桶中
                    Node<K, V> loHead = null, loTail = null;  // 旧哈希表当前bin的链表拆分后的头结点和尾结点（低位）
                    Node<K, V> hiHead = null, hiTail = null;  // 旧哈希表当前bin的链表拆分后的头结点和尾结点（高位）
                    Node<K, V> next;
                    // 步骤1：对于链表中的每个结点，判断在新哈希表中的位置，据此构建两个链表
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {  // 与旧哈希表中的位置相等
                            if (loTail == null)  // 用head指向第一个结点
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;  // tail始终指向最后一个结点
                        } else {  // ((e.hash & oldCap) == 1)，新的位置=旧的位置+旧哈希表的容量
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 步骤2：将两个链表分别插入到新哈希表中去
                    if (loTail != null) {
                        loTail.next = null; // 对于新哈希表中的链表，需要使其尾结点的next指向null
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

1.6.4 元素查询get

// 给定key，获取在哈希表中的值
public V get (Object key){
    Node<K, V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// hash函数：给定key，使用key的hashCode方法结果的高16位和低16位做异或运算得到
static final int hash (Object key){
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final Node<K, V> getNode (int hash, Object key){
    Node<K, V>[] tab;
    Node<K, V> first, e;
    int n;
    K k;
    // 哈希表存在且不为空，key所在的bin不为空
    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)  // 如果bin为红黑树结构，调用相应的方法
                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;
}

1.6.5 元素删除remove

// 给定key，删除哈希表中的对应结点，返回删除的结点值
public V remove (Object key){
    Node<K, V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
final Node<K, V> removeNode (int hash, Object key, Object value,boolean matchValue, boolean movable) {
    Node<K, V>[] tab;
    Node<K, V> p;
    int n, index;
    // 哈希表存在且不为空，key所在的bin不为空
    if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
        Node<K, V> node = null, e;
        K k;
        V v;
        // 步骤一：找到待删除的结点
        // 情况一：如果第一个结点即为要找的结点
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode) // 情况二：如果为红黑树，调用相应的方法找到待删除的结点
                node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
            else { // 情况三：如果为链表，遍历找到待删除的结点
                do {
                    if (e.hash == hash &&
                            ((k = e.key) == key ||
                                    (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 步骤二：删除对应结点
        if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
            if (node instanceof TreeNode) // 待删节点为树节点
                ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
            else if (node == p)  // 待删节点为头结点
                tab[index] = node.next;
            else  // 待删节点为链表的非头结点
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

1.6.6 元素更新replace

// 将哈希表中的键等于key、值等于oldValue的结点的值更新为newValue
// 返回是否更新成功（即输入的key:oldValue是否存在）
public boolean replace (K key, V oldValue, V newValue){
    Node<K, V> e;
    V v;
    if ((e = getNode(hash(key), key)) != null && ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
        e.value = newValue;
        afterNodeAccess(e);
        return true;
    }
    return false;
}
// 将哈希表中的键等于key的结点（不论原来的value是什么）的值更新为value
// 返回key对应的原来的value
public V replace (K key, V value){
    Node<K, V> e;
    if ((e = getNode(hash(key), key)) != null) {
        V oldValue = e.value;
        e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
    return null;
}

1.7 总结

2个重要的参数，capacity和装载因子。
capacity是哈希表中桶的数量，装载因子衡量了哈希表中元素个数与容量的关系，当元素个数/容量大于装载因子的时候，哈希表就要扩容。
扩容意味着增加桶的数量，对原有的元素重新作哈希得到存储位置。

2. LinkedHashMap

3. HashTable

HashTable虽然也实现了Map接口，但是它继承了DIctionary抽象类，而HashMap继承了AbstractMap抽象类。
HastTable是线程安全的。

public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable {}

Dictionary接口

public abstract class Dictionary<K,V> {
    public Dictionary() {}
    public abstract int size();
    public abstract boolean isEmpty();
    public abstract Enumeration<K> keys();
    public abstract Enumeration<V> elements();
    public abstract V get(Object key);
    public abstract V put(K key, V value);
    public abstract V remove(Object key);
}

4. ConcurrentHashMap

和HashTable一样，都是线程安全的，区别在于实现线程安全的方式不同。

底层数据结构不同：
JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。
Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的。

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

JDK1.7的ConcurrentHashMap

JDK1.8的ConcurrentHashMap

JDK1.7（上面有示意图）

首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。
ConcurrentHashMap 是由 Segment 数组结构和 HahEntry 数组结构组成。
Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁，扮演锁的角色。HashEntry 用于存储键值对数据。
static class Segment extends ReentrantLock implements Serializable { } 复制代码
一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似，是一种数组和链表结构，一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。

JDK1.8 （上面有示意图）

ConcurrentHashMap取消了Segment分段锁，采用CAS和synchronized来保证并发安全。数据结构跟HashMap1.8的结构类似，数组+链表/红黑二叉树。
synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。

5. 总结

	HashMap	LinkedHashMap	HashTable	ConcurrentHashMap
是否线程安全	非线程安全	非线程安全	线程安全	线程安全
对null的支持	允许一个null作为key，多个null作为value		不允许null作为key或value
初始化	（1）创建时如果不指定容量，默认初始值为16，之后每次扩充为原来的2倍（2）创建时指定了容量初始值，会扩充为2的幂次方大小		（1）创建时如果不指定容量，默认初始值为11，之后每次扩充为2n+1 （2）创建时指定了初始值，则使用指定的值进行初始化
底层实现	JDK1.8之前使用数组+链表，JDK1.8之后使用数组+链表+红黑树，当链表长度大于阈值时，将链表转化为红黑树。	数组+链表+红黑树数组-》双向链表	数组+链表