[1]Java集合体系结构（List、Set、Collection、Map的区别和联系）

集合(容器)面试题 - 图1
1、Collection 接口存储一组不唯一，无序的对象
2、List 接口存储一组不唯一，有序（插入顺序）的对象
3、Set 接口存储一组唯一，无序的对象
4、Map接口存储一组键值对象，提供key到value的映射。Key无序，唯一。value不要求有序，允许重复。（如果只使用key存储，而不使用value，那就是Set）

[2]Vector和ArrayList的区别和联系

相同点：
1）实现原理相同—-底层都使用数组
2）功能相同—-实现增删改查等操作的方法相似
3）都是长度可变的数组结构，很多情况下可以互用
不同点：
1）Vector是早期JDK版本提供，ArrayList是新版本替代Vector的
2）Vector线程安全，ArrayList重速度轻安全，线程非安全长度需增长时，Vector默认增长一倍，ArrayList增长50%

[3]ArrayList和LinkedList的区别和联系

相同点：
两者都实现了List接口，都具有List中元素有序、不唯一的特点。
不同点：
ArrayList实现了长度可变的数组，在内存中分配连续空间。遍历元素和随机访问元素的效率比较高；
集合(容器)面试题 - 图2
LinkedList采用链表存储方式。插入、删除元素时效率比较高
集合(容器)面试题 - 图3

[4]HashMap和Hashtable的区别和联系

相同点：
实现原理相同，功能相同，底层都是哈希表结构，查询速度快，在很多情况下可以互用
不同点：
1、Hashtable是早期提供的接口，HashMap是新版JDK提供的接口
2、Hashtable继承Dictionary类，HashMap实现Map接口
3、Hashtable线程安全，HashMap线程非安全
4、Hashtable不允许null值，HashMap允许null值

[5]HashSet的使用和原理（hashCode()和equals()）

1）哈希表的查询速度特别快，时间复杂度为O（1）。
2）HashMap、Hashtable、HashSet这些集合采用的是哈希表结构，需要用到hashCode哈希码，hashCode是一个整数值。
3）系统类已经覆盖了hashCode方法 自定义类如果要放入hash类集合，必须重写hashcode。如果不重写，调用的是Object的hashcode，而Object的hashCode实际上是地址。
4）向哈希表中添加数据的原理：当向集合Set中增加对象时，首先集合计算要增加对象的hashCode码，根据该值来得到一个位置用来存放当前对象，如在该位置没有一个对象存在的话，那么集合Set认为该对象在集合中不存在，直接增加进去。如果在该位置有一个对象存在的话，接着将准备增加到集合中的对象与该位置上的对象进行equals方法比较，如果该equals方法返回false,那么集合认为集合中不存在该对象，在进行一次散列，将该对象放到散列后计算出的新地址里。如果equals方法返回true，那么集合认为集合中已经存在该对象了，不会再将该对象增加到集合中了。
5）在哈希表中判断两个元素是否重复要使用到hashCode()和equals()。hashCode决定数据在表中的存储位置，而equals判断是否存在相同数据。
6） Y=K(X) ：K是函数，X是哈希码，Y是地址

[6]TreeSet的原理和使用（Comparable和comparator）

1）TreeSet集合，元素不允许重复且有序(自然顺序)
2）TreeSet采用树结构存储数据，存入元素时需要和树中元素进行对比，需要指定比较策略。
3）可以通过Comparable(外部比较器)和Comparator(内部比较器)来指定比较策略，实现了Comparable的系统类可以顺利存入TreeSet。自定义类可以实现Comparable接口来指定比较策略。
4）可创建Comparator接口实现类来指定比较策略，并通过TreeSet构造方法参数传入。这种方式尤其对系统类非常适用。

[7]集合和数组的比较（为什么引入集合）

数组不是面向对象的，存在明显的缺陷，集合完全弥补了数组的一些缺点，比数组更灵活更实用，可大大提高软件的开发效率而且不同的集合框架类可适用于不同场合。具体如下：
1）数组的效率高于集合类.
2）数组能存放基本数据类型和对象，而集合类中只能放对象。
3）数组容量固定且无法动态改变，集合类容量动态改变。
4）数组无法判断其中实际存有多少元素，length只告诉了array的容量。
5）集合有多种实现方式和不同的适用场合，而不像数组仅采用顺序表方式。
6）集合以类的形式存在，具有封装、继承、多态等类的特性，通过简单的方法和属性调用即可实现各种复杂操作，大大提高软件的开发效率。

[8]Collection和Collections的区别

1）Collection是Java提供的集合接口，存储一组不唯一，无序的对象。它有两个子接口List和Set。
2）Java中还有一个Collections类，专门用来操作集合类 ，它提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。

[9]Java的HashMap和Hashtable有什么区别HashSet和HashMap有什么区别？使用这些结构保存的数需要重载的方法是哪些？

答：HashMap与Hashtable实现原理相同，功能相同，底层都是哈希表结构，查询速度快，在很多情况下可以互用
两者的主要区别如下
1、Hashtable是早期JDK提供的接口，HashMap是新版JDK提供的接口
2、Hashtable继承Dictionary类，HashMap实现Map接口
3、Hashtable线程安全，HashMap线程非安全
4、Hashtable不允许null值，HashMap允许null值
HashSet与HashMap的区别
1、HashSet底层是采用HashMap实现的。HashSet 的实现比较简单，HashSet 的绝大部分方法都是通过调用 HashMap 的方法来实现的，因此 HashSet 和 HashMap 两个集合在实现本质上是相同的。
2、HashMap的key就是放进HashSet中对象，value是Object类型的。
3、当调用HashSet的add方法时，实际上是向HashMap中增加了一行(key-value对)，该行的key就是向HashSet增加的那个对象，该行的value就是一个Object类型的常量

[10]TreeMap和TreeSet在排序时如何比较元素？Collections工具类中的sort（）方法如何比较元素？

答：TreeSet要求存放的对象所属的类必须实现Comparable接口，该接口提供了比较元素的compareTo()方法，当插入元素时会 回调该方法比较元素的大小。TreeMap要求存放的键值对映射的键必须实现Comparable接口从而根据键对元素进行排序。Collections 工具类的sort方法有两种重载的形式，第一种要求传入的待排序容器中存放的对象比较实现Comparable接口以实现元素的比较；第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator接口的子类型（需要重写compare方法实现元素的比较），相当于一个临时定义的排序规则，其实就是是通过接口注入比较元素大小的算法，也是对回调模式的应用。

[11]下面的代码在绝大部分时间内都运行得很正常，请问什么情况下会出现问题？根源在哪里？

image.png
答：将if( list.size() <= 0 )改成：while( list.size() <= 0 )

[12]Comparable和Comparator接口是什么？

  1.   如果我们想使用Array或Collection的排序方法时，需要在自定义类里实现Java提供Comparable接口。Comparable接口有compareTo(T OBJ)方法，它被排序方法所使用。我们应该重写这个方法，如果“this”对象比传递的对象参数更小、相等或更大时，它返回一个负整数、0或正整数。但是，在大多数实际情况下，我们想根据不同参数进行排序。比如，作为一个CEO，我想对雇员基于薪资进行排序，一个HR想基于年龄对他们进行排序。这就是我们需要使用Comparator接口的情景，因为Comparable.compareTo(Object o)方法实现只能基于一个字段进行排序，我们不能根据对象排序的需要选择字段。Comparator接口的compare(Object o1, Object o2)方法的实现需要传递两个对象参数，若第一个参数比第二个小，返回负整数；若第一个等于第二个，返回0；若第一个比第二个大，返回正整数。

[13]Comparable和Comparator接口有何区别？

  1. Comparable和Comparator接口被用来对对象集合或者数组进行排序。Comparable接口被用来提供对象的自然排序，我们可以使用它来提供基于单个逻辑的排序。
  3. Comparator接口被用来提供不同的排序算法，我们可以选择需要使用的Comparator来对给定的对象集合进行排序。

[14]说一说 ArrayList 的扩容机制

ArrayList是List接口的实现类，它是支持根据需要而动态增长的数组。java中标准数组是定长的，在数组被创建之后，它们不能被加长或缩短。这就意味着在创建数组时需要知道数组的所需长度，但有时我们需要动态程序中获取数组长度。ArrayList就是为此而生的,但是它不是线程安全的，外ArrayList按照插入的顺序来存放数据
①ArrayList扩容发生在add()方法调用的时候， 调用ensureCapacityInternal()来扩容的，
通过方法calculateCapacity(elementData, minCapacity)获取需要扩容的长度:
②ensureExplicitCapacity方法可以判断是否需要扩容：
③ArrayList扩容的关键方法grow():
获取到ArrayList中elementData数组的内存空间长度 扩容至原来的1.5倍
④调用Arrays.copyOf方法将elementData数组指向新的内存空间时newCapacity的连续空间
从此方法中我们可以清晰的看出其实ArrayList扩容的本质就是计算出新的扩容数组的size后实例化，并将原有数组内容复制到新数组中去。

[15]HashSet如何检查重复

当你把对象加入HashSet时，HashSet会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较，如果没有相符的hashcode，HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象，这时会调用equals（）方法来检查hashcode相等的对象是否真的相同。如果两者相同，HashSet就不会让加入操作成功。（摘自我的Java启蒙书《Head fist java》第二版）
hashCode（）与equals（）的相关规定：

  1. 如果两个对象相等，则hashcode一定也是相同的
  2. 两个对象相等,对两个equals方法返回true
  3. 两个对象有相同的hashcode值，它们也不一定是相等的
  4. 综上，equals方法被覆盖过，则hashCode方法也必须被覆盖
  5. hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

==与equals的区别

  1. ==是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存空间的值是不是相同
  2. ==是指对内存地址进行比较 equals()是对字符串的内容进行比较

  3. ==指引用是否相同 equals()指的是值是否相同

    [16]HashMap的底层实现

    在JDK1.6，JDK1.7中，HashMap采用位桶+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间
    简单说下HashMap的实现原理：
    首先有一个每个元素都是链表（可能表述不准确）的数组，当添加一个元素（key-value）时，就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，同一各链表上的Hash值是相同的，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。

    当链表数组的容量超过初始容量的0.75时，再散列将链表数组扩大2倍，把原链表数组的搬移到新的数组中

即HashMap的原理图是：
image.png




A源码中的数据域

加载因子（默认0.75）：为什么需要使用加载因子，为什么需要扩容呢？因为如果填充比很大，说明利用的空间很多，如果一直不进行扩容的话，链表就会越来越长，这样查找的效率很低，因为链表的长度很大（当然最新版本使用了红黑树后会改进很多），扩容之后，将原来链表数组的每一个链表分成奇偶两个子链表分别挂在新链表数组的散列位置，这样就减少了每个链表的长度，增加查找效率

HashMap本来是以空间换时间，所以填充比没必要太大。但是填充比太小又会导致空间浪费。如果关注内存，填充比可以稍大，如果主要关注查找性能，填充比可以稍小。

  1.  public class HashMap<k,v> extends AbstractMap<k,v> implements Map<k,v>, Cloneable, Serializable {
  2.         private static final long serialVersionUID = 362498820763181265L;
  3.         static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  4.         static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量
  5.         static final float DEFAULT_LOAD_FACTOR = 0.75f;//填充比
  6.         //当add一个元素到某个位桶，其链表长度达到8时将链表转换为红黑树
  7.         static final int TREEIFY_THRESHOLD = 8;
  8.         static final int UNTREEIFY_THRESHOLD = 6;
  9.         static final int MIN_TREEIFY_CAPACITY = 64;
  10.         transient Node<k,v>[] table;//存储元素的数组
  11.         transient Set<map.entry<k,v>> entrySet;
  12.         transient int size;//存放元素的个数
  13.         transient int modCount;//被修改的次数fast-fail机制
  14.         int threshold;//临界值 当实际大小(容量*填充比)超过临界值时，会进行扩容 
  15.         final float loadFactor;//填充比（......后面略）

B HashMap的构造函数

HashMap的构造方法有4种，主要涉及到的参数有，指定初始容量，指定填充比和用来初始化的Map

  1. //构造函数1
  2. public HashMap(int initialCapacity, float loadFactor) {
  3.     //指定的初始容量非负
  4.     if (initialCapacity < 0)
  5.         throw new IllegalArgumentException(Illegal initial capacity:  +
  6.                                            initialCapacity);
  7.     //如果指定的初始容量大于最大容量,置为最大容量
  8.     if (initialCapacity > MAXIMUM_CAPACITY)
  9.         initialCapacity = MAXIMUM_CAPACITY;
  10.     //填充比为正
  11.     if (loadFactor <= 0 || Float.isNaN(loadFactor))
  12.         throw new IllegalArgumentException(Illegal load factor:  +
  13.                                            loadFactor);
  14.     this.loadFactor = loadFactor;
  15.     this.threshold = tableSizeFor(initialCapacity);//新的扩容临界值
  16. }
  18. //构造函数2
  19. public HashMap(int initialCapacity) {
  20.     this(initialCapacity, DEFAULT_LOAD_FACTOR);
  21. }
  23. //构造函数3
  24. public HashMap() {
  25.     this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
  26. }
  28. //构造函数4用m的元素初始化散列映射
  29. public HashMap(Map<!--? extends K, ? extends V--> m) {
  30.     this.loadFactor = DEFAULT_LOAD_FACTOR;
  31.     putMapEntries(m, false);
  32. }

C HashMap的存取机制

1，HashMap如何getValue值，看源码

  1. public V get(Object key) {
  2.         Node<K,V> e;
  3.         return (e = getNode(hash(key), key)) == null ? null : e.value;
  4.     }
  5.       /**
  6.      * Implements Map.get and related methods
  7.      *
  8.      * @param hash hash for key
  9.      * @param key the key
  10.      * @return the node, or null if none
  11.      */
  12.     final Node<K,V> getNode(int hash, Object key) {
  13.         Node<K,V>[] tab;//Entry对象数组
  14.     Node<K,V> first,e; //在tab数组中经过散列的第一个位置
  15.     int n;
  16.     K k;
  17.     /*找到插入的第一个Node，方法是hash值和n-1相与，tab[(n - 1) & hash]*/
  18.     //也就是说在一条链上的hash值相同的
  19.         if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
  20.     /*检查第一个Node是不是要找的Node*/
  21.             if (first.hash == hash && // always check first node
  22.                 ((k = first.key) == key || (key != null && key.equals(k))))//判断条件是hash值要相同，key值要相同
  23.                 return first;
  24.       /*检查first后面的node*/
  25.             if ((e = first.next) != null) {
  26.                 if (first instanceof TreeNode)
  27.                     return ((TreeNode<K,V>)first).getTreeNode(hash, key);
  28.                 /*遍历后面的链表，找到key值和hash值都相同的Node*/
  29.                 do {
  30.                     if (e.hash == hash &&
  31.                         ((k = e.key) == key || (key != null && key.equals(k))))
  32.                         return e;
  33.                 } while ((e = e.next) != null);
  34.             }
  35.         }
  36.         return null;
  37.     }

D HasMap的扩容机制resize();

构造hash表时，如果不指明初始大小，默认大小为16（即Node数组大小16），如果Node[]数组中的元素达到（填充比*Node.length）重新调整HashMap大小 变为原来2倍大小,扩容很耗时

  1.   /**
  2.      * Initializes or doubles table size.  If null, allocates in
  3.      * accord with initial capacity target held in field threshold.
  4.      * Otherwise, because we are using power-of-two expansion, the
  5.      * elements from each bin must either stay at same index, or move
  6.      * with a power of two offset in the new table.
  7.      *
  8.      * @return the table
  9.      */
  10.     final Node<K,V>[] resize() {
  11.         Node<K,V>[] oldTab = table;
  12.         int oldCap = (oldTab == null) ? 0 : oldTab.length;
  13.         int oldThr = threshold;
  14.         int newCap, newThr = 0;
  16.     /*如果旧表的长度不是空*/
  17.         if (oldCap > 0) {
  18.             if (oldCap >= MAXIMUM_CAPACITY) {
  19.                 threshold = Integer.MAX_VALUE;
  20.                 return oldTab;
  21.             }
  22.     /*把新表的长度设置为旧表长度的两倍，newCap=2*oldCap*/
  23.             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  24.                      oldCap >= DEFAULT_INITIAL_CAPACITY)
  25.           /*把新表的门限设置为旧表门限的两倍，newThr=oldThr*2*/
  26.                 newThr = oldThr << 1; // double threshold
  27.         }
  28.      /*如果旧表的长度的是0，就是说第一次初始化表*/
  29.         else if (oldThr > 0) // initial capacity was placed in threshold
  30.             newCap = oldThr;
  31.         else {               // zero initial threshold signifies using defaults
  32.             newCap = DEFAULT_INITIAL_CAPACITY;
  33.             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  34.         }
  38.         if (newThr == 0) {
  39.             float ft = (float)newCap * loadFactor;//新表长度乘以加载因子
  40.             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  41.                       (int)ft : Integer.MAX_VALUE);
  42.         }
  43.         threshold = newThr;
  44.         @SuppressWarnings({"rawtypes","unchecked"})
  45.     /*下面开始构造新表，初始化表中的数据*/
  46.         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  47.         table = newTab;//把新表赋值给table
  48.         if (oldTab != null) {//原表不是空要把原表中数据移动到新表中    
  49.             /*遍历原来的旧表*/        
  50.             for (int j = 0; j < oldCap; ++j) {
  51.                 Node<K,V> e;
  52.                 if ((e = oldTab[j]) != null) {
  53.                     oldTab[j] = null;
  54.                     if (e.next == null)//说明这个node没有链表直接放在新表的e.hash & (newCap - 1)位置
  55.                         newTab[e.hash & (newCap - 1)] = e;
  56.                     else if (e instanceof TreeNode)
  57.                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  58.     /*如果e后边有链表,到这里表示e后面带着个单链表，需要遍历单链表，将每个结点重*/
  59.                     else { // preserve order保证顺序
  60.                     新计算在新表的位置，并进行搬运
  61.                         Node<K,V> loHead = null, loTail = null;
  62.                         Node<K,V> hiHead = null, hiTail = null;
  63.                         Node<K,V> next;
  65.                         do {
  66.                             next = e.next;//记录下一个结点
  67.               //新表是旧表的两倍容量，实例上就把单链表拆分为两队，
  68. 　　　　　　　　　　　　　　//e.hash&oldCap为偶数一队，e.hash&oldCap为奇数一对
  69.                             if ((e.hash & oldCap) == 0) {
  70.                                 if (loTail == null)
  71.                                     loHead = e;
  72.                                 else
  73.                                     loTail.next = e;
  74.                                 loTail = e;
  75.                             }
  76.                             else {
  77.                                 if (hiTail == null)
  78.                                     hiHead = e;
  79.                                 else
  80.                                     hiTail.next = e;
  81.                                 hiTail = e;
  82.                             }
  83.                         } while ((e = next) != null);
  85.                         if (loTail != null) {//lo队不为null，放在新表原位置
  86.                             loTail.next = null;
  87.                             newTab[j] = loHead;
  88.                         }
  89.                         if (hiTail != null) {//hi队不为null，放在新表j+oldCap位置
  90.                             hiTail.next = null;
  91.                             newTab[j + oldCap] = hiHead;
  92.                         }
  93.                     }
  94.                 }
  95.             }
  96.         }
  97.         return newTab;
  98.     }

E JDK1.8使用红黑树的改进

在java jdk8中对HashMap的源码进行了优化，在jdk7中，HashMap处理“碰撞”的时候，都是采用链表来存储，当碰撞的结点很多时，查询时间是O（n）。
在jdk8中，HashMap处理“碰撞”增加了红黑树这种数据结构，当碰撞结点较少时，采用链表存储，当较大时（>8个），采用红黑树（特点是查询时间是O（logn））存储（有一个阀值控制，大于阀值(8个)，将链表存储转换成红黑树存储）
image.png
问题分析：

你可能还知道哈希碰撞会对hashMap的性能带来灾难性的影响。如果多个hashCode()的值落到同一个桶内的时候，这些值是存储到一个链表中的。最坏的情况下，所有的key都映射到同一个桶中，这样hashmap就退化成了一个链表——查找时间从O(1)到O(n)。
随着HashMap的大小的增长，get()方法的开销也越来越大。由于所有的记录都在同一个桶里的超长链表内，平均查询一条记录就需要遍历一半的列表。
JDK1.8HashMap的红黑树是这样解决的：
如果某个桶中的记录过大的话（当前是TREEIFY_THRESHOLD = 8），HashMap会动态的使用一个专门的treemap实现来替换掉它。这样做的结果会更好，是O(logn)，而不是糟糕的O(n)。
它是如何工作的？前面产生冲突的那些KEY对应的记录只是简单的追加到一个链表后面，这些记录只能通过遍历来进行查找。但是超过这个阈值后HashMap开始将列表升级成一个二叉树，使用哈希值作为树的分支变量，如果两个哈希值不等，但指向同一个桶的话，较大的那个会插入到右子树里。如果哈希值相等，HashMap希望key值最好是实现了Comparable接口的，这样它可以按照顺序来进行插入。这对HashMap的key来说并不是必须的，不过如果实现了当然最好。如果没有实现这个接口，在出现严重的哈希碰撞的时候，你就并别指望能获得性能提升了。

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

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上面也讲到了过了，Hash 值的范围值-2147483648到2147483647，前后加起来大概40亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash”。（n代表数组长度）。这也就解释了 HashMap 的长度为什么是2的幂次方。
这个算法应该如何设计呢？
我们首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。

[18]HashMap 多线程操作导致死循环问题

主要原因在于 并发下的Rehash 会造成元素之间会形成一个循环链表。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。

[19]CouncurrentHashMap 和CouncurrentHashMap变化

1、底层：
（1）底层数据结构：
：数组（Segment） + 数组（HashEntry） + 链表（HashEntry节点）
底层一个Segments数组，存储一个Segments对象，一个Segments中储存一个Entry数组，存储的每个Entry对象又是一个链表头结点。
image.png
数据结构：
Node数组+链表 / 红黑树： 类似hashMap
Node数组使用来存放树或者链表的头结点，当一个链表中的数量到达一个数目时，会使查询速率降低，所以到达一定阈值时，会将一个链表转换为一个红黑二叉树，通告查询的速率。
image.png
底层数据结构：
hashMap同hashTable；都是使用数组 + 链表结构
ConcurrentHashMap
：使用 Segment数组 + HashEntry数组 + 链表
：使用 Node数组+链表+ 红黑树
（3） ： 效率
hashMap只能单线程操作，效率低下
hashTable使用的是synchronized方法锁，若一个线程抢夺了锁，其他线程只能等到持锁线程操作完成之后才能抢锁操作
《1.7》ConcurrentHashMap 使用的分段锁，如果一个线程占用一段，别的线程可以操作别的部分，
《1.8》简化结构，put和get不用二次哈希，一把锁只锁住一个链表或者一棵树，并发效率更加提升。
保证安全机制
，
分段锁 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。

使用的是优化的synchronized 关键字同步代码块 和 cas操作了维护并发。

[20]其他并发集合类

ConcurrentSkipListMap

基于跳表实现，按照 key 自然排序，key 不能为 null，类似 TreeMap。
利用 volatile+CAS 来保证线程安全。

ConcurrentSkipListSet

使用 ConcurrentSkipListMap 实现。

CopyOnWriteArrayList

  基于数组实现，相当于支持并发的 ArrayList，刚创建时初始化为长度0的数组。
  利用写时复制来保证线程安全。
  写时复制：数组是 volatile 类型的，修改数组时，首先 ReentrantLock 加锁，然后复制一个副本数组，对副本进行修改完成后，把原来的数组指向这个新的数组完成赋值。读时不用加锁。

CopyOnWriteArraySet

使用 CopyOnWriteArrayList 实现。去重的，但是按照插入顺序排序的。